MathLabs

第1题

黑板上写有 20262026 个大于 11 的整数,不一定互不相同。在一次操作中,孔子从黑板的不同位置选取两个整数 m>1m>1 与 n>1n>1,并把这两个整数替换为 lcm⁡(m,n)gcd⁡(m,n)\tfrac{\operatorname{lcm}(m,n)}{\gcd(m,n)} 与 gcd⁡(m,n)\gcd(m,n)。只要还能进行,他就不断继续操作。(a) 求证:无论孔子如何选择,经过有限次操作后,黑板上恰有一个大于 11 的整数 MM。(b) 求证:MM 的值不依赖于孔子的选择。
第 1/4 步:改写替换规则并追踪乘积
lcm⁡(m,n)gcd⁡(m,n)=mngcd⁡(m,n)2,new pair product=mngcd⁡(m,n)\frac{\operatorname{lcm}(m,n)}{\gcd(m,n)}=\frac{mn}{\gcd(m,n)^2},\qquad \text{new pair product}=\frac{mn}{\gcd(m,n)}
详细分析

利用 lcm⁡(m,n)⋅gcd⁡(m,n)=mn\operatorname{lcm}(m,n)\cdot\gcd(m,n)=mn,替换后的两个数是 g:=gcd⁡(m,n)g:=\gcd(m,n) 与 mn/g2mn/g^2,其乘积为 mn/gmn/g。每当 g>1g>1 时,新乘积 mn/gmn/g 严格小于原来的乘积 mnmn,故黑板上全部 20262026 个数的乘积严格减小;每当 g=1g=1 时,替换结果为 (1,mn)(1,mn),总乘积不变,但会多出一个新的 11(因为 m,n>1m,n>1 都不等于 11,而 mn>1mn>1)。