# Using Fermat's little theorem

I have this question:

$a \equiv 12^{772} \pmod{71}$, when $0 \leq a < 71$

and I am having troubles getting it started.

$\frac{772}{71}$ is $10$ with a remainder of $62$;

How do I do this question?

-
@infrequentpylon: I edited your question. (Typeset it and added the number theory tag) – user17762 Dec 3 '10 at 1:26

$12^{772}=12^{71\cdot 10+62}\equiv 12^{10+62}=12^{71+1}\equiv 12\cdot 12=144\equiv 2$ mod $71$. So $a=2$.

Alternately,

$12^{772}=12^{70\cdot 11+2}\equiv 12^2=144\equiv 2$ mod $71$.

The first one uses the form $a^p\equiv a$ mod $p$ and the second uses the form $a^{p-1}\equiv 1$ mod $p$ if $gcd(a,p)=1$ where $p$ is prime.

-

HINT $\rm\ \ \ X^N \equiv X\ \ \Rightarrow\ \ X^{A + B\ N + C\ N^2 + \cdots} \equiv\ X^{A + B + C + \cdots}\ (mod\ N)$

NOTE $\$ This is nothing but "casting out orders" - a cyclic group analog of casting out nines. Namely, $\rm\ X^{N-1} = 1\ \Rightarrow\ X^N = X\$ so we can map $\rm\ N\to 1$ when calculating integral powers of $\rm\:X\:$.

When $\rm\:X\:$ has order dividing $\:9\:,\:$ then it amounts precisely to casting out nines from its exponents. For example, $\rm\ mod\ 27:\ (-2)^9 \equiv 1\ \Rightarrow\ (-2)^{721} \equiv -2\ \$ since $\rm\ \ 721\equiv 7+2+1\equiv 1\ \:(mod\ 9)$

-