Why does $n \equiv n^{21}\bmod 33$?

Question

I’m trying to understand why $n \equiv n^{21} \bmod 33$ for $n \in \{0, \ldots, 16\}$. I know that $\phi(33)=20$ and so $n^{20} \equiv 1 \bmod 33$ for all $n \in \mathbb Z$ coprime to $33$. This then simply gives $n^{21} \equiv n \bmod 33$ for the same $n$ as previously described. However, in my range of possible values for $n$ not all $n$ are coprime to $33$, yet I have that $n^{21} \equiv n$. I’m not certain why this has occurred. I also know that for all $n \in \mathbb Z$ I have $n^{33} \equiv n^{33-20} \equiv n^{13}$ but this also doesn’t help.

Answer 1

You've articulated well the reason why that exact approach doesn't work. However a slight elaboration will work:

By the Chinese remainder theorem, $n \equiv n^{21} \pmod {33}$ if and only if $n \equiv n^{21} \pmod {3}$ and $n \equiv n^{21} \pmod {11}$. So it suffices to prove those two congruences separately.

On the other hand, when the modulus is a prime, there's a version of Fermat's little theorem that works regardless of coprimalty: $n\equiv n^p\pmod p$. (The proof of this, of course, is like the approach you tried above: it follows when $(n,p)=1$ from $1\equiv n^{p-1}\pmod p$, while for $p\mid n$ it's trivial.) In particular, $n\equiv n^3\pmod 3$ and $n\equiv n^{11}\pmod{11}$.

Can you finish from there?

Answer 2

There are a few ways to explain this, Here's one:

$$a\equiv b\bmod p\implies a=py+b \therefore(a,p)=z\implies zc=zdy+b\implies zc-zdy=b$$ Which:$$\because zc-zdy=z(c-dy)\implies (a,b)==(a,p)$$ implies: $$(zc)^e\equiv z(c-dy) \bmod z(dy)$$ This means, the coprime part of a determines, which multiple of their gcd it lands on. EDIT: You can also use Fermat in parts, $n^{21}\equiv n \bmod 11, n^{21}\equiv n \bmod 3 \therefore n^{21}\equiv n \bmod 33$