Expert: Paul Klarreich - 7/22/2006

Question
Hi. Im revising for exams but Ive no idea how to do this question:

Calculate 71^36 (mod 19)

Im pretty sure it isnt as simple as typing 71^36 into calculator. Thanks! :)

Answer
Hi, Eoin,

You must tell me what subject you are studying.  There is something in the subject of number theory regarding an expression of the form:

71^18 (mod 19)

as an instance of

a^(p-1) mod p,

where p is prime.

Let me know as soon as possible.
=====================================
Eoin Asks in Category Advanced Math ...
 
Subject:  Calculation with mod
Private:  no
Question:  Hi. Im revising for exams but Ive no idea how to do this question:

Calculate 71^36 (mod 19)

Im pretty sure it isnt as simple as typing 71^36 into calculator. Thanks! :)
-------------------------------------------
Well, here is the solution, in case you can make use of it, IF YOU ARE STUDYING NUMBER THEORY.

There is a theorem, commonly known as Fermat's theorem (no, not Fermat's Last Theorem) that says:

If p is prime and p does not divide a, then

a^(p-1) mod p = 1

Now 19 is prime and 19 does not divide 71, so that means

71^18 mod 19 = 1

Then 71^36 mod 19 = (71^18 mod 19)^2 = 1^2 = 1.