作业帮 > 数学 > 作业

数论证明题:证明对任意整数a,b,n,如果n|ab且gcd(a,n)=1,则n|b

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/04/29 19:39:50
数论证明题:证明对任意整数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|