Question

初等数论问题？？？

若（a，b）=1，则对任意整数C，存在x使得（a+b*x，C）=1。

Answer 1

解：
当(b,C)≠1时，
设(b,C)=d，C=c*d，
则(a,d)=1且b/d为整数
故(a+b*x,C)=(a+d*(b/d)*x,c*d)=(a+b*x,c)
如此重复，必有c使(b,c)=1且(a+b*x,C)=(a+b*x,c)
而此时a+b*x≡a+b*y(mod c)当且仅当x≡y(mod c)
x从0取到c-1，a+b*x模c的值各不相同，此时必有一个x满足a+b*x≡1(mod c)，
故存在x使c|a+b*x-1，即(a+b*x,c)=1
故存在x使(a+b*x,C)=(a+b*x,c)=1