2
$\begingroup$

Consider the congruence $x^{n} \equiv 1 \pmod{p}$, $p$ prime. One of my friends mentioned that it suffices to suppose that $n$ divides $p - 1$ since if not the number of solutions to $x^{n} = 1$ is equal to the number of solutions to $x^{m} = 1$ where $m \mid p - 1$. I'm skeptical, why is this true?

2 Answers 2

1

The nonzero elements modulo $p$ form a cyclic group under multiplication. Questions like this are much more obvious when rephrased in terms of the isomorphic group of integers modulo $p-1$ under addition.

0

Using Discrete Logarithm, $n\cdot ind_gx\equiv 0\pmod{p-1}$ as $\phi(p)=p-1$ where $g$ is any primitive root of $p$.

this is a Linear Congruence Equation.

Using Linear congruence theorem, this case is clearly solvable as $0\mid (n,p-1)$ and has exactly $(n,p-1)$ in-congruent solutions.

Clearly, $(n,p-1)$ is a divisor of $(p-1)$