关于带余除法的题如图,括号表示最大公约数数论牛人来啊
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/28 06:13:44
关于带余除法的题如图,括号表示最大公约数数论牛人来啊
关于带余除法的题
如图,括号表示最大公约数
数论牛人来啊
关于带余除法的题如图,括号表示最大公约数数论牛人来啊
关于最大公约数有如下性质 （a,b）= （a-nb ,b） ,n是整数,（a,b）=（-a,b）（a,-b）
下面证明该题
左边 = （a^r1 +1 ,a^r2 +1）= ( a^r1 +1 - a^(r1-r2)*(a^r2 +1) ,a^r2 +1 ) =(1 - a^(r1-r2),a^r2 +1) =( a^(r1-r2 )-1,a^r2 +1) 通过上述步骤将 a^r1 变为了 a^(r1-r2 ) ,即a的次数降低了,继续同样步骤
左边 =( a^(r1-r2 )-1,a^r2 +1) = ( a^(r1-r2 )-1 - a^(r1-2r2 )*（a^r2 +1）,a^r2 +1)
=（-1 - a^(r1-2r2 ),a^r2 +1）=（ a^(r1-2r2 )+1,a^r2 +1） 即a^(r1-r2 ) 变为了a^(r1-2r2 )
反复上述步骤可发现 a^r1 +1 变为了 a^(r1-kr2) +(-1)^k ,k是整数
即左边 =（a^r1 +1 ,a^r2 +1） = （ a^(r1-kr2) +(-1)^k ,a^r2 +1）
取k =2*q2 -1 则 r1-kr2 = 2*q2*r2 -r3 -(2*q2 -1 )*r2 = r2-r3 ,(-1)^(2*q2 -1 ) = -1
所以有 左边=（a^r1 +1 ,a^r2 +1）=（ a^(r2-r3) -1 ,a^r2 +1）
然后化简右边
下面证明一下 （a,b）= （a-nb ,a） ,上面说（a,b）= （a-nb ,b）对任意整数n成立 ,但对（a,b）= （a-nb ,a） 只有（n,a）=1时才成立
（1） 设 t 是 a,b的公约数 ,则 t |a,t |b ,所以 t | （a-nb）,又 t |a 所以t 是a-nb ,a 的公约数
（ t |a表示 t 整除a） ,即 a,b的公约数都是a-nb ,a 的公约数
（2） 反过来 设 t 是a-nb ,a 的公约数 ,则 t | （a-nb）,t |a 所以 t |nb ,若（n,a）=1 ,则 t 不整除n ,否则（n,a）=t ,又 t |nb 所以 t |b ,即 t |a,t |b 即 a-nb ,a 的公约数 都是a,b的公约数
由（1）（2）得 a-nb ,a 的所有公约数 与 a,b的所有公约数相同 ,所以 a-nb ,a 的最大公约数 与 a,b的最大公约数相同 ,即（a,b）= （a-nb ,a） （（n,a）=1）
用这个式子化简右边
令 a = a^r2 +1 ,b=a^r3+1 ,n =a^(r2-r3) 现证（n,a）=1 即（a^(r2-r3),a^r2 +1 ）=1
首先证 （a,a^r2 +1 ）=1
假设（a,a^r2 +1 ）=t ,则 t |a ,t |a^r2 +1 ,因为 t |a ,所以t |a^r2 ,所以 t |1
即t =1 ,所以（a,a^r2 +1 ）=1 成立
我们知道若（a,b）=1 则(a^n,b) =1 ,所以由（a,a^r2 +1 ）=1 有（a^(r2-r3),a^r2 +1 ）=1
所以在a = a^r2 +1 ,b=a^r3+1 ,n =a^(r2-r3) 时,（n,a）=1
所以 （a,b）= （a-nb ,a）
即 右边 =（a^r2 +1,a^r3+1）=（a^r2 +1- a^(r2-r3)*（a^r3+1）,a^r2 +1）
=（1- a^(r2-r3),a^r2 +1）=（ a^(r2-r3) -1 ,a^r2 +1） =左边
左边=右边 证毕