(number theory): [imath]\exists x[/imath] so [imath]x^2\equiv -1[/imath] (mod p) [imath]\Leftrightarrow p \equiv 1[/imath] (mod 4) with p odd prime.

[MathNugget]

The question is basically the title. It's from Algebraic Number Theory, by Alaca and Williams. They use the Legendre symbol to say the same thing. I cannot seem to find it on the internet (I bet it is somewhere, but since they're probably written in Latex, it's hard to search for it)

Firstly, I'll work on "[imath]\Rightarrow[/imath]" (direct implication)

[imath]x^2\equiv -1 \Leftrightarrow x^2\equiv p-1 \Leftrightarrow p \mid x^2-p+1[/imath] (equivalences mod p)
Say [imath]x \in \mathbb{Z}_p[/imath], then [imath]x^2-p+1 \in \{-p+1, ... , p^2-p+1 \}[/imath]. Then since [imath]p \mid x^2-p+1 \Rightarrow x^2-p+1 \in \{0, p \}[/imath].

[imath]x^2-p+1=0[/imath] then [imath]\Delta=4(p-1)[/imath] and we notice p-1 can't be a square if [imath]p \equiv 3[/imath] (mod 4) since all squares mod 4 are 0 or 1...

Similarly if [imath]x^2-p+1=p[/imath] then [imath]\Delta=4(2p-1)[/imath] and we notice if [imath]p \equiv 3[/imath] (mod 4) then [imath]\Delta=4(2(4k+3)-1)=4(8k+5)[/imath] and there are no squares equivalent to 5 mod 8...

But on the other side, the task seems very hard to solve. I am familiar with some very basic tactics of number theory.
I was hoping that maybe I can prove that [imath]\forall i, j \in \mathbb{Z}_p[/imath], [imath]i^2\equiv j^2 \Leftrightarrow i=j[/imath], but it only happens on [imath]i, j \in \{0, ..., \frac{p-1}{2}\}[/imath]. So, in fact, only half of the numbers of [imath]\mathbb{Z}_p[/imath] are quadratic residues ... and I am trying to prove p-1 is one of those quadratic residues.

Any advice?

 

[fresh_42]

This statement is equivalent to the formula:
[math] \left(\dfrac{-1}{p}\right) =(-1)^{\frac{p-1}{2}} [/math]which says that [imath] -1 [/imath] is a quadratic residue modulo [imath] p [/imath] if [imath] (-1)^{\frac{p-1}{2}} =1[/imath] which is the case for [imath] p\equiv 1\pmod{4} .[/imath] The only other case is [imath] p\equiv 3\pmod{4} [/imath] which would lead to [imath] \left(\dfrac{-1}{p}\right)=-1 [/imath] and [imath] -1 [/imath] would be a quadratic non residue modulo [imath] p. [/imath]

This formula is a consequence of the law of quadratic reciprocity:
[math] \left(\dfrac{p}{q}\right)\cdot \left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}=\begin{cases} 1&\text{if }\;p\equiv 1\pmod{4}\text{ or }q\equiv 1\pmod{4}\\ -1 &\text{if }\;p\equiv 3\pmod{4}\text{ and }q\equiv 3\pmod{4} \end{cases}[/math]So how ever you write this theorem, with or without using Legendre symbols, the key is the quadratic reciprocity theorem.

 

[MathNugget]

This statement is equivalent to the formula:
[math] \left(\dfrac{-1}{p}\right) =(-1)^{\frac{p-1}{2}} [/math]which says that [imath] -1 [/imath] is a quadratic residue modulo [imath] p [/imath] if [imath] (-1)^{\frac{p-1}{2}} =1[/imath] which is the case for [imath] p\equiv 1\pmod{4} .[/imath] The only other case is [imath] p\equiv 3\pmod{4} [/imath] which would lead to [imath] \left(\dfrac{-1}{p}\right)=-1 [/imath] and [imath] -1 [/imath] would be a quadratic non residue modulo [imath] p. [/imath]

This formula is a consequence of the law of quadratic reciprocity:
[math] \left(\dfrac{p}{q}\right)\cdot \left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}=\begin{cases} 1&\text{if }\;p\equiv 1\pmod{4}\text{ or }q\equiv 1\pmod{4}\\ -1 &\text{if }\;p\equiv 3\pmod{4}\text{ and }q\equiv 3\pmod{4} \end{cases}[/math]So how ever you write this theorem, with or without using Legendre symbols, the key is the quadratic reciprocity theorem.

But wouldn't p and q have to be primes to apply that formula? (which -1 and p-1 aren't)

 

[fresh_42]

But wouldn't p and q have to be primes to apply that formula? (which -1 and p-1 aren't)

The quadratic reciprocity theorem (QRT) requires two primes, yes, but the two supplements of the QRT do only require one. Maybe I was wrong and misled by the word supplement which made me think they were corollaries. https://en.wikipedia.org/wiki/Quadratic_reciprocity#Supplements_to_Quadratic_Reciprocity
The Wikipedia page has also a proof of your statement

Quadratic reciprocity - Wikipedia

en.wikipedia.org

using Euler's criterion

Euler's criterion - Wikipedia

en.wikipedia.org

So maybe Euler is enough and QRT not necessary.

 

[MathNugget]

The quadratic reciprocity theorem (QRT) requires two primes, yes, but the two supplements of the QRT do only require one. Maybe I was wrong and misled by the word supplement which made me think they were corollaries. https://en.wikipedia.org/wiki/Quadratic_reciprocity#Supplements_to_Quadratic_Reciprocity
The Wikipedia page has also a proof of your statement

Quadratic reciprocity - Wikipedia

en.wikipedia.org

using Euler's criterion

Euler's criterion - Wikipedia

en.wikipedia.org

So maybe Euler is enough and QRT not necessary.

I see. Thank you!!