# Fermat Little Theorem

• Oct 4th 2008, 12:07 PM
namelessguy
Fermat Little Theorem
Can someone check if my work is correct on this problem?
Given $\displaystyle 1728=2^63^3$. Show that if $\displaystyle (a,7)=1, (a,13)=1, (a,19)=1$ then $\displaystyle a^{1728}\equiv 1 mod(7); a^{1728}\equiv 1 mod (13); a^{1728}\equiv 1 mod (19)$
By FLT, we have $\displaystyle a^6\equiv 1 mod(7)$,
$\displaystyle 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 $\displaystyle a^{1728}\equiv 1 mod (1729)$ using the result above and given that $\displaystyle 1729=7\times13\times19$. Can someone help me make the argument here?
• Oct 4th 2008, 12:28 PM
icemanfan
Quote:

Originally Posted by namelessguy
Then the follow question is to show that $\displaystyle a^{1728}\equiv 1 mod (1729)$ using the result above and given that $\displaystyle 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,
$\displaystyle a^{1728} \equiv 1 \mod 7$
$\displaystyle a^{1728} \equiv 1 \mod 13$

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

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

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