Using order of $a$ to show that $n \equiv 1 \mod p$

Question

We are given that $n$ is a prime number. Additionally, $a^p \equiv 1 \mod n$ where $p$ is a prime and the order of $a$.

How can I show that $n \equiv 1 \mod p$?

Answer 1

Since $a^p\equiv 1\;(\text{mod}\;n)$, it follows that $\gcd(a,n)=1$.

Since $n$ is prime, by Fermat's little Theorem, we have $a^{n-1}\equiv 1\;(\text{mod}\;n)$.

But then, since $p$ is the order of $a$, mod $n$, it follows that $p\mid (n-1)$, hence $n\equiv 1\;(\text{mod}\;p)$.