Gerry’s YAPFO Theorem on
Sum Of 2 Squares
After reading this article be sure to read the followup article explaining why 1/2 of all primes are of the “Sum of 2 Squares” variety.
.For whatever reason I seem to be fascinated with whether (or not) the terms of various formulas have prime factors in common. It is a subject of quite a few posts on this blog. Anyway…
Fermat’s theorem on Sums Of 2 Squares states that an odd prime P is expressible as
P = X2 + Y2
with X and Y integers, if and only if P = 1 (mod 4)
That is, if P-1 is divisible by 4.
5 = 12 + 22, 41 = 42 + 52, etc.
On the other hand, the primes 3, 7, 11, 19, etc. can not be expressed as the sum of 2 squares because
for them, P – 1 can not be evenly divided by 4.
Anyway, I recently stumbled into the above theorem via an excellent YouTube video on the Numberphile channel. Take a look (link below).
Does the guy in the following Numberphile video look like Max Von Sydow or what?
My initial thought was that the Sum Of 2 Squares theorem might make an interesting project with regard to which terms of the formula do (or do not) share prime factors (i.e. which terms might have prime factors in common). It would be another YAPFO project (YAPFO = Yet Another Prime Factor Oddity). Of course, I would start out by writing a program to show details for which candidate primes have terms with 1 or more prime factors in common.
P = X2 + Y2
Almost immediately it dawned on me that the “P” term could never share a prime factor with the other terms (X and Y) because P is prime, and X and Y are less than P.
The above immediately led to … Ok… so if P won’t be sharing a prime factor with either X or Y then the problem is reduced to whether or not X can share a prime factor with Y.
Ok. This could still be an interesting project with some coding. A couple of minutes later while making coffee it dawned on me that the X and Y terms could not possibly share any prime factors either. If they did share a prime factor we would end up with something like the following:
P = (Fc * Fx2 * Fx3.. * Fxn)2 + (Fc * Fy2 * Fy3.. * Fyn)2
where F? Are the prime factors of X and Y. And in particular, Fc is a prime factor common to both X and Y.
If there actually was a Fc common to both the X and Y terms then we can get the following…
P / Fc = ( Fx2 * Fx3.. * Fxn )2 + ( Fy2 * Fy3.. * Fyn )2
Non-Integer = Integer
which is a contradiction that tells us that there are no prime factors shared by both X and Y. So…Gerry’s theorem on
The Sums Of 2 Squares states that
for every odd prime P expressible as
P = X2 + Y2
There are not any prime factors common to
any of the terms for P, X, or Y.
So the whole episode was conceived as a YAPFO project but resolved itself in less than an hour so I guess we can’t really call it a “project.” Oh well. But it was still worth documenting.
Here are some related links you may want to follow:
It’s been 2 days since I first posted the above. But for some reason I kept thinking about
What portion of all primes could be expressed as
the sum of 2 squares (let’s call them “SOTS” primes):
It should be rather simple to figure this out since I already had a program I’d written called PrimeTest.exe. I used that program for an article written almost 1 year ago called “Primality Testing For Huge Integers” that you can read about here:
For PrimeTest.exe we specify a starting number, and how many numbers to examine/test. It will return summary stats about how many of the integers in that range are prime. And it will, if you want, also provide details about each of those primes in the range. It does other stuff too. Anyway, all I did was to modify the PrimeTest.exe code to:
.1. Identify which primes in the selected range could be be expressed as the sum of 2 squares ( P = X2 + Y2 ). I.e. where (P – 1) is evenly divisible by 4.
.2. At the end of each “test,” print stats on how many of the primes in the range were “SumOf2Squares” primes (SOTS primes).
1/2 of the primes are of the “SumOf2Squares” type (“SOTS” type”)
This ratio is extremely consistent across all ranges of any significant size!
I found the above extremely interesting but also very odd. Based on experience, I was expecting the number of SOTS primes to vary in some way with the natural log of the count of all primes in general or to vary with the log of the size/value of a prime(s) .
Again, 1/2 of the primes are of the SOTS variety and this is extremely consistent and varies little! But why this should be the case is a real mystery; and a very interesting one at that! Solving this mystery could make for a great project.
After reading this article be sure to read the followup article linked to just below:
As a final note, below is an example of using the PrimeTest.exe program: