Quadratic Residues -- Number Theory 22

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

[chandrasekhar]

Hello Michael, the definition of a quadratic residue doesn't require gcd(a, n)=1. Note that 4 is a quadratic residue (mod 6) and gcd(4, 6)=2, the definition makes sense for any a and n.

[prathikkannan]

I feel like the proof of eulers criterion was overcomplicated, I was able to come up with a much simpler argument. Basically for the non zero residues mod p, we have a^{p -1} = 1(mod p), and a^{(p - 1)/2} = -1 or a^{(p - 1)/2} = 1 modulo p. This follows from the fact that every residue is either primitive or not. Then by lagrange each congruence has at most (p - 1)/2 roots, but if we are to split p - 1 roots amongst the two to satisfy this condition if follows that each congruence has exactly (p - 1)/2 roots.

Now consider if a is a quadratic residue, then a = n^2(mod p) for some n and exponentiating by (p - 1)/2 we get a^{(p - 1)/2} = n^{p - 1} = 1(mod p). Therefore this congruence has (p - 1)/2 solutions, all of which are the quadratic residues. So now the (p - 1)/2 residues that are not quadratic residues must satisfy a^{(p - 1)/2} = -1(mod p) and we are doe as this is in accorance with the legender symbol.

[Tehom]

For the theorem at 10:00, I like to represent the non-zero elements of mod p (ie the multiplicative group of GF(p)) as a table as powers of some generator of GF(p)*. So basically I have a table of logarithms mod p. Then I just notice that any element a[2i] equals a[i]^2, the element half its distance from a[0] in the table, and thus is a quadratic residue, and that it also equals a[-i mod (p-1)]^2. Then I notice that a[i] and a[-i mod (p-1)] are always different elements except for the cases of a[0] and a[(p-1)/2], which are the two roots of unity. Thus all the even positions are quadratic residues and since each "consumes" two distinct square roots, this accounts for all the elements leaving nothing else as a quadratic residue.

[yonatanrosmarin]

In the proof of the Euler criterion, when dividing the set {1, 2, ..., p-1} to pairs, it is not clear that after removing terms, when picking a new k, there still exist a matching l so k*l = a. i.e. the fact that the inverse is unique per each k is implied here.

[keithmasumoto]

i love this stuff but it's still challenging to wrap my mind around. but i did watch the entire video.

[RexxSchneider]

Spoiler alert.

For those who want to check their answers to the warm-ups.


There are 6 quadratic residues mod 13 = { 1, 4, 9, 3, 12, 10 }
There are 3 quadratic residues mod 16 = { 1, 4, 9 }
There are 8 quadratic residues mod 17 = { 1, 4, 9, 16, 8, 2, 15, 13 }
Note that k^2 = { 1, 4, 9, ... } are obviously always quadratic residues mod n for k^2 < n.
The number of quadratic residues mod n is an interesting question. You may want to check whether the number of quadratic residues mod n is p if n=2p or 3p, where p is an odd prime.

(24/19) = (5/19) ≡ 5^9 mod 19 ≡ 5*(25^4) ≡ 5*(6^4) ≡ 5*(36^2) ≡ 5*(-2^2) ≡ 5*4 ≡ 20 ≡ 1 mod 19. So 5 is a quadratic residue mod 19, and so is 24. You can check that both 9^2 = 81 and 10^2 = 100 are congruent to 5 (and hence 24) mod 19.
(18/11) = (7/11) ≡ 7^5 mod 11 ≡ 7*(49^2) ≡ 7*(5^2) ≡ 7*3 ≡ 21 ≡ -1 mod 11. So 7 is a quadratic non-residue mod 11 and so is 18. Check: the 5 quadratic residues mod 11 are { 1, 4, 9, 5, 3 }

[AntonioLasoGonzalez]

Here is an alternate proof of the third euler criterion: From a previous video, we know that, because (p-1)/2 divides p-1, the congruence a^(p-1/2)=1(mod p) has exactly p-1 solutions. From the second euler criterion, we know that each quadratic residue mod p (a total of (p-1)/2) satisfies the congruence, then that means that they will be the only solutions, i.e. if a is a quadratic non-residue then a^(p-1/2) is not congruent to 1 mod p. Now, knowing that a^(p-1/2) is either 1 or -1 mod p, we get the third euler criterion.

[deadfish]

If you allow the Legendre symbol to be defined with p not prime (where the final condition becomes a, p not coprime), does Euler's criterion still hold (replacing (p-1)/2 with phi(p))?

[Horinius]

@Michael, there is no such gcd(a, n) = 1 condition for something to be a quadratic residue.

[kobethebeefinmathworld]

Wait, I thought you already uploaded this video weeks ago. What happened? 🤔