Fdtxjr

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)/2equiv 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)/2equiv -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.

Hints:

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

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

For the first part, note that $x^p-1equiv 1$ by Fermat's little theorem. Then assuming that $p$ is not $2$ (deal with that case separetly), we have $1equiv (x^2)^(p-1)/2equiv 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 $mathbbZ_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)/2equiv (alpha^2c+1)^(p-1)/2equiv alpha^c(p-1)alpha^(p-1)/2equiv 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 $pequiv 3pmod4$ (all i used was $pneq 2$), so I guess the conditions can be weakened.

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 = 1mod p$, $a^(p-1)/2a = a mod p$, and $a^(p-1)/2a = 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 = -1mod p$.

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 $fracp-12$ quadratic residues and $fracp-12$ non-residues and the quadratic residues are $1^2,2^2, cdots, (fracp-12)^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 pmodp$.

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-1equiv (a^(p-1)/2-1)(a^(p-1)/2+1) pmodp$$

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

You can check that $1^2, 2^2, cdots, (fracp-12)^2$ satisfy $x^(p-1)/2 equiv 1 pmodp$. 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 pmodp$.

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

$$left(fracapright) equiv a^(p-1)/2 pmod p;;text and left(fracapright) in -1,0,1$$.

where Legendre's symbol is defined as:

$$left(fracapright) = begincases;;,1 text if a text is a quadratic residue modulo ptext and a notequiv 0pmodp \-1 text if a text is a quadratic non-residue modulo p\;;,0 text if a equiv 0 pmodp. endcases$$

$newcommandZpmathbbZ/pmathbbZ$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
$$
fracp-12
$$
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$.