2
$\begingroup$

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.

$\endgroup$
0
5
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ $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. $\endgroup$ – achille hui Apr 20 '13 at 11:45
3
$\begingroup$

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

$\phi(1729)=1296$

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

And you have $1296=36^2$.

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

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.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.