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

Answer:

49 mod 13 = 10.

Step-by-step 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).