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

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.

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?

• For $n=n^{21}$ mod 33 would I just have to apply the theorem repeatedly? – Reinhild Van Rosenú Mar 4 '19 at 8:50

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$$