3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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?

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

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.