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

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 ?

• By 'least residue' do you mean a generator for the multiplicative group of $\Bbb Z/(p)$? If yes, it means you are aware of the fact that it's a cyclic group of order $p-1$. Then we can write $a=g^u, \ b=g^v$, ... Jul 6, 2018 at 1:25
• By least residue I mean any integer between and including 0 and p-1. I'm not really sure what a cyclic group is.
Jul 6, 2018 at 1:26
• Is $\gcd(a,p)=1$ ?
– lhf
Jul 6, 2018 at 2:10
• That's not given.
Jul 6, 2018 at 2:10

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

• Very nice, thanks for keeping it simple (i.e. no abstract algebra) :)
Jul 6, 2018 at 2:46

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

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$

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

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