Show that $a^j$ has order $(p − 1)/j$ modulo $p$.

Question

Suppose that $a$ has order $p − 1$ modulo $p$ where $p$ is a prime, and $j \mid (p − 1)$. Show that $a^j$ has order $(p − 1)/j$ modulo $p$.

I'm a little confused on how to start this.

Because $j \mid (p-1)$ I know by divisibility that $(p-1)$ is a multiple of $j$. So $(p-1) / j$ will be some integer $k$. After this do I use Eulers theorem to prove $a^j = k$ mod $p$?

Answer 1

Hint $\ (a^j)^n\equiv 1\iff p\!-\!1\mid jn\iff (p\!-\!1)/j\mid n$

Answer 2

We know that $a^{p-1} \equiv 1 \pmod{p}$ by Fermat's Little Theorem, and we know that $j \mid p-1$ so we can write $p-1 = jk$, whence $k = \frac{p-1}{j}$. Therefore, $$a^{p-1} \equiv a^{jk} \equiv \left(a^j\right)^k \equiv 1 \pmod{p}.$$ So we know that $a^j$ has order at most $\frac{p-1}{j}$. Can you show that there is no smaller number $m$ such that $\left(a^j\right)^m \equiv 1 \pmod p$?

Answer 3

In a finite cyclic group, each subgroup has size dividing the size of the group. Conversely, given a positive divisor of the size of the group, there is a subgroup of that size.