Wasn't proving Fermat's Little Theorem by counting necklaces really nifty! That's a very well known result -- I think even I discovered the argument many decades ago.
BUT there's another Theorem by Fermat which has an elegant proof based on counting shapes, and that proof was discovered just a few years ago, almost four centuries after the Theorem's discovery. Fermat's "Christmas" Theorem is also a key result in the evolution of number theory. Like much of Fermat's number theory, the first published proof was by Leonhard Euler. This Theorem was voted to be one of the Ten Most Beautiful Theorems of Mathematics in a survey of math teachers. It is also known as the "Fermat's Two Squares Theorem."
The theorem itself is #1:
Obviously statement #1 -- which is a true statement -- implies #2, #3, #4. I list these weaker versions of the Theorem in case we get tired, and decide to settle for a partial proof! In fact, we WILL get tired, and settle for just proving #2. Note that Zero is not an odd number, so #2 guarantees there will be at least one solution to 4k+1 = a2 + b2 whenever 4k+1 is prime. Search Youtube for "Mathologer windmill" and find a detailed complete proof. In this post I just try to entice you with an elegant counting argument.
The proof is based on Counting windmill shapes. But we needn't actually count the shapes; we simply must note whether the population is odd or even.
What is a "windmill shape"? It is a central square with four paddles attached, all with integer sides. The central square is X×X and each paddle a Y×Z rectangle with Y applying to the side flush with the square. In the image below we see TWO windmills: (X,Y,Z) = (3,7,1) and (X,Y,Z) = (5,1,3). They have the same area: 32 + 4⋅7⋅1 = 52 + 4⋅1⋅3 = 37.
But wait! These two examples are "sort of"(?) the same windmill, or rather they have the same windmill silhouette! There are TWO different ways, depending on how we pick the central square, to get the same windmill silhouette. And there will always be two ways exactly UNLESS X=Y. For the area=37 example, (X,Y,Z) = (1,1,9) is the only special case.
For area=65 there are TWO special cases: (X,Y,Z) = (1,1,16) and (X,Y,Z) = (5,5,2). But we need not worry about THAT. It can arise only because 65 is a multiple of 5, and we are concerned solely with (4k+1) which are prime.
When 4k+1 is prime, only (X,Y,Z) = (1,1,k) will NOT have a pair with the same silhouette. Since all but one are paired off, the number of windmills whose area is prime 4k+1 must be an odd number!
And now comes the step which seems nifty! We've written (4k+1) = X2 = 4⋅Y⋅Z but we are trying to express 4k+1 as the sum of two squares, NOT one square and four rectangles. So we restrict attention to the case Y=Z. Then 4k+1 = X2 + (2Y)2. Voila! Two squares.
So. We have an odd number of windmills and we want to erase all of those with Y≠Z. But (X,Y,Z) and (X,Z,Y) are two DIFFERENT windmills with the same area when Y≠Z. We don't know how many windmills we're erasing, but it will be an even number! An even minus an odd is an odd number.
Q.E.D.
BUT there's another Theorem by Fermat which has an elegant proof based on counting shapes, and that proof was discovered just a few years ago, almost four centuries after the Theorem's discovery. Fermat's "Christmas" Theorem is also a key result in the evolution of number theory. Like much of Fermat's number theory, the first published proof was by Leonhard Euler. This Theorem was voted to be one of the Ten Most Beautiful Theorems of Mathematics in a survey of math teachers. It is also known as the "Fermat's Two Squares Theorem."
The theorem itself is #1:
- Any prime of the form (4k+1) can be expressed as the sum of two squares in exactly one way.
- Any prime of the form (4k+1) can be expressed as the sum of two squares in an odd number of ways.
- Any prime of the form (4k+1) can be expressed as the sum of two squares in at least one way.
- Any prime of the form (4k+1) can be expressed as the sum of two squares in at most one way.
Obviously statement #1 -- which is a true statement -- implies #2, #3, #4. I list these weaker versions of the Theorem in case we get tired, and decide to settle for a partial proof! In fact, we WILL get tired, and settle for just proving #2. Note that Zero is not an odd number, so #2 guarantees there will be at least one solution to 4k+1 = a2 + b2 whenever 4k+1 is prime. Search Youtube for "Mathologer windmill" and find a detailed complete proof. In this post I just try to entice you with an elegant counting argument.
The proof is based on Counting windmill shapes. But we needn't actually count the shapes; we simply must note whether the population is odd or even.
What is a "windmill shape"? It is a central square with four paddles attached, all with integer sides. The central square is X×X and each paddle a Y×Z rectangle with Y applying to the side flush with the square. In the image below we see TWO windmills: (X,Y,Z) = (3,7,1) and (X,Y,Z) = (5,1,3). They have the same area: 32 + 4⋅7⋅1 = 52 + 4⋅1⋅3 = 37.
But wait! These two examples are "sort of"(?) the same windmill, or rather they have the same windmill silhouette! There are TWO different ways, depending on how we pick the central square, to get the same windmill silhouette. And there will always be two ways exactly UNLESS X=Y. For the area=37 example, (X,Y,Z) = (1,1,9) is the only special case.
For area=65 there are TWO special cases: (X,Y,Z) = (1,1,16) and (X,Y,Z) = (5,5,2). But we need not worry about THAT. It can arise only because 65 is a multiple of 5, and we are concerned solely with (4k+1) which are prime.
When 4k+1 is prime, only (X,Y,Z) = (1,1,k) will NOT have a pair with the same silhouette. Since all but one are paired off, the number of windmills whose area is prime 4k+1 must be an odd number!
And now comes the step which seems nifty! We've written (4k+1) = X2 = 4⋅Y⋅Z but we are trying to express 4k+1 as the sum of two squares, NOT one square and four rectangles. So we restrict attention to the case Y=Z. Then 4k+1 = X2 + (2Y)2. Voila! Two squares.
So. We have an odd number of windmills and we want to erase all of those with Y≠Z. But (X,Y,Z) and (X,Z,Y) are two DIFFERENT windmills with the same area when Y≠Z. We don't know how many windmills we're erasing, but it will be an even number! An even minus an odd is an odd number.
Q.E.D.
