# Show that $a^{3(n+1)^2+1} \equiv a$ mod 21 for every odd $n \in \mathbb{N}$

I tried tackling this problem by first dividing both sides by $$a$$ so that I get $$a^{3(n+1)^2} \equiv 1$$ mod 21. I did that so I can use the Chinese remainder theorem (since gcd(3, 7) = 1) to get the equations

$$x \equiv 1$$ mod 3

and

$$x \equiv 1$$ mod 7

Then I thought of using Fermat's little theorem to proceed, but that led me nowhere.

Any help is appreciated, thanks!

• You don't know $a$ is coprime to 21, so you can't divide by $a$. Jun 9, 2019 at 10:56
• Most of the proofs of this essentially repeat the proof of the simple direction of Korselt's Criterion. I added an answer from that more general standpoint. You should learn this general theorem since its proof is not much more work and it will give you much more power. Jun 9, 2019 at 14:40

As $$21=3\cdot7$$

Using Fermat's Little Theorem $$a^3\equiv a\pmod3\implies3|a(a^2-1)$$ $$a^7\equiv a\pmod 7\implies7|a(a^6-1)$$

As $$a^6-1=(a^2)^3-1^3=(a^2-1)\cdots$$

lcm$$(3,7)$$ will divide $$a(a^6-1)$$

So it is sufficient to establish $$3(n+1)^2+1\equiv1\pmod6$$ $$\iff(n+1)^2\equiv0\pmod2$$

$$\iff n+1\equiv0\pmod2$$

$$\iff n+1$$ is even

• @OP this amounts to repeating the proof of the simple direction of Korselt's Criterion - see the link in my answer. Jun 9, 2019 at 14:38

If $$a$$ is divided by $$7$$ it's obvious.

Let $$\gcd(a,7)=1$$.

Thus, $$a^6\equiv1\pmod7$$ and we obtain: $$a^{3(n+1)^2+1}=a^{3(n+1)^2}\cdot a\equiv a\pmod7.$$

By below $$(\Leftarrow)$$ it suffices to show that $$\,\color{#c00}{2,3}\mid 3(n\!+\!1)^2,$$ which is clear since $$n$$ is odd.

Theorem  (Korselt's Carmichael Criterion) $$\$$ For $$\rm\:1 < e,n\in \Bbb N\:$$ we have

$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\ n\ \ is\ \ \color{}{squarefree},\ \ and \ \ \color{#c00}{p\!-\!1}\mid e\!-\!1\ \, for\ all \ primes\ \ p\mid n\quad$$

Proof $$\$$ See this answer.

Since $$3$$ and $$7$$ are relatively prime you can prove it separately for $$3$$ and $$7$$.

We do it only for $$7$$. If $$7\mid a$$ we are done. If $$7\nmid a$$ then $$a^6 \equiv_7 1$$ so $$a^{3(n+1)^2}\equiv_7 1$$ and we are done again.