如何证明 若gcd(a,m) =1,gcd(b,m) =1,则 gcd(ab,m)=1

Rt

Rt

Rt

容我先去百度一下gcd

这是数论的基本结论吧。。用那个定理（名字忘了。。）
(a,b)=1,则有am+bn=1.反之也成立（好像是这样的）

gcd(a,m)=gcd(a*gcd(b,m),m)=gcd(gcd(ab,am),m)=gcd(ab,gcd(am,m))=gcd(ab,m)

看看欧拉定理能不能用，有强烈的感觉可以

这不是显然的吗

蒟蒻表示看不懂9楼的做法
我这边提供一种证法吧
引理1欧几里得算法: ∀a,b∈N,b≠0,gcd(a,b) = gcd(b,a%b);
证明:
若b>a,则a%b = a,则gcd(b,a%b) = gcd(b,a)则引理显然成立
若b<=a,设a = q*b+r,其中0≤r<b,显然r = a%b。对于a,b的任意公约数d。因为d|a,d|q*b,所以d|(a-qb)
(a = dk,qb = dk',所以 a-qb = d(k-k')显然d|(a-qb))所以d|(a-qb) = d|r,所以d也是b,r的公约数,所以b,a%b的公约数集合相同
因此gcd(a,b) = gcd(b,a%b);
证毕
定理:若gcd(x,m)=1,gcd(y,m)=1,则gcd(x*y%m,m)=1;
证明:
想想gcd(x,m)=1的条件是什么,x,m分解质因数完x,m的质因数集合没有相同的子集,y与m也一样。所以x*y一定与m互质
即gcd(x*y,m)=1。由欧几里得算法可得:gcd(x*y,m) = gcd(m,x*y%m) = 1;
证毕