初等数论中的同余问题
2个回答
展开全部
我提议一下，接力答题。后来者发现前面的已有正确答案，就答其他题目。
我们的目的在于帮助出题人，绝不是为了分数，也最好不要有争分数的心态。
另外，有空的朋友，包括出题人，请将题目用文字打出来，便于后来答题的人引用。
本来我应当把这个题目全敲字，并全部答一遍。但是我还是先提倡一下吧。
题一：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
于是将这个数按三位三位的分节，即可求得余数，或者判定整除性。
此时从左开始分节的话，要注意，最后的数为正，则后面带的因子为正。否则带负因子。
过程A，即首起三位分段求余法：1123456789==(112-345+678)*10+9==4450+9=4459==0 mod 7，即1123456789被7整除。
过程B，即末起三位分段余余法：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.
我们的目的在于帮助出题人，绝不是为了分数，也最好不要有争分数的心态。
另外，有空的朋友，包括出题人，请将题目用文字打出来，便于后来答题的人引用。
本来我应当把这个题目全敲字，并全部答一遍。但是我还是先提倡一下吧。
题一：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
于是将这个数按三位三位的分节，即可求得余数，或者判定整除性。
此时从左开始分节的话，要注意，最后的数为正，则后面带的因子为正。否则带负因子。
过程A，即首起三位分段求余法：1123456789==(112-345+678)*10+9==4450+9=4459==0 mod 7，即1123456789被7整除。
过程B，即末起三位分段余余法：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.
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
|
广告 您可能关注的内容 |
