Results 1 to 3 of 3

Math Help - Fermat's

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    13

    Fermat's

    Find least nonnegative residue... n=99^999999 m=23


    Let n be an integer. Prove each congruence below.
    a. n^21 is congruent to n mod 30
    b. n^7 congruent to n mod 42
    c. n^13 is congruent to n mod 2730


    Let a E Z and let p be a prime number. Prove that p|a^p + (p-1)!a and p|(p-1)!a^p +a
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by kel1487 View Post
    a. n^21 is congruent to n mod 30
    I do this first one - others should be similar. Let (Z_30)* be the multiplicative group of the units of (Z_30) under multiplication. A consequence of the Chinese Remainder Theorem is that (Z_30)* is isomorphic to the group (Z_2)* x (Z_3)* x (Z_5)* and this group in turn is isomorphic to G = (Z_2) x (Z_4). Note the group G has the property that any element raised to the power of four returns the identity. Therefore, if gcd(n,30)=1 then we can regard n being in (Z_30)* and so n^4 is the identity. Thus, n^4 = 1 (mod 30) if gcd(n,30)=1. This means n^21 = (n^4)^5 = 1 (mod 30).

    A simple calculation will prove that this problem is true for n=2,3,5. Now let n be an integer (not divisible by 30 - otherwise the problem is trivial). Then gcd(n,30)=1,2,3,5,6,10,15. If the gcd = 1 then that is the case above. If gcd = 2 then it mean we can write n=2m where gcd(m,30)=1. But this means n^21 = (2m)^21 = 2^21 * n^21 = 1 (mod 30). The situation is similar if gcd = 3 or 5 because we proved this special cases. Say that gcd = 6. Then we can write n = 2*3*m where gcd(m,30)=1. But then n^21 = 2^21 * 3^21 * m^21 = 1 (mod 30). The same situation if gcd = 10 because then we could write n=2*5*m. And repeat the argument.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by kel1487 View Post
    Let a E Z and let p be a prime number. Prove that p|a^p + (p-1)!a and p|(p-1)!a^p +a
    1) a^p + (p-1)!a = a + (-1)a = 0 (mod p)
    2)a^p(p-1)! + a = a(-1) + a = 0 (mod p)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat's little theorem help!
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 17th 2011, 08:16 PM
  2. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 19th 2009, 09:47 PM
  3. fermat's little thm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 28th 2009, 10:37 AM
  4. Not Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 10:39 PM
  5. fermat...or not fermat?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2006, 09:16 AM

Search Tags


/mathhelpforum @mathhelpforum