# 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$. – user10354138 Jun 9 '19 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. – Bill Dubuque Jun 9 '19 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. – Bill Dubuque Jun 9 '19 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.