初等数论中的同余问题

初等数论中的同余问题
初等数论中的同余问题

初等数论中的同余问题
我提议一下,接力答题.后来者发现前面的已有正确答案,就答其他题目.
我们的目的在于帮助出题人,绝不是为了分数,也最好不要有争分数的心态.
另外,有空的朋友,包括出题人,请将题目用文字打出来,便于后来答题的人引用.
本来我应当把这个题目全敲字,并全部答一遍.但是我还是先提倡一下吧.
题一：s=1^5+2^5+...+1990^5 mod 3
易见对于任意整数a,a^(2N+1)==a mod 3 (见注释)
故s mod 3== 1+2+3+...+1990 ==1990*1991/2 ==1*2 /2 ==1 mod 3 (此处利用到了分数形式的求余.见后文“洪伯阳同余表示”之说明.）
常规形式：s mod 3== 1+2+3+...+1990 ==1990*1991/2 =995*1991==2*2 ==1 mod 3
即答案为s==1 mod 3
注释：由欧拉缩系计数函数定理或费马小定理,或直接验证,可知,当
a==1或2 mod 3时,a^2==1 mod 3
故 对于任意整数,a^(2n+1) ==a mod 3.
题二：数a的十进制表示写成a=(a[n-1],a[n-2],...,a[1],a[0]),问它被7整除的条件.
并说明1123456789能否被7整除.
题二解一A,B：三位分段求余法：推荐!
已知1001=7*11*13,故10^3==-1 mod 7
于是将这个数按三位三位的分节,即可求得余数,或者判定整除性.
此时从左开始分节的话,要注意,最后的数为正,则后面带的因子为正.否则带负因子.
即首起三位分段求余法：1123456789==(112-345+678)*10+9==4450+9=4459==0 mod 7,即1123456789被7整除.
即末起三位分段余余法：1123456789==(1-123+456-789)*(-1)==(1-123-333)*(-1)=455==0 mod 7
一般的推广略去.
题二解二：首起逐位求余法.这种方式不推荐.
原理：10a+b==3a+b mod 7
于是1123456789 mod 7==423456789==3456789==1356789==656789==256789
这种方式和逐位心算做除法一样,我们一般熟记九九乘法表,对两位数求余数是非常熟悉的,因此这样还不如直接按两位两位的心算做除法.
题二解三：首起两位分段求余法.推荐!
首先在心中两位分节成11,23,45,67,89,于是
1123456789==4,02,03,04,05 mod 7
再根据 100a+b==2a+b mod 7
于是402030405==10030405==230405==5005==105==0 mod 7
这种方法比较利于心算.还可以结合1001k==0 mod 7简化上面的过程：
1123456789==4,02,03,04,05 mod 7==10030405==20405==5005==0 mod 7
题二解四：尾起逐位求余法,即割尾求余法.这种求余法要利用分数表示求余数.
如果只用此法判定整除性,则可简化.
分数z=x/y mod m等价于 yz==x mod m.这种表示我常称为洪伯阳同余表示.百度搜索 wsktuuytyh 洪伯阳同余表示,可以找到很多相关资料.近来有一些数论教材上也开始比较正式的用这种表示,这种方法可能会流行开来.
原理：10a+b==(a-2b)(-1/2) mod 7==-a/2+b mod 7
如果不用求余数,只用判定整数性,只需利用：
10a+b==0 mod 7 等效于 a-2b==0 或-a/2+b ==0 即可.
题三：n为整数,求证13|(4^(2n+1)+3^(n+2)),我也提倡写成：(4^(2n+1)+3^(n+2)) |：13
或者说4^(2n+1)+3^(n+2)==0 mod 13
请朋友们包括出题人,将题目用文字打出来,便于后来答题的人引用.或者继续答题吧.原谅我没再继续了.
题六：今天是星期四,问10的10次方 天后的那一天是星期几
题六解一：即求 4+10^10除以7的余数.
易见1001=7*11*13,即10^3=1000==-1 mod 7
故10^10=(10^3)^3*10==(-1)*10==-10 mod 7
故4+10^10==4-10=-6==1 mod 7
即所求为星期一
题六解二：
易见1000+1==0 mod 7,故10^6-1=(100+1)(1000-1) =0 mod 7
或者直接得到10^6==1 mod 7
故10^10=(10^6)*10^4== 100^2 ==2^2=4 mod 7
于是 4+10^10==4+4==1
即所求为星期一.
题五提示：
方法一：利用二项式定理.
(100a+b)^n mod 100 ==b^n mod 100
(10a+b)^n mod 100 ==b^n+n*b^(n-1)*10a mod 100
方法二：利用由欧拉缩系计数函数定理
a与25互质时,即a与5互质时,
a^(20m+n)==a^n mod 25
注意,此时也可以利用二项式定理求(5a+b)^n mod 25.
先求原数 mod 25 及原数 mod 2,再反求原数 mod 50.
另有些细节,略去.
题七：求7^(9^(9^9)) mod 100
提示：可先求7^(9^(9^9)) mod 25,及7^(9^(9^9)) mod 4,再用中国剩余定理求解.
与题五类似.略.注意其中用到9^(9^9) =20k+r,并且7^20 ==1 mod 25.

10^10同余（10^3）x（10^3）x（10^3）x10同余6x6x6x4同余1x1x1x3同余-3（mod7）
所以为星期五