若(a,m)=1,b≡a( mod n),证明(b,m)= 1.

假设(b,m)≠1，则(b,m)=k(k>1)，则m=kp，b=kq，其中p,q为正整数且(k,p)=1。

由题意得b≡a(mod n)，即kq≡ak(mod n)。

因为(a,m)=1，所以a与m互质，即存在整数x、y，使得ax+my=1。

将上式两边同乘k，得akx+mky=k。

因为kq≡ak(mod n)，所以存在整数t，使得kq=ak+tn，即kq-ak=tn。

将上式代入akx+mky=k，得ak(x+tq)+mky=1。

因为(x+tq)、y为整数，且(a,m)=1，所以(b,m)=1，与(b,m)≠1矛盾。

因此，假设不成立，即(b,m)=1。

相关问题

设(G,*)=(a)是n阶循环群,b=ak,kZ,证明 元素b是群G的生成元素,当且仅当n和k互素 （提示：若n与k互素，则存在整数p与q，使得pn+qk=1）

证明：

首先，如果n和k不互质，则存在正整数d使得n=md，k=nd，其中m和d均为正整数。那么b=ak=(a^d)^m，即b是(a^d)的m次幂，因此b不能是群G的生成元素。

接下来，假设n和k互质，我们要证明b是群G的生成元素。由于n阶循环群G中有且仅有n个元素，因此b的阶必定是n。也就是说，对于任意正整数m，b^m≠e（其中e表示G中的单位元素），否则b的阶不可能是n。

接下来，我们需要证明，对于任意元素a^i（i=1,2,...,n-1），都可以表示成b的幂次。考虑使用反证法，假设存在某个元素a^i不能表示成b的幂次。由于a^i是G的一个元素，因此它肯定属于某个子群H=<a^d>（其中d=gcd(i,n)），那么H的阶为n/d。又因为b是G的一个元素，因此b也属于H，而且b的阶为n。因此，存在正整数x和y，使得b^n=(a^d)^x，a^i=(a^d)^y。根据提示，由于n和k互质，存在整数p和q，使得pn+qk=1。那么有：

(a^d)^y = a^i = a^(qn+pd)y = (a^q)^n^y * (a^d)^p^y

因此，我们可以得到：

(a^q)^n^y = (a^d)^(y-p^yn)

因为a和a^q都是G中的元素，所以它们的阶都是n。因此，左右两边都是n阶元素的n次幂，它们相等当且仅当它们相等的阶是n。因此，我们可以得出：

y-p^yn ≡ 0 (mod n)

由于p和q的存在，我们可以得到：

pn+qk=1

qn ≡ 1 (mod n)

因此，存在正整数y'，使得y=yn'+d。将其代入上面的式子中，我们可以得到：

yn' ≡ -p^yn' (mod n/d)

因为n和k互质，所以n和n/d也互质，因此我们可以将上式两边同时乘以p^n'y'，得到：

(p^n'y')(yn'+1) ≡ 0 (mod n/d)

因为p和n/d互质，所以p^n'y'和yn'+1也互质。因此，我们可以得到：

yn'+1 ≡ 0 (mod n/d)

这意味着d|1，即d=1，而i和n互质，因此i和k也互质。因此，我们可以得到：

b^m = b^(mx+ny) = (a^k)^x * (a^n)^y = a^(kx+ny)

因此，任意元素a^i都可以表示成b的幂次，因此b是群G的生成元素。