题目

数论的一个题,用裴蜀定理证明：
m个盒中各有若干个球,每一次可在其中任选n（n

提问时间：2020-12-22

答案

充分性:若(m,n)=1,则由裴蜀定理,存在正整数x,y使得xn-ym=1,即xn=ym+1.
将m个盒子排成一圈,从某个盒子A开始,(按固定方向)顺次进行x次操作,则由上述等式可知,操作的结果是使A盒子中增加了y+1个球,而其它盒子中都增加了y个球,即A盒子比其余的盒子多增加了1个球.因此,如果选A盒子为球数最少的盒子,则通过上述方法有限次后可使所有盒子中球数相等.
必要性:反证法.
仍设有m个盒子(m>n),开始时共有a个球(a是一个待定的正整数),设经过k次操作使得m个盒子的球数都相等,设此时每个盒子各有p个球.由于一次操作使球的总数增加n,故有 kn+a=mp.
由此可见,m与n的最大公约数必须整除a.因此,当m,n不互素时,若取a=1,则上面的等式不可能成立,即不能通过有限次操作使每个盒子中的球数相等,矛盾.
因此假设不成立,从而必有(m,n)=1.