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.
 A: $$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}$$
A: 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$
A: 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$$
A: 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....
