Question

Use Fermat's Little Theorem to determine 7^542 mod 13.

Answer 1

`a^(p-1) \equiv 1 \pmod p` where
`p` is prime,
`a\in\mathbb{Z}` and
`a` is not divisible by
`p`.

`7^(13-1)\equiv 1 \pmod {13}\\7^(12)\equiv 1 \pmod {13}\\\\542=45\cdot12+2\\\\7^(45\cdot 12)\equiv 1 \pmod {13}\\7^(45\cdot 12+2)\equiv 7^2 \pmod {13}\\7^(542)\equiv 49 \pmod{13}`

Answer 2

49 mod 13 = 10.

Explanation:

Fermat's little theorem states that

x^p = x mod p where p is a prime number.

Note that 542 = 41*13 + 9 so

7^542 = 7^(41*13 + 9) = 7^9 * (7^41))^13

By FLT (7^41)^13 = 7^41 mod 13

So 7^542 = ( 7^9 * 7(41)^13) mod 13

= (7^9 * 7^41) mod 13

= 7^50 mod 13

Now we apply FLT to this:

50 = 3*13 + 11

In a similar method to the above we get

7^50 = (7^11 * (7^3))13) mod 13

= (7^11 * 7^3) mod 13

= (7 * 7^13) mod 13

= ( 7* 7) mod 13

= 49 mod 13

= 10 (answer).