solutions to $x^n\equiv a\pmod{p}$

Question

I'm asked to prove that if $\gcd(n,p-1)=1$ where p is prime, then $$x^n\equiv a \pmod{p}$$ has exactly one solution. What I've done so far is the following,

Since $\gcd(n,p-1)=1$, that means, except for $1$, there is no least residue $r$ such that $r^n\equiv 1\pmod{p}$. Moreover, it would suffice to show that every least residue raised to $n$ is cogruent to another unique least residue or, in other words, for any two least residues $a,b$, $$a^n\equiv b^n\pmod{p}\quad\to\quad a\equiv b\pmod{p}.$$ To do so, suppose $a^n\equiv b^n\pmod{p}$, then $$p\mid (a-b)(a^{n-1}+a^{n-2}b+\dots + b^{n-2}a+ b^{n-1})$$ and so $p$ must divide one of those terms. At this point, I tried to show that $p\nmid (a^{n-1}+a^{n-2}b+\dots + b^{n-2}a+ b^{n-1})$ by finding a contradiction but I got stuck. I'm thinking maybe one of my earlier steps was incorrect because I'm not really using the fact that $\gcd(n,p-1)=1$ in the proof. Am I heading in the right direction here ?

Answer 1

If $a\equiv0$, then $a\equiv 0^n$.

If $a\not\equiv0 $, then $\gcd(a,p)=1$. Since $\gcd(n,p-1)=1$, we have $nu=1+(p-1)v$, for some $u,v \in \mathbb N$. Then $(a^u)^n = a^{nu} = a^{1+(p-1)v} = a (a^{p-1})^v \equiv a$.

Therefore, the map $x \mapsto x^n$ on $\Bbb Z/(p)$ is surjective and so it must be injective. In other words, there is exactly one solution of $x^n \equiv a \bmod p$.

Answer 2

Suppose $p$ is prime, and $n$ is an integer such that $\gcd(n,p-1)=1$.

Let $f:Z_p\to Z_p$ be given by $f(x)=x^n$.

Claim:$\;f$ is injective.

First we show $f(x)=0\iff x=0$ . . . \begin{align*} &f(x)=0\\[4pt] \iff\;&x^n=0\\[4pt] \iff\;&x^n\equiv 0\;(\text{mod}\;p)\\[4pt] \iff\;&p{\,\mid\,}x^n\\[4pt] \iff\;&p{\,\mid\,}x\qquad\text{[since $p$ is prime]}\\[4pt] \iff\;&x\equiv 0\;(\text{mod}\;p)\\[4pt] \iff\;&x=0\\[4pt] \end{align*} Next, suppose $f(x)=f(y)$, for some $x,y\in Z_p$, with $x,y\ne 0$.

Let $z\in Z_p$ be given by $z=xy^{-1}$. \begin{align*} \text{Then}\;\;&f(x)=f(y)\\[4pt] \implies\;&x^n=y^n\\[4pt] \implies\;&x^n(y^{-1})^n=1\\[4pt] \implies\;&z^n=1\\[4pt] \implies\;&z^{\large{{\gcd(n,p-1)}}}=1\\[4pt] \implies\;&z=1\\[4pt] \implies\;&x=y\\[4pt] \end{align*} It follows that $f$ is injective, as claimed.

But $Z_p$ is finite, hence, since $f$ is injective, $f$ is bijective.

It follows that for all integers $a$, the congruence $$x^n\equiv a (\text{mod}\;p)$$ has a unique solution for $x$, mod $p$, namely $x=f^{-1}(r)$, where $r=(a\;\text{mod}\;p)$.

Answer 3

We are given the fact that $gcd(n,p-1)=1$ i.e. $$nk_1=k_2(p-1)+1 \implies n=k_2\times k_1^{-1}(p-1)+1\tag{1}$$, for some integers $k_1$ and $k_2$ Let ,we are asked to find $x^n \mod p$ i.e. $$x^{(k_2 k_1^{-1}p-k_2 k_1^{-1}+1)}\mod p\tag{2}$$ Since $p$ is a prime, $x^p \mod p=x$ .Put it in expression (2) to get $x \mod p$, so the answer will be $x$.
Hence proved if $x<p$

Answer 4

I found a proof that, more generally, if $p\not\mid a$, then $x^n\equiv a \pmod p$ has $0$ or $d=\gcd(n,p-1)$ solutions, depending on whether $a^{\frac{p-1}d}\equiv 1\pmod p$. The proof uses a primitive root mod $p$...

I will try to reproduce it: write $g^b\equiv a\pmod p$. For any $x$ satisfying the congruence, we have $x$ is $g^m$ for some $m$.. Then $g^{nm}\equiv g^b\pmod p$, which means $nm\equiv b\pmod{p-1}$, since the order of $g\pmod p$ is $p-1$. This linear congruence has $0$ or $d$ solutions, depending on whether $d\not\mid b$ or $d\mid b$. Finally, the latter condition is equivalent to $(p-1)\mid \frac{(p-1)b}d$, which is equivalent to $g^{\frac {(p-1)b}d}\equiv a^{\frac {(p-1)}d}\equiv 1 \pmod p$...

Answer 5

$a \equiv 0 \iff x \equiv 0$ by Euclid's Lemma.

Consider $a \not\equiv 0$. Then $x \not\equiv 0$. Let $g$ be a primitive root (which always exists mod $p$), $\chi$ such that $g^\chi \equiv x$, $\alpha$ such that $g^\alpha \equiv a$.

Then $x^n \equiv a \mod p \iff g^{\chi n} \equiv g^\alpha \mod p \iff \chi n \equiv \alpha \mod{p-1} $, since the order of $g$ is $p-1$. A basic fact of modular linear congruences is that since $n$ and $p-1$ are coprime, there is exactly one solution $\chi$ which corresponds to one solution $x$.