# Fermat Little Theorem

• Oct 4th 2008, 01:07 PM
namelessguy
Fermat Little Theorem
Can someone check if my work is correct on this problem?
Given $1728=2^63^3$. Show that if $(a,7)=1, (a,13)=1, (a,19)=1$ then $a^{1728}\equiv 1 mod(7); a^{1728}\equiv 1 mod (13); a^{1728}\equiv 1 mod (19)$
By FLT, we have $a^6\equiv 1 mod(7)$,
$a^{1728}\equiv (a^6)^{288}\equiv 1^{288}\equiv 1 mod (7)$
We can prove the other two similarly.
Then the follow question is to show that $a^{1728}\equiv 1 mod (1729)$ using the result above and given that $1729=7\times13\times19$. Can someone help me make the argument here?
• Oct 4th 2008, 01:28 PM
icemanfan
Quote:

Originally Posted by namelessguy
Then the follow question is to show that $a^{1728}\equiv 1 mod (1729)$ using the result above and given that $1729=7\times13\times19$. Can someone help me make the argument here?

Your work is correct for the first part of the problem.

To get you on the right track,
$a^{1728} \equiv 1 \mod 7$
$a^{1728} \equiv 1 \mod 13$

$a^{1728} = 7m + 1$ for some integer m
$a^{1728} = 13n + 1$ for some integer n

Subtraction yields
$13n - 7m = 0$
$13n = 7m$
$n = \frac{7m}{13}; 7|n$ (because (7, 13) = 1)
$n = 7p$ for some integer p

$a^{1728} = 13(7p) + 1$
$a^{1728} = 91p + 1$
$a^{1728} \equiv 1 \mod 91$
• Oct 4th 2008, 01:30 PM
Laurent
You proved that 7, 13 and 19 divide $a^{1728}-1$. Moreover, these numbers are relatively prime, so that (by Gauss Theorem) their product (1729) divides $a^{1728}-1$ as well. In other words, $a^{1728}=1\,({\rm mod }\,1729)$.
• Oct 4th 2008, 01:40 PM
namelessguy
Thanks a lot icemanfan and Laurent. I forgot to relate congruence to divisibility.