Theorem 30: Pythagorean triples

If I asked you to give a list of mathematical theorems, I suspect that you might well think of Pythagoras‘s theorem pretty early on.  It has the rare distinction of being a theorem that’s commonly discussed (by name) in maths classes in schools today.  It should probably be a theorem of the week in its own right, but for today I’d like to focus on some rather lovely number theory associated with it.

Let’s quickly remind ourselves what Pythagoras’s theorem says.  Here’s a right-angled triangle.

The theorem says that : the square on the hypotenuse is equal to the sum of the squares on the other two sides.  There are a lot of proofs of this, but they’ll have to wait for a future post, I’m afraid!

I think that a lot of people discover, in the course of their studies of Pythagoras’s theorem at school, that there are some particularly nice right-angled triangles.  One has side lengths 3, 4, 5 (quick check: ).  Another has side lengths 5, 12, 13 (check: ).  Another has side lengths 6, 8, 10 (check: ).  Of course, these are particularly nice because the side lengths are all whole numbers (integers).  I’m going to concentrate on such solutions in this post.

This leads to lots of interesting questions.  Are there more solutions (with integer side lengths)?  How many more?  Are there infinitely many?  How can we find more solutions?  Can we find them all?  Are some more interesting than others?  Are there any interesting patterns?  How can we possibly hope to solve a single equation in three variables?  I encourage you to think about these questions before reading on.  (You could, for example, look for more solutions from yourself and see where you can go from there.)  You might also have your own questions that you’d like to consider, of course.

Theorem 29: the law of quadratic reciprocity

I think this theorem has a wonderful name.  I thought that when I first heard the name, even before I’d heard what the theorem says!  It just rolls off the tongue.  It’s also a very lovely theorem.

When I wrote about sums of squares (in my post about Lagrange’s theorem), I tried to persuade you that thinking about squares and modular arithmetic is a good idea.  In particular, we saw that a number (like 7 or 103) that leaves remainder 3 on division by 4 (is 3 (mod 4)) cannot be written as the sum of two squares, because squares are always divisible by 4 or 1 more than a multiple of 4: squares are 0 (mod 4) or 1 (mod 4).  We say that 1 is a quadratic residue (good name!) (mod 4), and that 3 is a quadratic non-residue (mod 4) (because 3 is not a square (mod 4)).  0 and 2 are not coprime to the modulus 4, so we don’t call them quadratic residues or quadratic non-residues.

How can we find the quadratic residues (mod 7), say?  We simply square each number from 0 to 6 and take the remainder on division by 7.  We don’t need to go beyond 6, because we’ll just get the same again:  (mod 7), so (mod 7) and so on.  Let’s list some quadratic residues mod various small numbers.  For each n, I’ll list , , …, , and then we can see whether we see anything interesting.  Please do check my numbers!

2: 0, 1

3: 0, 1, 1

4: 0, 1, 0, 1

5: 0, 1, 4, 4, 1

6: 0, 1, 4, 3, 4, 1

7: 0, 1, 4, 2, 2, 4, 1

8: 0, 1, 4, 1, 0, 1, 4, 1

9: 0, 1, 4, 0, 7, 7, 0, 4, 1

10: 0, 1, 4, 9, 6, 5, 6, 9, 4, 1

11: 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1

12: 0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1

13: 0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1

14: 0, 1, 4, 9, 2, 11, 8, 7, 8, 11, 2, 9, 4, 1

15: 0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1

16: 0, 1, 4, 9, 0, 9, 4, 1, 0, 1, 4, 9, 0, 9, 4, 1

17: 0, 1, 4, 9, 16, 8, 2, 15, 13, 13, 15, 2, 8, 16, 9, 4, 1

18: 0, 1, 4, 9, 16, 7, 0, 13, 10, 9, 10, 13, 0, 7, 16, 9, 4, 1

19: 0, 1, 4, 9, 16, 6, 17, 11, 7, 5, 5, 7, 11, 17, 6, 16, 9, 4, 1

