1.设p = 23和a = 5，使用费尔马小定理计算a^{2020} mod p?

5 2020 ^{2020} 2020 ≡ \equiv ≡ 5 91 × 22 + 18 ^{91\times22+18} 91×22+18 ( m o d 23 ) \pmod{23} (mod23) 因为91 × \times × 22=92 × \times × (23-1)，所以5 91 × 22 + 18 ^{91\times22+18} 91×22+18 ≡ \equiv ≡ 5 18 ^{18} 18 ( m o d 23 ) \pmod{23} (mod23)。 5 2 ^2 2 mod 23=2 5 4 ^4 4 mod 23=2 × \times × 2 mod 23=4 5 9 ^9 9 mod 23=5 × \times × 4 × \times × 4 mod 23=11 5 18 ^{18} 18 mod 23=11 × \times × 11 mod 23=6 因此结果为6。

使用欧拉定理计算2^{100000} mod 55。

5和11互素，因此 Φ \Phi Φ(5 × \times × 11)= Φ \Phi Φ(5) × \times × Φ \Phi Φ(10)=4 × \times × 10=40= Φ \Phi Φ(55)。 2 100000 ^{100000} 100000 ≡ \equiv ≡ 2 2500 × 40 ^{2500\times40} 2500×40 ( m o d 55 ) \pmod{55} (mod55) 因为2500 × \times × 40=2500 × \times × Φ \Phi Φ(55)，所以2 100000 ^{100000} 100000 ≡ \equiv ≡ 2 0 ^0 0 ( m o d 55 ) \pmod{55} (mod55)=2

3.手动计算7^{1000}的最后两个数位等于什么？

7 1000 ^{1000} 1000 ≡ \equiv ≡ 7 10 × 99 + 10 ^{10\times99+10} 10×99+10 ( m o d 100 ) \pmod{100} (mod100) 因为 10 × 99 = 10 × ( 100 − 1 ) 10\times99=10\times(100-1) 10×99=10×(100−1)，所以7 10 × 99 + 10 ^{10\times99+10} 10×99+10 ≡ \equiv ≡ 7 10 ^{10} 10 ( m o d 100 ) \pmod{100} (mod100)。 7 2 ^2 2 mod 100=49 7 5 ^5 5 mod 100=7 × \times × 49 × \times × 49 mod 100=7 7 1 0 ^10 10 mod 100=7 × \times × 7 mod 100=49 因此结果为49，十位为4，个位为9。