Theory of numbers: Quadratic residues

This lecture is part of an online undergraduate course on the theory of numbers.

We define quadratic residues (squares) and describe their basic properties, in particular Euler's criterion. The we describe fast algorithms to test whether a number is a quadratic residue, and if so to find its square root.

[mostly_mental]

Thanks for the videos. Number theory's never been my strong suit, but this series is making it a lot clearer.

It occurrs to me that the integers mod p are a field where half of the nonzero values are quadratic residues. And that's true of the reals, too (the positive half are residues). With the reals, we get a lot of value from introducing a square root for one of the nonresidues (i = sqrt(-1)). Is there some value to defining a square root for one of the nonresidues mod p? I know it can't be the same value for every p, so it's probably not as useful, but I'm curious.

[gunhasirac]

Notes:
(1) If a^n ≡ 1 mod p (omitted hereafter) with n odd, then sqrt(a) ≡ a^{(1-n)/2}

(2) 18:30 If a^p ≡ 1 and p ≡ 3 mod 4, then by Euler’s criterion, a^{(p-1)/2} ≡ 1 and by (1) sqrt(a) ≡ a^{(1-n)/2} ≡ a^{(3-p)/4} ≡ a^{(1+p)/4} since a^{(p-1)/2} ≡ 1.

(3) To find the square root of -1 for the case p ≡ 1 mod 4, we observe that -1 ≡ g^{(p-1)/2} ≡ ( g^{(p-1)/4} )^2 ≡ ( g^{(p-1)/4} * g*{(p-1)/2} )^2 ( g is a primitive root) and there’s in total (p-1)/2 numbers in (Z/pZ)* that has the form: g to the power (p-1)/4 or (p-1)/4 + (p-1)/2. Hence guessing solution of square root of -1 is actually very efficient.

(4) If a^{2^m} ≡ 1, let g be a primitive root and g^{2^n * r} ≡ 1 and a = g^{2^k *s}, r, s odd. Then we have ( g^{2^k *s} )^{2^m} = g^{ 2^(k+m) *s} ≡ 1 whence r divides s and k = n - m, i.e. a ≡ g^{2^(n-m) *rt}, t odd.

Then it’s easy to check that a*g^{2^k *r} has order dividing 2^(m-1) (missing r in the video). Then sqrt(a) ≡ sqrt( a*g^{2^k *r} ) / g^{ 2^(k-1) *r } and you have an algorithm that works inductively.

In practice we first find a primitive root and calculate g^{ 2^(n-m) *r} up to g^{ 2^(n-1) *r} (just by squaring). Then calculate order of a*g^{ 2^k *r}, say 2^m’, and repeat the algorithm for 2^m’. Note that if a*g^{ 2^k *r} has order strictly smaller than 2^(m-1) then applying algorithm for 2^(m-1) will fail, so checking the order of a*g^{ 2^k *r} at every step is necessary.

(5) Finally for general a, we just solve x, y such that x*2^n + y*r = 1 and apply (1) and (4).

[VaslavTchitcherine]

24:28 Why must n be greater than m if a is a square? This seems to be true as in the following case: if p=19 and a = 18, we have ord(a)=2 so m = 1. Also, p-1=18 = 2 x 9 so n = 1, and in this case there is no number x such that x^2 = 18 mod 19.

[stevenhaker]

Around 20:52, it seems like guessing will help find a square root of -1, but not necessarily a primitive root. But around 24:40 it seems like you do treat g like it's a primitive root, so I'm a little confused. Thank you for your videos, they are great!

[nizar.lahyani]

Hello Professor, thank you very much for this course, i have just a problem with the générators of (Z/13Z)*, we found in this course 6 generators, but in the course of primitive roots we found that the number of generatos is equal to phi(p-1) that is phi(12)=4. Thank you again and excuse me for disturbance

[huaizhongr]

Is it just me wondering why at 25: 12, ag^{2^{n-m}} has order dividing 2^{m-1}? I thought you have to have (ag^{2^{n-m}})^{2^{m-1}} congruent to 1 mod p. But I cannot see why that is true. Anyone care to take a look at it?