Prove for all odd $n \in \mathbb{Z}$: $a^{3(n+1)^2+1} \equiv a$ mod $21$.
I started this way: $21 = 3*7$ and $gcd(3,7) = 1$. So
\begin{cases} x \equiv a^{3(n+1)^2+1} \, \text{mod} \, 7 \\ x \equiv a^{3(n+1)^2+1} \, \text{mod} \, 3 \end{cases}
I was trying to use following theorem to solve the equation with mod $3$: $a^p \equiv a$ mod $p$ with $p$ a prime number. But I have no idea how to solve the first equation (the one with mod $7$) and how to prove that $n$ has to be an odd number.
Thanks in advance!
Answer
If $n$ is odd then $n+1$ is even and $4|(n+1)^2$ and $12|3(n+1)^3$ and $3(n+1)^3 +1\equiv 1\pmod {12}$. (Let $3(n+1)^3 + 1 = 12k + 1$
By Fermat's little theorem $a^{3(n+1)^2+1} = a^{12k}a\equiv 1^{2k}a \equiv a$ if $7\not \mid a$ and if $7|a$ then $a^{3(n+1)^2+1}\equiv 0 \equiv a\pmod 7$.
Likewise $a^{3(n+1)^2+1} = a^{12k}a\equiv 1^{4k}a \equiv a$ if $3\not \mid a$ and if $3|a$ then $a^{3(n+1)^2+1}\equiv 0 \equiv a\pmod 3$
So $a^{3(n+1)^2 +1}\equiv a \pmod {3,7}$ if $n$ is odd.
And since $a^{3(n+1)^2+1} \equiv a\pmod 3$ and $a^{3(n+1)^2+1} \equiv a \pmod 7$, then $a^{2(n+1)^3+1}\equiv a \pmod {3*7}$ by the Chinese remainder theorem.
That is to say: $a\equiv a\pmod {21}$ is certainly a solution to $x\equiv a\pmod 3$ and $x\equiv a\pmod 7$ because $a \equiv a \pmod{anything}$, and CRT says that is the only solution $\mod 21$.
No comments:
Post a Comment