Question

大学初等数论的问题!

1、 证明：70！≡61！（mod 71）
2、 求3的100次方的模10的余数
3、 求3的50次方的十进制数表示中最末的两位数

Answer 1

1、 证明：70！≡61！（mod 71）
解：引理：ac==bc mod m,(c,m)=1,则a==b.证略。
依引理，只须证70!/61!==1 mod 71
即 70*69*...62==-1*-2*...*-9==-9!==-362880==1，显然。
2、 求3的100次方的模10的余数
解：引理：(a,m)=1,则a^φ（m）==1 mod m.证略。
由于3^φ（10）==1mod 10,即3^4==1
故3^100==1
3、 求3的50次方的十进制数表示中最末的两位数
同上理，3^25==1 mod 100
故3^50==1
即其十进表示最末二位数为01