Results 1 to 3 of 3

Math Help - Order of Integer Proof

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    Order of Integer Proof

    Suppose we have p is a prime, a > 1, and gcd(a,p) = 1

    1.) Prove that a^(ord_(p)a - 1) + a(ord_(p)a - 2) + ... + a^1 + 1 = 0 (mod p)

    2.) Prove that if a has order 3 (mod p), then a + 1 has ord 6 (mod p).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fifthrapiers View Post
    Suppose we have p is a prime, a > 1, and gcd(a,p) = 1

    1.) Prove that a^(ord_(p)a - 1) + a(ord_(p)a - 2) + ... + a^1 + 1 = 0 (mod p)
    We know that,

    a^k = 1 (mod p) where k is ord_p(a).
    If and only if,
    a^k - 1 = 0 (mod p)
    Factorize,
    (a-1)(a^{k-1}+a^{k-2}+...+a^1+1)=0 (mod p)
    Since,
    a-1 != 0 (mod p ) unless a=1 (but then proof is trivial).
    That means, (division)
    a^{k-1}+a^{k-2}+...+a^1+1 =0(mod p)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fifthrapiers View Post
    2.) Prove that if a has order 3 (mod p), then a + 1 has ord 6 (mod p).
    Let us first show that if gcd(a,p)=1 then gcd(a+1,p)=1. Meaning, we want to show that the order modulo p is defined (because if gcd(a+1,p)=p then the order is not defined!)

    Say, it is not, gcd(a+1,p)=1 that is a+1=pn. Hence, a=pn-1.
    But then a = pn -1 = -1 (mod p) meaning the order is 2 not 3, a contradiction.

    Thus, this problem does not lead to an undefined operation.

    Now we can solve this problem, gaze below.
    Attached Thumbnails Attached Thumbnails Order of Integer Proof-picture10.gif  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: March 6th 2011, 11:08 AM
  2. Order of Integer Question
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 27th 2010, 09:51 PM
  3. Order of Integer Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 21st 2010, 05:33 PM
  4. Number theory, order of an integer
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 06:53 AM
  5. order of an integer
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 21st 2006, 06:37 AM

Search Tags


/mathhelpforum @mathhelpforum