# 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 $(a^x)^y = a^{xy} \equiv 1(\bmod m)$. Now if $k so that $(a^x)^k \equiv 1$ then it means $a^{kx}\equiv 1(\bmod m)$ and $kx < xy$ but $xy$ is order of $a$. This is a contradiction. Thus the order of $a^x$ must be $y$

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