Modular exponentiation and Fermat's little theory

Question

 

Calculate 314^163 mod 7 by using:

 

a) Modular exponentiation

b) Fermat's little theory

Answer 1

By Fermat's Little Theorem, we know that if a is coprime with p, then a^p-1 ≡ 1 (mod p). We can use this to simplify our calculation as follows:

1. Check if 314 and 7 are coprime, meaning they share no factors.
2. 7 is a prime number.
3. 314 = 2 * 157, and 157 is prime.
4. Therefore 314 is coprime with 7.
5. Therefore, we can deduce that 314⁶ ≡ 1 (mod 7).
6. Next we will use the properties of modular exponentiation to make this simpler.
7. We know the identity (a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m, therefore we can deduce that a^xy mod m = ((a^x mod m)(a^y mod m)) mod m.
8. Since we know 314^6 ≡ 1 (mod 7), we will want to use this to simplify the calculation.
9. 163 = (27*6) + 1
10. Therefore 314¹⁶³ = (314⁶)²⁷* 314¹
11. Next we apply this:
12. (314⁶)²⁷* 314¹ ≡ 1²⁷*314 (mod 7)
13. 1²⁷*314 (mod 7) ≡ 1*314 ≡ 314 (mod 7)
14. 314 = 44*7 + 6, therefore 314 ≡ 6 (mod 7)
15. Therefore, 314¹⁶³ ≡ 6 (mod 7)