Results 1 to 4 of 4

Thread: 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 $\displaystyle e$ such that $\displaystyle a^e \equiv 1 \ mod(p)$ must be a divisor of $\displaystyle p-1$

    This what I have so far:

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

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


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

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

    $\displaystyle \Rightarrow \ k = 0 $

    But it's not clear to me how to show that $\displaystyle 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
    22
    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 $\displaystyle e$ such that $\displaystyle a^e \equiv 1 \ mod(p)$ must be a divisor of $\displaystyle p-1$

    This what I have so far:

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

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


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

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

    $\displaystyle \Rightarrow \ k = 0 $

    But it's not clear to me how to show that $\displaystyle 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 $\displaystyle 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 $\displaystyle e$.

    You know by the division algorithm that $\displaystyle e=q(p-1)+r$ for some $\displaystyle 0\leqslant r\leqslant p-2$. Evidently then we have that $\displaystyle 1\equiv a^{(p-1)q+r}\equiv a^r\text{ mod }p$. Now, if $\displaystyle r\ne 0$ then we'd have that $\displaystyle r<e$ and $\displaystyle r\in K$ contradicting the minimality of $\displaystyle 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 $\displaystyle e$ is the smallest such integer...and from this you must prove that $\displaystyle e\mid p-1$


    P.S. If you know group theory this is clear since $\displaystyle |\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 $\displaystyle e$ is the smallest such integer...and from this you must prove that $\displaystyle e\mid p-1$
    Thanks for the explanation. Yes, I was confused.

    P.S. If you know group theory this is clear since $\displaystyle |\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 $\displaystyle a^{p-1} \equiv 1 \bmod{p} $ so $\displaystyle e $ should be less than or equal to $\displaystyle p-1 $ . If we write $\displaystyle e = (p-1)q + r $ then $\displaystyle q = 0 $ and $\displaystyle r = e $ and nothing to tell us !


    To prove the statement , we should use Euclidean Algorithm

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

    In fact , if we can find a natural number $\displaystyle T $ such that $\displaystyle a^T \equiv 1 \bmod{p} $ then $\displaystyle 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: Jun 15th 2011, 08:04 AM
  2. Replies: 13
    Last Post: May 12th 2011, 04:32 AM
  3. Replies: 2
    Last Post: Jul 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: Jul 5th 2010, 02:44 AM
  5. Replies: 2
    Last Post: Mar 26th 2009, 06:58 PM

Search Tags


/mathhelpforum @mathhelpforum