Results 1 to 4 of 4

Math Help - Proving that e is a divisor of (p-1) if a^e equiv 1 mod(p) for the smallest e

  1. #1
    Newbie
    Joined
    Dec 2010
    From
    Bangalore
    Posts
    2

    Question Proving that e is a divisor of (p-1) if a^e equiv 1 mod(p) for the smallest e

    Hello,

    I am learning some elementary number theory by myself, and am trying to solve the following:

    Prove that the smallest e such that a^e \equiv 1 \ mod(p) must be a divisor of p-1

    This what I have so far:

    Let e \equiv k \ mod(p-1).

    \Rightarrow \ e = k + r(p-1)


    \Rightarrow \ a^{k + r(p-1)} \equiv 1 \ mod(p)

    From this we can show that a^{k}\ mod(p) \equiv 1 \mod(p)

    \Rightarrow \ k = 0

    But it's not clear to me how to show that e should be the smallest such integer.

    I'd appreciate any help in understanding the above.

    Regards

    M
    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 glman74 View Post
    Hello,

    I am learning some elementary number theory by myself, and am trying to solve the following:

    Prove that the smallest e such that a^e \equiv 1 \ mod(p) must be a divisor of p-1

    This what I have so far:

    Let e \equiv k \ mod(p-1).

    \Rightarrow \ e = k + r(p-1)


    \Rightarrow \ a^{k + r(p-1)} \equiv 1 \ mod(p)

    From this we can show that a^{k}\ mod(p) \equiv 1 \mod(p)

    \Rightarrow \ k = 0

    But it's not clear to me how to show that e should be the smallest such integer.

    I'd appreciate any help in understanding the above.

    Regards

    M
    I think you're almost there. Let K=\left\{m\in\mathbb{N}:a^m\equiv 1\text{ mod }p\right\}. This is non-empty (obviously) and so it has a smallest element e.

    You know by the division algorithm that e=q(p-1)+r for some 0\leqslant r\leqslant p-2. Evidently then we have that 1\equiv a^{(p-1)q+r}\equiv a^r\text{ mod }p. Now, if r\ne 0 then we'd have that r<e and r\in K contradicting the minimality of e.


    Now that I read your post more carefully though, I think you may have misunderstood what you were to prove. You are given that e is the smallest such integer...and from this you must prove that e\mid p-1


    P.S. If you know group theory this is clear since |\langle a\rangle|\mid\left|\mathbb{Z}_p^{\times}\right|.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    From
    Bangalore
    Posts
    2
    Now that I read your post more carefully though, I think you may have misunderstood what you were to prove. You are given that e is the smallest such integer...and from this you must prove that e\mid p-1
    Thanks for the explanation. Yes, I was confused.

    P.S. If you know group theory this is clear since |\langle a\rangle|\mid\left|\mathbb{Z}_p^{\times}\right|.
    I am not there yet - but I hope to understand the above some day!

    Regards

    M
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    I don't think the division algorithm works in this case , because we have  a^{p-1} \equiv 1 \bmod{p} so e should be less than or equal to  p-1 . If we write  e = (p-1)q + r then  q = 0 and  r = e and nothing to tell us !


    To prove the statement , we should use Euclidean Algorithm

    Suppose  D is the HCF of  e and  p-1 then we can always find a pair of positive integers  (x,y) such that  ex - (p-1)y = D so  a^{ex} \equiv a^{(p-1)y} a^D \bmod{p} implying  a^D \equiv 1 \bmod{p} but  D \leq e because D|e and  D \geq e because of the minimality of  e . We conclude that  e=D so  e = D |p-1 .

    In fact , if we can find a natural number  T such that  a^T \equiv 1 \bmod{p} then  e|T . It is a very important result !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 15th 2011, 08:04 AM
  2. Replies: 13
    Last Post: May 12th 2011, 04:32 AM
  3. Replies: 2
    Last Post: July 10th 2010, 05:14 PM
  4. [SOLVED] a \not\equiv b (mod m), then b \not\equiv a (mod m)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 5th 2010, 02:44 AM
  5. Replies: 2
    Last Post: March 26th 2009, 06:58 PM

Search Tags


/mathhelpforum @mathhelpforum