Results 1 to 4 of 4

Math Help - 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 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?
    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 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
    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 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).
    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: September 27th 2011, 06:52 PM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 01:33 AM
  4. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 09:47 PM
  5. Fermat's Little Theorem Help [again]
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 28th 2008, 08:15 AM

Search Tags


/mathhelpforum @mathhelpforum