Quadratic residues

Factual Questions
1

I’m reading about them in “What is mathematics?” and I just can’t get it. Can anyone explain them in a simple manner, with examples?

2

  1. Modular Arithmetic
    When working modulo an integer, we ignore multiples of that integer. This is easier to grasp with examples, so let’s work modulo 5. In this case we only have 5 numbers to work with: 0, 1, 2, 3 and 4. To perform any calculation mod 5, work it out as normal and throw out all multiples of 5, to leave only the remainder. For example,
    3 + 4 = 2, as 3 + 4 = 7 in normal arithmetic, and the remainder when 7 is divided by 5 is 2.
    1 + 4 = 0
    3 [symbol]´[/symbol] 4 = 2 ( the remainder when 12 is divided by 5)
    2 [symbol]´[/symbol] 3 = 1

  2. Quadratic Residues
    Let’s look at the integers mod 3, now. In particular, we can work out the squares of each of the integers.
    0[sup]2[/sup] = 0
    1[sup]2[/sup] = 1
    2[sup]2[/sup] = 1 ( the remainder when 4 is divided by 3)

So, of the three possibilities 0, 1 and 2, two of them ( namely 0 and 1) can be represented as square numbers, and the other ( 2) can’t.

Let’s carry out the same calculations mod 5:
0[sup]2[/sup] = 0
1[sup]2[/sup] = 1
2[sup]2[/sup] = 4
3[sup]2[/sup] = 4
4[sup]2[/sup] = 1

This time, there are three numbers ( 0, 1 and 4) that can be expressed as square numbers, and 2 ( 2 and 3) that can’t.

Now we should mention two conventions. In this context, we normally work with a modulus that is a prime number. Also, we ignore the number 0. We can now say that in each of the two cases above, half of the non-zero integers can be written as square numbers ( i.e. 1 out of 2 in the first case and 2 out of 4 in the second) and half cannot.

We call those non-zero numbers which can be written as square numbers in arithmetic modulo p ( a prime number) the quadratic residues mod p, and those that cannot the quadratic non-residues mod p. Thus from the above, we see that
1 is a quadratic residue mod 3 and 2 is a quadratic non-residue mod 3
1 and 4 are quadratic residues mod 5, and 2 and 3 are quadratic non-residues mod 5.

We can show that, for every odd prime number p, exactly half of the numbers 1, 2, …, p-1 are quadratic residues mod p, and half are non-residues.

3

So far so good. If p is prime, then exactly half the numbers 1,2,3,…,p-1 are quadratic residues (QR) mod p and the other half are called quadratic non-residues (QNR) mod p. (Why not non-quadratic residues? I don’t know.) To continue, mod 7, 1,2,4 are QR and 3,5,6 are QNR. But it is slightly misleading to stick to the numbers between 1 and p-1. We also say that 8,9,11,15,16,18,22… are QR and that 10,12,13,17,19,20,24… are QNR. This leads to the following amazing discovery. Suppose p and q are distinct primes. So neither divides the other. You can ask if p is a QR of q and if q is a QR of p. Gauss proved (although earlier mathematicians, notably Lagrange, had actually observed this and tested it for lots of values, but Gauss gave the first proof) that there were essentially two cases to consider. Forget the prime 2 (which is exceptional in the sense that there is only one non-zero residue and that is 1 which is evidently a QR mod 2). Suppose p and q are distinct odd primes. If either one has the form 4k + 1 then either p is a QR mod q and q is a QR mod p or else p is a QNR mod p and p is a QNR mod q. The second case is that both primes leave a remanider of 3 when divided by 4 (such as 7 and 11). In that case either p is a QR mod q and q is a QNR mod p or else p is a QNR mod q and q is a QR mod p.

Let me give some examples.

=================
One prime =1 mod 4 and the other one =3 mod 4:

13 and 19. In this case 13 is a QNR mod 19 and 19 is a QNR mod 13.

13 and 23. Each is a QR mod the other.

Both primes = 3 mod 4:

11 and 19. 11 is a QR mod 19 and 19 is a QNR mod 11.

Using Gauss’s “law of quadratic reciprocity” and certain other more easily proved theorems, it is easy to draw these conclusions without actually calculating, even for 100 or 1000 digit primes.

I believe that Gauss was so taken with this result that he published I think 8 distinct proofs. When I was in grad school one of my profs published a paper titled, “The 151st proof of quadratic reciprocity”.