7 Use Fermats Little Theorem to show that Solutiona Accordin

7. Use Fermats Little Theorem to show that

Solution

a) According to Fermat\'s theorem

a^(p-1) = 1 mod(p)

Since 11 is an prime number, Hence we can write

a^(11-1) = 1 mod(11)

=> a^(10) = 1 mod 11

Now in the above case is valid for any value of a which is coprime with 11

2^(10) = 1 mod 11

Coming back to the question, we need to prove 2^(340) = 1 (mod 11)

2^(340) = 2^(10) * 2^(10) * ..... * 2^(10) [34 times]

[2^(10) mod (11) * 2^(10) mod 11 * ..... * 2^(10) mod 11 (34 times] mod 11

1 mod 11

Hence 2^(340) = 1 mod(11)

b) According to Fermat\'s theorem

a^(p-1) = 1 mod(p)

Since 31 is an prime number, Hence we can write

a^(31-1) = 1 mod(31)

=> a^(30) = 1 mod 31

Now in the above case is valid for any value of a which is coprime with 31

2^(30) = 1 mod 31

Coming back to the question, we need to prove 2^(340) = 1 (mod 31)

2^(340) = 2^(30) * 2^(30) * ..... * 2^(30) [11 times] * 2^(10)

[2^(30) mod (31) * 2^(30) mod 31 * ..... * 2^(30) mod 31 (11 times] mod 31 * 2^(10) mod 11

1 mod 31

Hence 2^(340) = 1 mod(31)