# Using Fermat's Little Theorem to compute vast numbers

I was given a how problem set with the following problems to solve (I'm allowed to use a calculator for all operations excluding exponentiation):

$3^{23} + 3 ≡ 5^{37} − 4 \pmod 7$

$1,000,001^{999,999} ≡ 1 \pmod {1, 000, 000}$

...I know Fermat's Little Theorem should help me manipulate even these vast numbers, but I don't know where or how to begin. For the second one, should I start with a much smaller number, like $1,000,001 ≡ 1 \pmod {1,000,000}$? (That should hold, right?)

• You should begin with Fermat's little theorem in the case of $3^{23}$ and the prime $p=7$. What does it tell you ? – Dietrich Burde Jul 7 '16 at 14:59
• For the second one, what you stated is true. Now, if you raise both sides to any power... – Some Math Student Jul 7 '16 at 15:00
• Alternatively, use the binomial theorem to unfold $(1+10^6)^{999999}$. All but the first term are multiples of $10^6$. – Henning Makholm Jul 7 '16 at 15:02

You should learn some basic rules for congruences before you proceed with Fermat's Theorem.

Firstly,

• Congruences with same modulo n are- $1.$Reflexive,$2.$Symmetric and $3.$ Transitive.

This simply means congruences with same modulo can be added,subtracted and multiplied to give new congruences.

For eg, $2^2\equiv1\pmod3$ and $4^2\equiv1\pmod3$.

This implies,

1.$2^2+4^2\equiv(1+1)\pmod3$

2.$2^2\times2^2\equiv(1\times1)\pmod3$

Similarly they can also be subtracted.

See,from them product rule of congruences,we see that if $a\equiv b\pmod c$ then,$a^n\equiv b^n\pmod c$.

So,if $1000001\equiv1\pmod{1000000}$ then $1000001^n\equiv1^n\pmod{1000000}$.For your question,$n=999,999$.

Hint for your second first part-

$3^{7-1}\equiv1\pmod7$ (By,Fermat's Little Theorem)

$\implies3^{23}\equiv3^5\pmod7$

$\implies3^{23}\equiv5\pmod7$

Also, we see,$3\equiv{-4}\pmod7$

Adding the congruences,$3^{23}+3\equiv5+(-4)\pmod7$.

Now,try to find out why the $5^{37}$.

Hint: Modulo 7, $$3^{23}\equiv3^{21}3^{2}\equiv(3^{7})^{3}3^{2}\equiv3^{3}3^{2}\equiv3\cdot3^{2}3^{2}\equiv3\cdot2\cdot2\equiv-1\cdot2\equiv-2\equiv5.$$ You should be able to use similar manipulations on these types of problems.

\begin{align} & {{3}^{6}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{3}^{18}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{3}^{23}}\overset{7}{\mathop{\equiv }}\,243\,\,\Rightarrow {{3}^{23}}+3\overset{7}{\mathop{\equiv }}\,246\,\overset{7}{\mathop{\equiv }}\,1 \\ & {{5}^{6}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{5}^{36}}\overset{7}{\mathop{\equiv }}\,1\,\,\,\Rightarrow \,\,\,{{5}^{37}}\overset{7}{\mathop{\equiv }}\,5\,\,\Rightarrow {{5}^{37}}-4\overset{7}{\mathop{\equiv }}\,1\,\,\,\,\,\,\, \\ \end{align} then $${{3}^{23}}+3\overset{7}{\mathop{\equiv }}\,{{5}^{37}}-4$$ $${{({{10}^{6}}+1)}^{999999}}=\sum\limits_{i=0}^{999999}{\left( \begin{matrix} 999999 \\ i \\ \end{matrix} \right)}{{({{10}^{6}})}^{999999-i}}\,\overset{{{10}^{6}}}{\mathop{\equiv }}\,1\,\,\,\,$$

• Isn't your method too complex? – tatan Jul 7 '16 at 15:05