MathLabs

Bài 1

Có 20262026 số nguyên lớn hơn 11 được viết trên bảng đen, không nhất thiết khác nhau. Trong một nước đi, Khổng Tử chọn hai số nguyên m>1m>1 và n>1n>1 ở hai vị trí khác nhau trên bảng và thay hai số nguyên này bằng lcm⁡(m,n)gcd⁡(m,n)\tfrac{\operatorname{lcm}(m,n)}{\gcd(m,n)} và gcd⁡(m,n)\gcd(m,n). Ông tiếp tục thực hiện các nước đi chừng nào còn có thể. (a) Chứng minh rằng, bất kể các lựa chọn của Khổng Tử, sau hữu hạn nước đi, có đúng một số nguyên MM trên bảng lớn hơn 11. (b) Chứng minh rằng giá trị của MM không phụ thuộc vào các lựa chọn của Khổng Tử.
Bước 3 trên 4: Trên số mũ của mỗi số nguyên tố, một nước đi là một bước Euclid
Bước trướcBước tiếp
(vp(m),vp(n))=(x,y) ⟼ (min⁡(x,y), ∣x−y∣),gcd⁡(min⁡(x,y),∣x−y∣)=gcd⁡(x,y)(v_p(m),v_p(n))=(x,y)\ \longmapsto\ (\min(x,y),\,|x-y|),\qquad \gcd(\min(x,y),|x-y|)=\gcd(x,y)
Phân tích chi tiết

Cố định một số nguyên tố pp và viết x=vp(m)x=v_p(m), y=vp(n)y=v_p(n) cho số mũ pp-adic của hai số được chọn. Khi đó vp(gcd⁡(m,n))=min⁡(x,y)v_p(\gcd(m,n))=\min(x,y) và vp(lcm⁡(m,n)/gcd⁡(m,n))=max⁡(x,y)−min⁡(x,y)=∣x−y∣v_p(\operatorname{lcm}(m,n)/\gcd(m,n))=\max(x,y)-\min(x,y)=|x-y|. Vì gcd⁡(min⁡(x,y),∣x−y∣)=gcd⁡(x,y)\gcd(\min(x,y),|x-y|)=\gcd(x,y) (tính bất biến chuẩn của một bước trừ trong thuật toán Euclid), ước chung lớn nhất của cả 20262026 số mũ vp(t1),…,vp(t2026)v_p(t_1),\ldots,v_p(t_{2026}) trên bảng không đổi qua mọi nước đi.