# What am I doing wrong in congruences

Find the remainder of the division of $1990^{21}$ with $21$.

By Fermat Little Theorem, $1990^{20}\equiv 1\pmod{21}$.

So, $(1990^{20})^{99} \cdot1990^{11} \equiv 1990^{11} \mod{21}$.

We know that $1990=94 \cdot 21 + 16$, therefore $1990 \equiv 16$. So we now want to solve $16^{11} \equiv \pmod{21}$.

We also can understand that:

$16 \equiv -5 \pmod{21}$

$16^{2} \equiv 4\pmod{21}$

If I write $16^{11}=(16^2)^5\cdot16 \equiv 4^5\cdot16\pmod{21}$. Now I can solve with a scientific calculator and manually get the remainder that is $4$.

But If I write $16^{11}\equiv(-5)^{11}\pmod{21}$, I can also solve this with a scientific calculator manually, but the remainder is $17$, not $4$. What is wrong?

• $3\cdot7=21$ is not a prime, so you cannot use Little Fermat that way. The totient function is $\phi(21)=(3-1)\cdot(7-1)=12$, so if $a$ is coprime to $21$ you have $a^{12}\equiv1\pmod{21}$. – Jyrki Lahtonen Mar 4 '17 at 20:31
• To use Fermat's Little Theorem, you need a prime modulo and $21$ is not a prime as you know. – Ninja Mar 4 '17 at 20:31
• You're using Fermat's little theorem wrong : $21$ isn't prime. Moreover, your later calculations don't really make sense : why 99 and 11 ? A fast way to solve this would be using Euler's theorem (generalization of Fermat's little theorem), but maybe you don't know that. Thus another way to do it would be to calculate the first few powers of $1990$ mod $21$, and see some cycle, and use this to your advantage – Max Mar 4 '17 at 20:32
• Should the original power have been $1990^{1991}$ instead of $1990^{21}$? – Henning Makholm Mar 4 '17 at 20:33

Fermat's Little Theroem applies to prime modulus, but $21$ is not prime. So the cycling of exponents happens on a number which divides Euler's totient $\phi(21) = \phi(3)\cdot \phi(7) = 2\cdot 6 = 12$.
You can immediately reduce $1990 \equiv 16 \bmod 21$, as you observe. We also know $16 = 2^4$. And then using the fact that $\gcd(2,21) = 1$ we know that $2^{\phi(21)} \equiv 1 \bmod 21$ so $1990^{21}\equiv 16^{21}$ $\equiv 2^{84}$ $\equiv (2^{12})^7$ $\equiv 1^7$ $\equiv 1 \bmod 21$
$\ {\rm mod}\ 7\!:\,\ 1990\equiv 2\,$ so $\,\color{#c00}{1990^{\large 3}}\equiv 2^{\large 3}\equiv \color{#c00}1$
$\ {\rm mod}\ 3\!:\,\ 1990\equiv 1\,$ so $\,\color{#c00}{1990^{\large 3}}\equiv 1^{\large 3}\equiv\color{#c00} 1,\,$ so combining we have
${\rm mod}\ 21\!:\ \color{#c00}{1990^{\large 3}\equiv 1},\,$ since $\,1990^{\large 3}\!-1\,$ is divisible by $\,3,7\,$ so by their lcm $= 21,\,$
so $\ 1990^{\large 21}\!\equiv (\color{#c00}{1990^{\large 3}})^{\large 7}\!\equiv \color{#c00}1^{\large 7}\!\equiv 1$