a (simple?) property of primitive roots

Question

Let $p\neq 2$ be a prime and let $a$ be a primitive root modulo $p^k$ satisfying $p^k|a^{p^k-1}-1$ and $p^k\nmid a^{\dfrac{p^k-1}{q}}-1$ for all prime divisors $q$ of $p^k-1$. Then $k=1$.

---

I was reading a solution to a contest problem and the above statement was used, but the proof was omitted... I don't see a solution, could you help?

Answer 1

According to the question, we have $$a^{p^k-1} \equiv 1 \ \mbox{mod} \ p^k$$ So the order divides $p^k-1$. We know that $a$ is a primitive root, so the order of $a$ must be $\phi(p^k)=p^k-p^{k-1}$, as it generates the group under multiplication. So $p^k-p^{k-1} \mid p^k-1$ However, it must be the case that they are equal, otherwise we contradicts the last assumption the question makes, with equality at $k=1$. Therefore $k=1$.

Answer 2

Euler's theorem state that :

$$a^{\varphi(n)} \overset{n}{\equiv} 1 \Longrightarrow a^{p^k-p^{k-1}} \overset{p^k}{\equiv} 1.$$

---

Lemma: Let $n$ be a natural number and let $a$ be any integer.
Then for evey natural number $t$ we have: $$a^t\overset{n}{\equiv} 1 \Longleftrightarrow \text{ord}_n(a) \mid t.$$

---

Suppose on contrary that $2 \leq k$.
Let's deonte order of $a$ module $p^k$ by $r$; then:

• your assumption implies that $r \mid p^k-1$;
• also Euler's theorem implies that $r \mid p^k-p^{k-1}$;

so we can conclude that $r$ must divides $\gcd \left( p^k-p^{k-1} , p^k-1 \right) $,
in other words $r \mid p-1$; which implies that $\color{Blue}{r \leq p-1}$.

Note that the assumption that $a$ is a primitive root module $p^k$ implies that $r=p^k-p^{k-1}$

So we have :

$$\color{Red}{p} \leq p^{k-1} < (p-1)p^{k-1}=p^k-p^{k-1}=\color{Blue}{r \leq p-1};$$ which is an obvious contradiction.