Fermat Little Theorem

**namelessguy** · October 4th 2008, 12:07 PM

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?

**icemanfan** · October 4th 2008, 12:28 PM

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$

**Laurent** · October 4th 2008, 12:30 PM

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

**namelessguy** · October 4th 2008, 12:40 PM

Thanks a lot icemanfan and Laurent. I forgot to relate congruence to divisibility.

Thread: Fermat Little Theorem

LinkBack

Thread Tools

Display

Fermat Little Theorem

Similar Math Help Forum Discussions

Fermat’s Theorem

abstract algebra [primitive root mod n, euler theorem, fermat theorem]

Fermat's Last Theorem

Fermat's Little Theorem

Fermat's Little Theorem Help [again]

Search Tags