Let $(a,p)=1$ where $p$ is an odd prime. Show that if $a$ has order $2k \text{(mod p)}$ for an integer $k$, then $a^{k} \equiv -1 \text{(mod p)}$.
My attempt is that since $a$ has order $2k,$ then $a^{2k} \equiv 1 \text{(mod p)}$, which means that $(a^{2})^{k} \equiv 1 \text{(mod p)}$. But how can I use primality of $p$?
Best Answer
We have $a^{2k}-1 = (a^k+1)(a^k-1)$ and thus $p \mid (a^k-1)(a^k+1)$. Therefore by Euclid's Lemma either $a^k \equiv 1\pmod{p}$ or $a^k \equiv -1 \pmod{p}$. The former case is impossible since $2k$ is the order of $a$ modulo $p$. Thus $a^k \equiv -1 \pmod{p}$.