Return to Answer

Commonmark migration

edited Jun 17, 2020 at 8:17

The answer above is the best explanation but just for reference, the formal proof I was looking for was found quite easily once I realised my question applied to odd-ordered finite fields too, and is as follows, taken from this document from ETH Zurich.

The theorem is:

Let $q$ be an odd prime power, and $a \in \mathbb{F}_q$, then:

$a \in QR(q), \iff a^{(q-1)/2} = 1$

$a \in QNR(q), \iff a^{(q-1)/2} = -1$

$| QNR(q) | = \frac{q-1}{2} = | QR(q) |$

And the essence of the proof is:

1: A polynomial of degree $d$, with coefficients from a field $R$, can have at most $d$ roots in $R$. 2: Lagrange's Theorem: In a finite group $G$, $x^{|G|} = 1$ for any $x \in G$.

On the one hand, by Fact 1, the polynomial $x^{q-1} -1 = 0$ cannot have more than $q - 1$ roots by Legrange's theorem, because all the elements in $\mathbb{F}_q^*$ are roots.

Consequently, since $x^{q-1} - 1 = ( x^{(q-1)/2} + 1 ) ( x^{(q - 1)/2} - 1 )$ and the ring of polynomials over $\mathbb{F}_q$ has no (non-trivial) zero divisors, again Fact 1 implies that both factors $( x^{(q-1)/2} + 1 )$ and $( x^{(q-1)/2} - 1 )$ must have exactly $\frac{q-1}{2}$ roots.

The theorem is:

Let $q$ be an odd prime power, and $a \in \mathbb{F}_q$, then:

$a \in QR(q), \iff a^{(q-1)/2} = 1$

$a \in QNR(q), \iff a^{(q-1)/2} = -1$

$| QNR(q) | = \frac{q-1}{2} = | QR(q) |$

And the essence of the proof is:

1: A polynomial of degree $d$, with coefficients from a field $R$, can have at most $d$ roots in $R$. 2: Lagrange's Theorem: In a finite group $G$, $x^{|G|} = 1$ for any $x \in G$.

On the one hand, by Fact 1, the polynomial $x^{q-1} -1 = 0$ cannot have more than $q - 1$ roots by Legrange's theorem, because all the elements in $\mathbb{F}_q^*$ are roots.

Consequently, since $x^{q-1} - 1 = ( x^{(q-1)/2} + 1 ) ( x^{(q - 1)/2} - 1 )$ and the ring of polynomials over $\mathbb{F}_q$ has no (non-trivial) zero divisors, again Fact 1 implies that both factors $( x^{(q-1)/2} + 1 )$ and $( x^{(q-1)/2} - 1 )$ must have exactly $\frac{q-1}{2}$ roots.

The theorem is:

Let $q$ be an odd prime power, and $a \in \mathbb{F}_q$, then:

$a \in QR(q), \iff a^{(q-1)/2} = 1$

$a \in QNR(q), \iff a^{(q-1)/2} = -1$

$| QNR(q) | = \frac{q-1}{2} = | QR(q) |$

And the essence of the proof is:

1: A polynomial of degree $d$, with coefficients from a field $R$, can have at most $d$ roots in $R$. 2: Lagrange's Theorem: In a finite group $G$, $x^{|G|} = 1$ for any $x \in G$.

On the one hand, by Fact 1, the polynomial $x^{q-1} -1 = 0$ cannot have more than $q - 1$ roots by Legrange's theorem, because all the elements in $\mathbb{F}_q^*$ are roots.

Consequently, since $x^{q-1} - 1 = ( x^{(q-1)/2} + 1 ) ( x^{(q - 1)/2} - 1 )$ and the ring of polynomials over $\mathbb{F}_q$ has no (non-trivial) zero divisors, again Fact 1 implies that both factors $( x^{(q-1)/2} + 1 )$ and $( x^{(q-1)/2} - 1 )$ must have exactly $\frac{q-1}{2}$ roots.

Source Link

answered Dec 1, 2016 at 15:26

bekah

The theorem is:

Let $q$ be an odd prime power, and $a \in \mathbb{F}_q$, then:

$a \in QR(q), \iff a^{(q-1)/2} = 1$

$a \in QNR(q), \iff a^{(q-1)/2} = -1$

$| QNR(q) | = \frac{q-1}{2} = | QR(q) |$

And the essence of the proof is:

1: A polynomial of degree $d$, with coefficients from a field $R$, can have at most $d$ roots in $R$. 2: Lagrange's Theorem: In a finite group $G$, $x^{|G|} = 1$ for any $x \in G$.

On the one hand, by Fact 1, the polynomial $x^{q-1} -1 = 0$ cannot have more than $q - 1$ roots by Legrange's theorem, because all the elements in $\mathbb{F}_q^*$ are roots.

Consequently, since $x^{q-1} - 1 = ( x^{(q-1)/2} + 1 ) ( x^{(q - 1)/2} - 1 )$ and the ring of polynomials over $\mathbb{F}_q$ has no (non-trivial) zero divisors, again Fact 1 implies that both factors $( x^{(q-1)/2} + 1 )$ and $( x^{(q-1)/2} - 1 )$ must have exactly $\frac{q-1}{2}$ roots.