0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ You don't know $a$ is coprime to 21, so you can't divide by $a$. $\endgroup$ – user10354138 Jun 9 '19 at 10:56
  • 2
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jun 9 '19 at 14:40
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @OP this amounts to repeating the proof of the simple direction of Korselt's Criterion - see the link in my answer. $\endgroup$ – Bill Dubuque Jun 9 '19 at 14:38
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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