Results 1 to 4 of 4

Math Help - Euler Function Proof

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    79

    Euler Function Proof

    Suppose that m is an integer with m > 1 and gcd(a(a-1), m) = 1. Prove that:
    1 + a + a^2 + ... + a^(phi(m) - 1) ≡ 0 mod m


    I'm really not sure where to start with this. I assume I will have to make use of Euler's Theorem at some point, but I don't even know where to begin.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by uberbandgeek6 View Post
    Suppose that m is an integer with m > 1 and gcd(a(a-1), m) = 1. Prove that:
    1 + a + a^2 + ... + a^(phi(m) - 1) ≡ 0 mod m


    I'm really not sure where to start with this. I assume I will have to make use of Euler's Theorem at some point, but I don't even know where to begin.
    I assume it's supposed to be that (a-1,m)=1. Then, a-1\in \mathbb{Z}_m^{\times}. But, note that by using the common formula \displaystyle (a-1)\sum_{n=0}^{\varphi(m)-1}a^n=a^\varphi(n)-1\equiv 0\text{ mod }m. Thus, multiplying both sides by (a-1)^{-1} gives the result.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by uberbandgeek6 View Post
    Suppose that m is an integer with m > 1 and gcd(a(a-1), m) = 1. Prove that:
    1 + a + a^2 + ... + a^(phi(m) - 1) ≡ 0 mod m


    I'm really not sure where to start with this. I assume I will have to make use of Euler's Theorem at some point, but I don't even know where to begin.
    The assumption (a(a-1),m)=1 implies both (a,m)=1 and (a-1,m)=1. So by Euler's Theorem, a^{\phi(m)}\equiv1\pmod m, i.e. a^{\phi(m)}-1\equiv0\pmod m.

    Now, we can divide both sides by a-1 to get the equivalent congruence \displaystyle\frac{a^{\phi(m)}-1}{a-1}\equiv0\pmod m since a-1 is relatively prime to m . (The left-hand side is an integer...)

    But \displaystyle\frac{a^{\phi(m)}-1}{a-1}= 1+a+a^2+\cdots+a^{\phi(m)-1} (Sum of geometric series). The result follows.

    To Drexel28, it's not enough to have (a-1,m), simply because (a,m)=1 is needed to conclude that a^{\phi(m)}-1\equiv0\pmod m.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by melese View Post
    The assumption (a(a-1),m)=1 implies both (a,m)=1 and (a-1,m)=1. So by Euler's Theorem, a^{\phi(m)}\equiv1\pmod m, i.e. a^{\phi(m)}-1\equiv0\pmod m.

    Now, we can divide both sides by a-1 to get the equivalent congruence \displaystyle\frac{a^{\phi(m)}-1}{a-1}\equiv0\pmod m since a-1 is relatively prime to m . (The left-hand side is an integer...)

    But \displaystyle\frac{a^{\phi(m)}-1}{a-1}= 1+a+a^2+\cdots+a^{\phi(m)-1} (Sum of geometric series). The result follows.

    To Drexel28, it's not enough to have (a-1,m), simply because (a,m)=1 is needed to conclude that a^{\phi(m)}-1\equiv0\pmod m.
    Bleh, of course. Stupid mistake.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euler function proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 23rd 2011, 08:44 AM
  2. Euler's totient function Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 10th 2011, 05:30 AM
  3. Proof about Euler's φ-function
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: September 28th 2010, 01:13 PM
  4. Euler's phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 7th 2010, 08:46 PM
  5. Euler phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 29th 2009, 09:58 PM

Search Tags


/mathhelpforum @mathhelpforum