3
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ 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$, ... $\endgroup$
    – Berci
    Jul 6, 2018 at 1:25
  • $\begingroup$ By least residue I mean any integer between and including 0 and p-1. I'm not really sure what a cyclic group is. $\endgroup$
    – Adam
    Jul 6, 2018 at 1:26
  • $\begingroup$ Is $\gcd(a,p)=1$ ? $\endgroup$
    – lhf
    Jul 6, 2018 at 2:10
  • $\begingroup$ That's not given. $\endgroup$
    – Adam
    Jul 6, 2018 at 2:10

5 Answers 5

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Very nice, thanks for keeping it simple (i.e. no abstract algebra) :) $\endgroup$
    – Adam
    Jul 6, 2018 at 2:46
2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.