数论证明题:证明对任意整数a,b,n,如果n|ab且gcd(a,n)=1,则n|b
这是出现在《算法导论》第31章数论算法的题.
人气：256 ℃ 时间：2020-06-20 14:57:06
解答
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
推荐
- 数论：证明：二元一次不定方程ax+by=N,的非负整数解为[N/ab]或[N/ab]+1,其中a>0,b>0,(a,b)=1.
- 数论证明整数a,b的最大公约数可以写成gcd(a,b)=sa+tb的形式,s,t为整数,不要辗转相除的逆推次生品,那个我也会,要一种更形式化的证明
- 数论难题a(n)表示前n个正整数的最小共倍数,证明a(n)>=2^(n-1)
- 数论中,若a,b是整数,证明 (a,b)=(a+b,b).
- 设n为正整数,证明：6 | n(n + 1)(2n +1).
- dutch 到底是德国还是荷兰?
- 先观察有什么规律,填写空格-1,1,0,1,1,2,( ),5,
- 急死啦,英语词
猜你喜欢
