Results 1 to 2 of 2

Math Help - Proving a generalization of Fermat's Little Theorem, involving the Euler phi function

  1. #1
    Newbie
    Joined
    Mar 2012
    From
    Southeast Michigan
    Posts
    4

    Proving a generalization of Fermat's Little Theorem, involving the Euler phi function

    Here is a simplified idea of what I am working to solve. I am unsure where to start (besides what I've listed below from looking at previous sections), or where to go from there. Thanks in advance for any help with this proof!

    The Euler phi function ϕ gives the number of positive integers less than or equal to, and relatively prime to, a give positive integer. e.g. ϕ(3)=2, ϕ(5)=4. There is a generalization of Fermat's Little Theorem due to Euler:


    Theorem. Let n be a positive integer and a∈ℤ with gcd(a,n)=1. Then a^(ϕ(n))≡1(mod n)


    (a) Prove this theorem.


    (b) Explain why Fermat's Little Theorem is a special case of this theorem.


    What I've deduced so far.
    The fact that a^|G|=e for every a∈G, if G is finite with identity e, seems as if it will help.
    LaGrange's Theorem and/or cosets will likely be used as well.


    Thanks in advance. Any help/solution to this would be a lifesaver!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Proving a generalization of Fermat's Little Theorem, involving the Euler phi func

    consider, that for any natural number n > 0, the set of integers modulo n co-prime to n form a group, often called the group of units modulo n, or U(n).

    this group has order φ(n): |U(n)| = φ(n). it may not be clear that if gcd(a,n) = 1 and gcd(b,n) = 1, that gcd(ab,n) = 1 as well.

    but if gcd(a,n) = 1, then there are integers r,s with ar + sn = 1, and if gcd(b,n) = 1, then there are integers t,u with bt + un = 1.

    hence (ar + sn)(bt + un) = 1*1 = 1, so:

    ab(rt) + (aru + bst + sun)n = 1, so there are integers x,y (namely x = rt, and y = aru+bst+sun) with (ab)x + yn = 1, gcd(ab,n) = 1.

    if we denote a modulo n by [a], this shows that if [a],[b] are in U(n), so is [a][b] = [ab]. since U(n) is finite, it is a group, since it is closed

    under multiplication modulo n. thus Lagrange's theorem applies.

    to obtain Fermat's Little Theorem, one considers the group U(p), where p is a prime.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  2. Working with mod p (Euler's and Fermat's Theorem)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 22nd 2010, 11:22 PM
  3. Replies: 0
    Last Post: September 17th 2009, 06:44 PM
  4. Proving Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2009, 03:06 AM
  5. [SOLVED] Problem involving Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 19th 2009, 12:58 PM

Search Tags


/mathhelpforum @mathhelpforum