Prove that $a^{n-1} \equiv 1 \pmod n$ and $a^{(n-1)/p} \not\equiv 1 \pmod n$ for every prime $p$ dividing $n-1$ implies $n$ is prime [duplicate]

Question

Let $a$ and $n\ge3$ be integers. Suppose that $a^{n-1} \equiv 1 \pmod n$, while $a^{(n-1)/p} \not\equiv 1 \pmod n$ for every prime $p$ dividing $n-1$, and I want to show that $n$ is prime.

First of all, we know that $(a,n) = 1$ because if $(a,n) = g > 1$, then $g \mid n$ which means $a^{n-1} \equiv 1 \pmod g$, but this is impossible since $g \mid a \implies g \mid a^{n-1}$. Since $a^{n-1} \equiv 1 = a^0 \pmod n$, it follows that $n-1 \equiv 0 \pmod{\phi(n)}$ (this is the part I am having trouble proving, I know that the converse always holds, and I want to show that in this case the statement also holds), which means $n - 1 = k \cdot\phi(n)$, and now we just need to show $k = 1$. But we have that $(n-1)/p \not \equiv 0 \pmod {\phi(n)}$ which means $\phi(n) \nmid (n-1)/p$ for all $p$ dividing $n-1$. Thus, $\phi(n) = n-1$.

Is it possible to prove the statement preceding the text in bold? Otherwise, what is the right approach to take for this problem?

Answer 1

Ended up figuring out the answer. Here's the altered proof:

First of all, we know that $(a,n) = 1$ because if $(a,n) = g > 1$, then $g \mid n$ which means $a^{n-1} \equiv 1 \pmod g$, but this is impossible since $g \mid a \implies g \mid a^{n-1}$. Since $a^{n-1} \equiv 1 = a^0 \pmod n$, it follows that $n-1 \equiv 0 \pmod{h}$, where $h$ is the order of $a\pmod n$, which means $n - 1 = k \cdot h$, and now we just need to show $k = 1$. But we have that $(n-1)/p \not \equiv 0 \pmod {h}$ which means $h \nmid (n-1)/p$ for all $p$ dividing $n-1$. Thus, $h = n-1$. But $\phi(n) \leq n-1$ and $h \mid \phi(n)$ so $\phi(n) = n - 1$.