已知： $gcd(a,m)=1$

求证： $gcd(a+km,m)=1,\ (k\in \mathbb{Z})$

证明：

反证法：
设 $gcd(a+km,m)=d\neq 1$，
则 $a+km=qd,m=pd$，
所以 $a+kpd=qd$，
所以 $a=qd-kpd=d(q-kp)$，
所以 $gcd(a,m)\ge d\neq 1$，与已知矛盾，
故 $gcd(a+km,m)=1$，得证