# Fermat's Little Theorem Problem

How can we use Fermat's Little Theorm to find the least non-negative residue modulo m with numbers with large exponents. For example, how would one find the least non-negative residue modulo m with values $n = 3^{1000000}$ and $m = 19$.

I understand how the basic method works (ie finding a way to introduce a factor of $3^{18}$ and then reducing), but dividing 1000000 by 18 is time consuming and I feel there is a quicker method that I don't understand yet.

-

In fact, finding the remainder of $10^6$ by $18$ is not really that tough

Observe that $10^{n+1}-10=10(10^n-1)$ is divisible by $10\cdot 9=90,$ as $9\mid(10^n-1)$ for $n\ge1$

Hence $18\mid(10^{n+1}-10)\implies 10^{n+1}\equiv10\pmod{18}$ for $n\ge1$

So, $$3^{10^n}\equiv3^{10}\pmod {19} \text{ for } n\ge1$$

-
As $(a-b)\mid(a^n-b^n)$ where $a,b,n$ are positive integers, $(10-1)\mid(10^n-1)$ –  lab bhattacharjee Feb 10 '13 at 6:41
How did you jump from mod 18 to mod 19, that's the step I don't really understand. –  Math_Illiterate Feb 10 '13 at 7:33
@Ockham, for prime $p$ and $(x,p)=1,$ if $a\equiv b\pmod {p-1},$ i.e., $a=c(p-1)+b$ for some integer $c, x^a=x^{c(p-1)+b}=(x^{p-1})^c\cdot x^b\equiv x^b\pmod p$ as $x^{p-1}\equiv1\pmod p$ –  lab bhattacharjee Feb 10 '13 at 8:41
Wish I know the mistake here that has caused the down vote –  lab bhattacharjee Aug 16 '14 at 14:39

$$3^{18}\equiv 1 \text{ mod 19}$$ $$3^{18*55555}\equiv 1 \text{ mod 19}$$ $$3^{999990}\equiv 1\text{ mod 19}$$ $$3^{1000000}\equiv 3^{10} \text{ mod 19}$$ $$3^{1000000}\equiv 16\text{ mod 19}$$

-
can you explain a little more about what you did at each step? –  Math_Illiterate Feb 10 '13 at 6:28
$a^b\equiv c\implies (a^b)^d\equiv c^d \implies a^{bd}\equiv c^d,$ not $a^{b^d}\equiv c^d$ –  lab bhattacharjee Feb 10 '13 at 6:28
So the steps listed above are not correct? –  Math_Illiterate Feb 10 '13 at 6:31
I don't think this result is correct. According to wolfram alpha $3^{10^6} \equiv 7 \space \text{mod} \space 19$ does not hold. –  Math_Illiterate Feb 10 '13 at 6:44
@Ockham I fixed it, sorry for errors. –  Ethan Feb 10 '13 at 6:58

Hint $\rm\ mod\ 9\!:\, 10^6\equiv 1^6\equiv 1,\,\ mod\ 2\!:\, 10^6\equiv 0,\$ so $\rm\ mod\ 18\!:\, 10^6\equiv 10,\,$ so $\rm\,mod\ 19\!:\ 3^{10^6}\!\equiv 3^{10}$

Alternatively  we may employ Euler's Criterion and quadratic reciprocity:

$$\rm\quad mod\ 19\!:\,\ \color{#C00}{3^9} \equiv \left(\frac{3}{19}\right) \equiv\, -\left(\frac{19}{3}\right)\equiv\, -\left(\frac{1}{3}\right)\equiv\,\color{#C00}{-1}$$

$\rm 10^6\!-1 = 9k,\ k\ odd,\,$ so $\rm\, mod\ 19\!:\ 3^{10^6} = 3^{1+9k} =\, 3 (\color{#C00}{3^9})^k\equiv 3 (\color{#C00}{-1})^k\equiv -3$

-
I assume your using some theorem that allows you to multiply mod values, can you tell me the name of the theorem or give a little explanation as to how this whole thing works –  Math_Illiterate Feb 10 '13 at 6:40
$\rm mod\ 9\!: 10^6\equiv 1,\:$ so $\rm\:mod\ 18\!: 10^6\equiv 1\ \ or\ \ 1+9=10.\:$ Since $\rm\,10^6\,$ is even, it must be $10.\:$ Generally one can use CRT (Chinese Remainder), but that'd be overkill here. –  Math Gems Feb 10 '13 at 6:50
@MathGems It was overkill once you started adding colors lol –  Ethan Feb 10 '13 at 7:16
@Ethan The colors greatly aid the reader to follow the structure of the inferences. E.g. when I wrote equational inferences like above in older systems without such highlight capabilities, I often received questions, e.g. why is the penultimate congruence true? With it and its source both highlighted in red, one easily sees that it is an application of the replacement rule $\rm\: a\equiv b\:\Rightarrow\:f(a)\equiv f(b),\:$ where $\rm\:f(n) = 3n^k,\:$ and $\rm\,a= 3^9,\,b= -1.\ \$ In more complex proofs, this structure may be much less clear. –  Math Gems Feb 10 '13 at 16:27

Modular arithmetic makes this easy.

To find 1000000 modulo 18, we can first find 100000 modulo 18, and then multiply by 10 and reduce modulo 18 again.

To find 100000 modulo 18, we can first find 10000 modulo 18, and then multiply by 10 and reduce modulo 18 again.

To find 10000 modulo 18....

-