Results 1 to 9 of 9

Math Help - Order modulo a prime

  1. #1
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169

    Order modulo a prime

    I am not sure how to prove this:

    If a has order t modulo a prime p, show that a^(t-1)+a^(t-2)+...+a+1 == 0(mod p).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by tarheelborn View Post
    I am not sure how to prove this:

    If a has order t modulo a prime p, show that a^(t-1)+a^(t-2)+...+a+1 == 0(mod p).
     1+a+\cdot\cdot\cdot+a^{t-2}+a^{t-1} = \frac{1-a^t}{1-a} \equiv 0\mod{p} since  a^t\equiv 1 \mod{p} .

    Note that it's necessary that  \text{ord}_p(a)>1 , otherwise  (1-a)^{-1} doesn't exist modulo  p .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    I can't untangle the algebra of this move... Sorry, can you break it down into a couple of steps? Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by tarheelborn View Post
    I can't untangle the algebra of this move... Sorry, can you break it down into a couple of steps? Thanks.
    This is a geometric series.

    What do you get when you multiply  (a-1)(a^{t-1}+a^{t-2}+\cdot\cdot\cdot+a+1) ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    You would get (a*a^(t-1)+a*a^(t-2)+...+a^2+a-a^(t-1)-a^(t-2)-1), right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by tarheelborn View Post
    You would get (a*a^(t-1)+a*a^(t-2)+...+a^2+a-a^(t-1)-a^(t-2)-1), right?
    Correct, now notice how the majority of the terms cancel out, so you end up with  a^t-1 .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    Yes, actually I did notice that...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by tarheelborn View Post
    So since a^t == 1 (mod p), (a^t)-1 == 0 (mod p), is that the idea?
    yep
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. If a has order n - 1 modulo n, then n is prime.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 10th 2011, 12:29 PM
  2. Summation up to p-1 modulo p, p prime
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: October 21st 2011, 05:46 PM
  3. prime and modulo proofs
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 22nd 2011, 02:43 AM
  4. Replies: 3
    Last Post: February 17th 2011, 07:51 AM
  5. square modulo the prime...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 12th 2010, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum