Can some1 please help me with this

made another mistake its

please help me solve the following without using a calculator

9^7 mod 143 oops!! :confused:

thanks

Printable View

- Apr 10th 2006, 03:51 PMdarren_a1Eulers theorem
Can some1 please help me with this

made another mistake its

please help me solve the following without using a calculator

9^7 mod 143 oops!! :confused:

thanks - Apr 12th 2006, 10:50 PMrgep
Note that 143 = 11.13 so we do it by the Chinese Remainder Theorem, and use Fermat's Little Theorem.

Modulo 11: 9^7 == (3^2)^7 == 3^14 == 3^10.3^4 == 1.3^4 == 81 == 4

Modulo 13: 9^7 == (3^2)^7 == 3^14 == 3^12.3^2 == 1.3^2 == 9

Now to reconstruct the answer. 6.11 - 5.13 = 1 by Euclid's algorithm. So

6.11.a - 5.13.b is == a mod 13 and == b mod 11. The answer is thus 6.11.9 - 5.13.4 == 594 - 260 == 334 == 48 mod 143.

Answer: 48.