数论证明题:证明对任意整数a,b,n,如果n|ab且gcd(a,n)=1,则n|b
问题描述:
数论证明题:证明对任意整数a,b,n,如果n|ab且gcd(a,n)=1,则n|b
这是出现在《算法导论》第31章数论算法的题.
答
n|ab 推出 存在 K,使得 ab=nK;
gcd(a,n)=1 推出 存在 u,v,使得 ua+vn=1;
对上式两端同时乘以b,有
uab+vnb=b;
代入第一式有:unK+vnb=b;
即 n(uK+vb)=b
所以 n|b