证明等式gcd(m,n)=gcd(n mod m,m),对每对正整数m和n,m>0都成立.这是算法设计与分析上的题.求大神帮忙
人气:373 ℃ 时间:2020-05-19 08:08:40
解答
这是用辗转相除法求两个数的最大公约数
原理:
如果 n=bm+r
则 (n,m)=(m,r)
gcd(m,n)求的是 m与n的最大公约数
n mod m是n除以m的余数
所以有 gcd(m,n)=gcd(n mod m,m)
如果还是不明白,请搜索“辗转相除法"
推荐
- 设m>1,x,y和g都是正整数,且gcd(g,m)=1.如果x ≡y(modφ(m)),求证gx ≡gy(mod m).
- 根据gcd(2^2^m 2^2^n)=1证明质数有无穷多个
- 如何证明gcd(a,b)=gcd(a,a+b)
- 证明 x^b = x mod p 的解的个数是 gcd(b-1,p-1).
- Public Function gcd() dim m%,n% Do r = m Mod n m = n n = r Loop Until r = 0 gcd = m End Function
- 春风和煦的诗句
- 甲、乙两人在同一条路上前进,甲每小时5km,乙每小时行7km,甲于中午12点时经过A地,乙于下午2点经过A地,
- x:8=0.2::1/2过程啊啊啊啊啊啊啊啊啊啊啊
猜你喜欢