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

• Dec 1st 2010, 05:37 PM
glman74
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
• Dec 1st 2010, 05:47 PM
Drexel28
Quote:

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 $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 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|$.
• Dec 1st 2010, 09:24 PM
glman74
Quote:

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.

Quote:

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
• Dec 3rd 2010, 12:58 AM
simplependulum
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 !