7
$\begingroup$

I've stumbled upon this congruence very similar to Fermat's Little Theorem, but I can't seem to wrap my head around how to solve it. It goes like this:

i) Suppose $p$ is prime, $(a,p)=1$ and the congruence $x^2 \equiv a \pmod p$ has a solution $x$. Prove that $a^{(p-1)/2}\equiv 1 \pmod p$.

And the same question but with an additional condition:

ii) Suppose $p$ is prime, $p \equiv 3 \pmod 4$, $(a,p) = 1$ and the congruence $x^2 \equiv a \pmod p$ does not have a solution $x$. Prove that $a^{(p-1)/2}\equiv -1 \pmod p$.

For i: Since $x^2 \equiv a \pmod p$ has a solution, we know that $p \mid x^2 - a$, hence $kp=x^2-a$ for some integer $k$, or $a = x^2-kp$. Now this doesn't really help me much!

For ii: Similarly stumped.

$\endgroup$
  • 1
    $\begingroup$ As noted in one of the answers, the condition $p \equiv 3 \pmod{4}$ in (ii) is superfluous. $\endgroup$ – Andreas Caranti Sep 23 '13 at 7:53
7
$\begingroup$

Hints:

(i) If $x^2 \equiv a \pmod p$ then what is $a^{\frac{p-1}{2}}$ as a power of $x$? Do this and apply Fermat's little theorem.

(ii) Write $x=a^{\frac{p-1}{2}}$. Fermat's little theorem gives you $x^2 \equiv 1 \pmod p$. Now use the rest of the information you've been given.

$\endgroup$
2
$\begingroup$

For the first part, note that $x^{p-1}\equiv 1$ by Fermat's little theorem. Then assuming that $p$ is not $2$ (deal with that case separetly), we have $1\equiv (x^2)^{(p-1)/2}\equiv a^{(p-1)/2}$.

For the second part, let $\alpha$ be a primitive element (this means that there is an element $\alpha$ in $\{1,...,p-1\}$ such that $\alpha$ has order exactly $p-1$ (this means that $\alpha^i$ will range through $\mathbb{Z}_p^\times$ as we let $i=1,2,..,p-1$).

Then, since $a$ is not a square, we have that $a=\alpha^{2c+1}$, so $$a^{(p-1)/2}\equiv (\alpha^{2c+1})^{(p-1)/2}\equiv \alpha^{c(p-1)}\alpha^{(p-1)/2}\equiv \alpha^{(p-1)/2}$$Now note that $\alpha^{(p-1)/2}$ is a root of $x^2-1$. Also note that $1$ and $-1$ are also roots. Note that we cannot have three roots (the degree of $x^2-1$ is $2$ and over a field, the degree bounds the number of roots), so we have that $\alpha^{(p-1)/2}$ is either $1$ or $-1$, but it cannot be $1$ since the order of $\alpha$ is $p-1$, hence it is $-1$, and we are done. I just realized that I did not use the fact that $p\equiv 3\pmod{4}$ (all i used was $p\neq 2$), so I guess the conditions can be weakened.

$\endgroup$
2
$\begingroup$

For the first one, one just has to compute: $a^{(p-1)/2} = x^{2(p-1)/2} = x^{p-1} = 1 \mod p$.

For the second one, let $p = 4k + 3$. $a^{(p-1)/2}$ is a root of $X^2 - 1$ (as above) which has only two solutions: $1$ and $-1$. If $a^{(p-1)/2} = 1\mod p$, $a^{(p-1)/2}a = a \mod p$, and $a^{(p-1)/2}a = a^{(p+1)/2} = a^{2(k+1)} = {(a^{k+1})}^2$, hence $x^2 = a$ has a solution, which is a contradiction. Hence $a^{(p-1)/2} = -1\mod p$.

$\endgroup$
1
$\begingroup$

This is an important theorem due to Leonhard Euler reworded in a different essence I think and it is usually proved at the beginning of an introduction to quadratic residues.

First you need to know that in a complete residue system modulo $p$, there are exactly $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ non-residues and the quadratic residues are $1^2,2^2, \cdots, (\frac{p-1}{2})^2$. This could be checked as an easy exercise. If you needed further help with this let me know.

By using Fermat's little theorem we know that $a^{p-1} \equiv 1 \pmod{p}$.

Now I'll give you a sketch of proof for Euler's criterion, you can work out the details on your own. You can factor $a^{p-1} -1$ as $$a^{p-1}-1=(a^{(p-1)/2}-1)(a^{(p-1)/2}+1)$$

$$\implies 0 \equiv a^{p-1}-1\equiv (a^{(p-1)/2}-1)(a^{(p-1)/2}+1) \pmod{p}$$

But since $p$ is a prime number, then $a^{(p-1)/2}-1 \equiv 0 \pmod{p}$ or $a^{(p-1)/2}+1 \equiv 0 \pmod{p}$

You can check that $1^2, 2^2, \cdots, (\frac{p-1}{2})^2$ satisfy $x^{(p-1)/2} \equiv 1 \pmod{p}$. Now if you work out the details now which is easy I think it's obvious that $a$ is a non-residue if and only if $a^{(p-1)/2} \equiv -1 \pmod{p}$.

If you're familiar with Legendre's symbol you can state this theorem this way as well:

$$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\ \pmod{ p}\;\;\text{ and } \left(\frac{a}{p}\right) \in \{-1,0,1\}$$.

where Legendre's symbol is defined as:

$$\left(\frac{a}{p}\right) = \begin{cases}\;\;\,1 \text{ if } a \text{ is a quadratic residue modulo}\ p\text{ and } a \not\equiv 0\pmod{p} \\-1 \text{ if } a \text{ is a quadratic non-residue modulo}\ p\\\;\;\,0 \text{ if } a \equiv 0 \pmod{p}. \end{cases}$$

$\endgroup$
1
$\begingroup$

$\newcommand{Zp}{\mathbb{Z}/p\mathbb{Z}}$Among the many proofs of these facts, let me mention one that uses basically only Fermat's little theorem, and then the fact that a polynomial of degree $n$ over a field has at most $n$ roots. And then of course you need to know that $\Zp$ is a field, for $p$ prime.

I take $p$ to be an odd prime.

If $0 \ne b \in \Zp$, then the equation $$ x^{2} = b^{2} $$ has the two solutions $x = b, -b$, and no more, because $x^{2} - b^{2}$ is a polynomial of degree $2$ over the field $\Zp$.

It follows that there are $$ \frac{p-1}{2} $$ non-zero squares in $\Zp$.

If $0 \ne b \in \Zp$, we have $$ (b^{2})^{(p-1)/2} = 1, $$ so if $a = b^{2}$ is a non-zero square, then $$ a^{(p-1)/2} = 1. $$

In other words, the non-zero squares in $\Zp$ are roots of the polynomial $$ f = x^{(p-1)/2} - 1. $$ Since there are $(p-1)/2$ squares, and $f$ has degree $(p-1)/2$, the non-zero squares are exactly the roots of the $f$.

So if $a$ is a non-square, we have $a^{(p-1)/2} \ne 1$. Since $$ (a^{(p-1)/2})^{2} = 1, $$ we have that $a^{(p-1)/2}$ is a root of $x^{2} - 1$, and it is different from $1$, so $a^{(p-1)/2} = -1$.

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