题目

数论证明题:证明对任意整数a,b,n,如果n|ab且gcd(a,n)=1,则n|b
这是出现在《算法导论》第31章数论算法的题.

提问时间：2021-03-30

答案

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