Question

急，大学初等数论关于同余的问题！

已知ab≡-1（mod24），证明24|（a+b）
解：ab≡-1（mod24）得ab≡-1（mod3）
若a≡-1（mod3）则b≡1（mod3）
若a≡1（mod3）则b≡-1（mod3）
同样有ab≡-1（mod8）
若a≡±1（mod8）则b≡∓1（mod8）
若a=±3（mod8）则3ab≡-3（mod8），即±b≡-3（mod8） b≡∓3（mod8）
请问这些若是怎么的出来的 尤其是最后一个若 3是哪来的 3ab又是怎么来的
谢谢！！！

Answer 1

A为十进制数n=4568^7777的各位数字之和，B为A的各位数字之和，C为B的个位数字之和，C=（）
A.5 B.32 C.9 D.14

先用一个任意的三位数w=100x+10y+z说明一个引理.
w的各位数字之和是:w1=x+y+z.
可以看到,w==w1 mod 9
于是排除答案C
以上说明的是：
引理1:
数n=ar...a2a1a0,其数字和为S(n),则
n==S(n)mod 9.即 9|n-S(n)

引理2
正整数n的十进制位数:b(n)=1+[lgn]。
例如：10的位数是2,lg10=1; 99的位数是2,lg99<2

由此立即得到
引理3:
正整数n的十进制表示的各位数字之和S(n)<=9(1+[lgn])。

解：
记n的各位数字和为S(n)
取n=4568^7777
A=S(n)<=9*(1+7777*lg4568)<9*(1+7777*4)=9*31109=279981
从而B=S(A)<=2+9*5-1=46
从而C=S(B)<=4+9-1=12
由此可以在四个答案A.5 B.32 C.9 D.14中，
只有A,C候选。

又
易见以下各数除以9的余数相等
n,A,B,C
（数论上讲：n==A mod 9,n与A关于除数(模)9同余）
显然
n==4568^7777==5^7777>0 mod 9
由此可以排除答案C
综上，选A

附记：
n==4568^7777 mod 9 == 5^(7777 mod 6) mod 9== 5^1==5
这里利用到
若（a,m）=1,m不整除r,则a^r mod m == a^(r mod φ(m)) mod m,
其中φ(m)为m的欧拉函数,即m的既约剩余系中的同余类的个数，也就是小于m的正整数中与m互质的数的个数。
φ(9)=6.

如果不利用欧拉函数，仅利用同余知识，可以写成：
n==4568^7777 mod 9 == 5^7777==125^2592*5==(-1)^2592*5==5 mod 9

Answer 2

注意ab≡-1 (mod 8)说明a和b中任何一个，如a 应该满足a≡奇数 (mod 8)，从而只有a≡±1或±3 （mod 8）；
至于第二个问题，注意到此时的前提：ab≡-1 (mod 8)，两边同乘以3即可得3ab≡-3 (mod 8).

追问

你好 请问下 注意ab≡-1 (mod 8)说明a和b中任何一个，如a 应该满足a≡奇数 (mod 8)

a≡奇数是怎么得到的

追答

如果a,b中存在偶数，则ab也为偶数，从而ab不可能为8k-1的形式，即不可能有ab≡-1 (mod 8).

追问

哦哦 好像是喔
那3ab≡-3（mod8），怎么得出±b≡-3（mod8） b≡∓3（mod8） 再次麻烦了。。

追答

a=±3（mod8）得3a≡±9 （mod8），即3a≡±1 （mod8），然后在所有b模8的同余类里，
只有b≡∓3（mod8）才能满足3ab≡-3（mod8），这个 可以枚举验证的。
b模8的同余类有7类：
b≡±3（mod8） b≡±2（mod8） b≡±1（mod8） b≡0（mod8） b≡4（mod8）

Answer 3

已知ab≡-1（mod 24），证明：24|(a+b)。
证明：
因为：ab≡-1（mod 24），24=3x8
所以：ab≡-1（mod 3）、ab≡-1（mod 8）
1，由ab≡-1（mod 3）得：
a），当a≡1时，b≡-1，a+b≡0（mod 3）
b），当a≡-1时，b≡1，a+b≡0（mod 3）
所以：a+b≡0（mod 3）……①
2，由ab≡-1（mod 8）得：
a），当a≡1时，b≡-1，a+b≡0（mod 8）
b），当a≡-1时，b≡1，a+b≡0（mod 8）
所以：a+b≡0（mod 8）……②
由①，②知：a+b≡0（mod 24）
即：24|(a+b)

追问

你好 mod8的时候还有个a=±3（mod8）则3ab≡-3（mod8），即±b≡-3（mod8） b≡∓3（mod8） 主要是这个不太清楚

追答

1，我的证明，还要补充：“3和8互质”；
2，我的证明不涉及你提的疑问；
3，你的疑问也是我的疑问：
由ab≡-1（mod 8），可以推出：
a），当a≡1时，b≡-1，a+b≡0（mod 8）
b），当a≡-1时，b≡1，a+b≡0（mod 8）
若：a≡±3，则b≡多少，才能满足：ab≡-1（mod 8）！？
你的是标准答案么？

追问

绝对标准 书上原文 我只是最后a+b≡0（mod 24）的几步没写 因为这个加法懂
就是mod8的时候还有个a=±3（mod8）则3ab≡-3（mod8），即±b≡-3（mod8） b≡∓3（mod8）这个不懂+_+

追答

Sorry！我也看不明白。