设正整数r与正整数n互素,且r小于n,证明存在小于n的正整数k,使得kr+1能被n整除.
用【反证法】和【抽屉原理】
记A(k)=kr+1,k=0,1,2,3,……,n-1,
若n个正整数A(0),A(1),A(2),……,A(n-1)都不能被n整除,那么除以n所得余数只能是1,2,3,……,n-1,这n-1种不同的可能。
根据【抽屉原理】n个正整数A(0),A(1),A(2),……,A(n-1)中至少有两个在除以n所得余数相同,设它们是A(i)和A(j),i<j。
那么A(j)-A(i)一定是n的整数倍,即(j-i)r一定是n的整数倍。
由于r和n互素,那么j-i一定是n的整数倍,
但是1≤j-i<n-1,j-i就不可能是n的整数倍。
这样就得到了矛盾,命题证毕。全部
用【反证法】和【抽屉原理】
记A(k)=kr+1,k=0,1,2,3,……,n-1,
若n个正整数A(0),A(1),A(2),……,A(n-1)都不能被n整除,那么除以n所得余数只能是1,2,3,……,n-1,这n-1种不同的可能。
根据【抽屉原理】n个正整数A(0),A(1),A(2),……,A(n-1)中至少有两个在除以n所得余数相同,设它们是A(i)和A(j),i<j。
那么A(j)-A(i)一定是n的整数倍,即(j-i)r一定是n的整数倍。
由于r和n互素,那么j-i一定是n的整数倍,
但是1≤j-i<n-1,j-i就不可能是n的整数倍。
这样就得到了矛盾,命题证毕。收起