20: 0, 1, 4, 9, 16, 5, 16, 9, 4, 1, 0, 1, 4, 9, 16, 5, 16, 9, 4, 1

There are lots of interesting patterns to explore there; I encourage you to look for them and try to explain them before you read on!  (I’m not going to go into most of them here, because I don’t have space in this post; I might return to them later.  I’m going to focus on just one in this post.)

As you might have already noticed, there are some particularly nice things that happen with quadratic residues to prime moduli (things that don’t necessarily happen with composite moduli).  I’d like to concentrate on prime moduli here.  I think it’ll be convenient to have lists of quadratic residues (QRs) and quadratic non-residues (QNRs) to prime moduli, written in numerical order (rather than the order in which they occur, which is what I gave above).  So here they are.

2: QRs 1

3: QRs 1; QNRs 2

5: QRs 1, 4; QNRs 2, 3

7: QRs 1, 2, 4; QNRs 3, 5, 6

11: QRs 1, 3, 4, 5, 9; QNRs 2, 6, 7, 8, 10

13: QRs 1, 3, 4, 9, 10, 12; QNRs 2, 5, 6, 7, 8 11

17: QRs 1, 2, 4, 8, 9, 13, 15, 16; QNRs 3, 5, 6, 7, 10, 11, 12, 14

19: QRs 1, 4, 5, 6, 7, 9, 11, 16, 17; QNRs 2, 3, 8, 10, 12, 13, 14, 15, 18

Perhaps that will help you see more interesting patterns (if you hadn’t already seen them).

Let’s think about linking rows.  For example, I see that 5 is a quadratic residue (mod 19).  Is 19 a quadratic residue (mod 5)?  Well, 19 = 4 (mod 5), and 4 is a quadratic residue (mod 5), so we say that 19 is a quadratic residue (mod 5).

OK, what else?  3 is not a quadratic residue (mod 17); is 17 a quadratic residue (mod 3)?  Quick check: 17 = 2 (mod 3), so 17 is not a quadratic residue (mod 3).

This is all getting a bit clumsy to write out.  Fortunately, there’s some notation that can help us: the Legendre symbol.  We write it as .  It is defined to be 1 if a is a quadratic residue (mod p), -1 if a is a quadratic non-residue (mod p), and 0 if p divides a.  (This is for prime p.  There is a generalisation, called the Jacobi symbol, that is defined for composite p, but I shan’t go into the details now.)

So we’ve seen that , and .  I suggest you try computing some more of these pairs, for practice.

Is it always the case that for primes p and q?

We can quickly see that it isn’t (if you haven’t already): , but .

Hopefully your examples showed that quite often and are the same, but sometimes they are different (which necessarily means that one is the negative of the other).  Can we be more precise about this?  Can we predict in advance when they’ll be the same and when they’ll be different?  You might like to try this for yourself, using your earlier computations and any more that you feel necessary.

A Brief History of Mathematics

I see that Marcus du Sautoy will be presenting some short programmes on a Brief History of Mathematics on BBC Radio 4 next week.  Might be  worth listening to.

Theorem 28: there are infinitely many Carmichael numbers

This week’s theorem follows from my previous posts on Fermat’s little theorem and (to a lesser extent) Wilson’s theorem.

We saw that Fermat’s little theorem tells us that if is prime and is not divisible by then .  Could we use this as a test for primality?  Wilson’s theorem gave us a criterion for a number to be prime ( is prime if and only if ), although it doesn’t give us a practical way to test whether a number is prime.  Could we get something similar from Fermat’s little theorem?

Well, how might this work?  Let’s stick to odd values of (since it’s pretty easy to check whether an even number is prime!).  We might hope that if there’s a number (not 1) so that then must be prime.  If there is such a number , we say that is a pseudoprime to the base .  But does the existence of a base to which is a pseudoprime mean that must be prime?

No.  Simple example: , so 15 is a pseudoprime to the base 4 (but certainly isn’t prime).

OK, so that didn’t work.  But if is prime then we know that for all numbers coprime to .  Suppose we know that is a pseudoprime to all bases with coprime to .  Does that mean that is prime?