Results 1 to 4 of 4

Thread: Fermat Little Theorem

  1. #1
    Member
    Joined
    Nov 2007
    Posts
    108

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by namelessguy View Post
    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$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    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)$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2007
    Posts
    108
    Thanks a lot icemanfan and Laurent. I forgot to relate congruence to divisibility.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermatís Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 27th 2011, 06:52 PM
  2. Replies: 4
    Last Post: Jan 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jun 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Oct 19th 2009, 09:47 PM
  5. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Oct 28th 2008, 08:15 AM

Search Tags


/mathhelpforum @mathhelpforum