Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$.

Question

Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$.

I want to know if my attempt is correct.

First $a^{13} \equiv (a^3)^4 \cdot a \equiv a^4 \cdot a \equiv a^3 \cdot a^2 \equiv a \cdot a^2 \equiv a^3 \equiv a \pmod 3$.

Second, $(a^7)^2 \cdot a^{-1} \equiv a^2 \cdot a^{-1} \equiv a \pmod 7$.

Third, $a^{12} \equiv 1 \pmod{13} \implies a^{13} \equiv a \pmod{13}$.

So, $3, 7, 13 | a^{13} - a$. Since they are relatively prime in pairs, $$3 \cdot 7 \cdot 13 | a^{13} - a \implies a^{13} \equiv a \pmod{ 3 \cdot 7 \cdot 13}$$

Is it correct? Could you suggest an easier or a better proof?

Thanks.

Answer 1

By Euler's Theorem (or you may even use Fermat's theorem),

$a^2 \equiv 1 \pmod {3} \implies a^{12} \equiv 1 \pmod 3 \implies a^{13} \equiv a \pmod 3$

$a^6 \equiv 1 \pmod {7} \implies a^{12} \equiv 1 \pmod 7 \implies a^{13} \equiv a \pmod 7$

$a^{12} \equiv 1 \pmod {13} \implies a^{13} \equiv a \pmod {13} $

$\therefore a^{13} \equiv a \pmod {lcm[3,7,13]} \implies a^{13} \equiv a \pmod {3\times7\times13}$

It is quit trivial if $a$ is not co-prime to at least one of $3, 7, 13.$ Then you will not even need Euler or Fermat's theorem.

Remember, if

$a\equiv b \pmod {m_1}$

$a\equiv b \pmod {m_2}$

.

.

.

$a\equiv b \pmod {m_n}$

then, $a\equiv b \pmod {lcm[m_1,m_2,...,m_n]}$

Answer 2

By the Chinese remainder theorem, we have that $ R = \mathbb{Z}/(3 \cdot 7 \cdot 13)\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/13\mathbb{Z} $, so the equation $ X^{13} - X = 0 $ holds for $ R $ if it holds for each factor ring on the right. On the other hand, we know by Fermat's little theorem that this equation does hold for each ring on the right, and the result follows. (Note that $ 2, 6 | 12 $, which is why the equation holds.)