求证：p为质数,给定一个不能被p整除的正整数x,则存在y和k使得xy=1+kp等式成立

Question

求证：p为质数,给定一个不能被p整除的正整数x,则存在y和k使得xy=1+kp等式成立

Answer 1

互质的数a,b.则最小公倍数为ab.则a/b,2a/b,3a/b.ba/b共b个数,这b个数除以b之后的余数的集合,必然为{0,1,2,3.b-2,b-1}
题中p和x互质,因此x,2x,3x.(p-1)x,px共p个数,这p个数除以p之后余数形成的集合必然是{0,1,2,3.p-2,p-1}.选其中余数为1的项,必然能找出对应的被除数yx,因为yx除以p余数为1.显然xy-1之后一定是p的整倍数,此倍数就正好是k.
所以,一定存在正整数y和k,使得xy=1+kp成立.