# Thread: order of primitive roots

1. ## order of primitive roots

let m be a positive integer and let a be an integer with (a,m)=1.
(a) Prove that if Ordm(a)=xy (with x and y positive integers), then ordm(a^x)=y
(b) prove that if ordm(a)=m-1, then m is a prime number.

2. Originally Posted by mndi1105
let m be a positive integer and let a be an integer with (a,m)=1.
(a) Prove that if Ordm(a)=xy (with x and y positive integers), then ordm(a^x)=y
Because $\displaystyle (a^x)^y = a^{xy} \equiv 1(\bmod m)$. Now if $\displaystyle k<y$ so that $\displaystyle (a^x)^k \equiv 1$ then it means $\displaystyle a^{kx}\equiv 1(\bmod m)$ and $\displaystyle kx < xy$ but $\displaystyle xy$ is order of $\displaystyle a$. This is a contradiction. Thus the order of $\displaystyle a^x$ must be $\displaystyle y$

(b) prove that if ordm(a)=m-1, then m is a prime number.
That is because $\displaystyle \text{ord}(a) =m-1 \leq \phi(m) \leq m - 1$.
The inequalities force $\displaystyle \phi(m) = m-1$.
This happens if and only if $\displaystyle m$ is prime.