Question

初等数论同余问题：

A为十进制数4568^7777的个位数字之和，B为A的各位数字之和，C为B的个位数字之和，C=（）
A.5 B.32 C.9 D.14
（题很有趣吧，不要奢望用计算器呦）
不是个位数字，是各位数字

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

解：A<=lg(4568^7777)*9<4*7777*9=279972
B<1+9*5=46,C<3+9=12
又9|4568^7777-C,4568^7777≡5^7777≡5*5^7776≡5*10^3888≡5(mod9),故C≡5（mod9）C=5

Answer 3

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