0

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$?

1 Answers1

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)$.

quasi
  • 58,772
  • Why does it follow that $gcd(a,n)=1$? –  Oct 26 '18 at 13:53
  • 1
    If $\gcd(a,n) > 1$, then since $n$ prime, it would follow that $a\equiv 0;(\text{mod};n)$, but that would imply $a^p\equiv 0;(\text{mod};n)$. – quasi Oct 26 '18 at 13:56