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

1. ## 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

2. Originally Posted by glman74
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|$.

3. 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

4. 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 !