# $a^{37} \equiv a \pmod {1729}$ [duplicate]

Use Euler theorem to show that

$$a^{37} \equiv a \pmod {1729}$$ is true for any integer $a$.

I am a beginner in Number theory and stuck in this problem. Show me the right direction.

$1729 = 7 \cdot 13 \cdot 19$

We know Fermat's little theorem $a^{p-1} \equiv 1 \pmod p$. Notice that $p-1 = 6, 12, 18$ have a lot in common the lcm is $36$.

So by chinese remainder theorem you can get $a^{36}=1 \pmod {1729}$.

• $a$ need not be relative prime to 1729. you should use the more general form of Fermat's little theorem $a^p \equiv a \pmod p$ for prime p. – achille hui Apr 20 '13 at 11:45

$a^{\phi(1729)}=1 (\mod 1729)$

$\phi(1729)=1296$

$a^{1296}=1 (\mod 1729)$

And you have $1296=36^2$.

• Your note is superfluous, though what you did requires that. +1 and try to mend this. – DonAntonio Apr 20 '13 at 14:24

By Chinese Remainder Theorem $R=\mathbb{Z}_{1729}\cong\mathbb{Z}_7\times\mathbb{Z}_{13}\times\mathbb{Z}_{19}$. Write the elements of $R$ in three coordinates, then you can easily see the result.