Fermat's Christmas Theorem
Mike Stone
sum of two squares if all its odd prime factors are to an even power.
However, afaics this doesn't seem to apply to 441, which is the product of
3exp2 and 7exp2 - both even powers.
Am I missing something obvious?
--
Mike Stone - Peterborough, England
"Freddie experienced the sort of abysmal soul-sadness which afflicts one of
Tolstoy's Russian peasants when, after putting in a heavy day's work
strangling his father, beating his wife, and dropping the baby in the
reservoir, he turns to the cupboard only to find the vodka bottle empty".
P G Wodehouse - Jill the Reckless
Mike Stone
"Mike Stone" <mws...@aol.com> wrote in message
news:7o9uvaF...@mid.individual.net...
> I understood that FCT stated that a positive integer is expressible as the
> sum of two squares if all its odd prime factors are to an even power.
>
> However, afaics this doesn't seem to apply to 441, which is the product of
> 3exp2 and 7exp2 - both even powers.
>
> Am I missing something obvious?
>
Whoops! Should have been "- - factors of the form 4n+3 - -"
Philippe 92
>> I understood that FCT stated that a positive integer is expressible as the
>> sum of two squares if all its odd prime factors are to an even power.
>
>
>> However, afaics this doesn't seem to apply to 441, which is the product of
>> 3exp2 and 7exp2 - both even powers.
>>
>> Am I missing something obvious?
>>
Hi,
and 441 = 21^2 + 0^2, that is sum of two squares ;-)
FCT doesn't say "strictly positive".
It is strictly positive when there is at least one 4k+1 prime factor,
or the factor 2 at an odd power.
(this doesn't prevent *some* of the decompositions to have nullsquares,
for instance 15^2 = 9^2 + 12^2 *or* 15^2 + 0^2)
This is also the drawback of other related theorems about sum of
squares :
Lagrange : any number is sum of 4 squares
Gauss : all numbers not of the form (8k+7)4^n are sum of 3 squares
All these including the possibility for some of the squares to be 0^2
For instance playing with the Lagrange theorem,
56 is sum of up to 4 squares in only one way = 6^2 + 4^2 + 2^2
(as all numbers in the form 7*2^(2k+1) this decomposition is unique)
therefore, 56 is sum of 4 squares as 6^2 + 4^2 + 2^2 + 0^2
*requiring* a 0^2
This results into complicated criteria (like the details about FCT)
to say when the squares are *non null*
BTW the "FCT" (in a letter from Fermat to Mersenne on 25 December 1640)
is exactly about :
the number of ways in which a number may be sum of two squares
(including the eventual + 0^2, and not just if it is or not)
Regards.
--
Philippe C., mail : chephip, with domain free.fr
site : http://mathafou.free.fr/ (mathematical recreations)
Mike Stone
"Philippe 92" <nos...@free.invalid> wrote in message
news:mn.4c1d7d9cd...@free.fr...
Thanks.
What brought this to my attention was a little conundrum about Pythagorean
Triangles. I understand that the hypotenuse, being the sum of two squares,
is always of the form 4n+1, and never 4n+3. OK so far, but I notice that
some 4n+1 numbers - 9, 21, 33, 57, 69, 77, 81, 93 - -, are _not_ the sum of
two squares, and in every case that I've found, these numbers are ones whose
prime _factors_ are 4n+3. I can now see that 81 passes as a sum of two
squares in the same way as 441, but the others don't.
Is there some obvious reason (Obvious except to me, that is. You will gather
I am no mathematician) why a 4n+1 number which is the _product_ of two 4n+3
numbers (or the multiple of such a product) cannot be the sum of two
squares?
Philippe 92
>>> I understood that FCT stated that a positive integer is expressible
>>> are to an even power.
>>
>
> the sum of two squares, is always of the form 4n+1, and never 4n+3.
> OK so far, but I notice that some 4n+1 numbers - 9, 21, 33, 57, 69,
> 77, 81, 93 - -, are _not_ the sum of two squares, and in every case
> that I've found, these numbers are ones whose prime _factors_ are 4n+3.
> I can now see that 81 passes as a sum of two squares in the same way
> as 441, but the others don't.
> Is there some obvious reason (Obvious except to me, that is. You will
> gather I am no mathematician) why a 4n+1 number which is the
> _product_ of two 4n+3 numbers (or the multiple of such a product)
> cannot be the sum of two squares?
The problem is here in the chain :
"it is sum of two square => it is a 4k+1 number" (true, and obvious)
Which is not "it is a 4k+1 number => ..."
As you noticed not all of the N = 4k+1 are sums of two squares, and
it *is* the FCT [Fermat Christmas Theorem].
This can be understood in plenty of ways.
The most direct one is to consider prime decomposition in Z[i]
But as "not being a mathematician" this would be of little help !
To prove that, using elementary methods (without Gauss integers)
is tedious and quite long, so I won't try.
Some of the steps are however not obvious.
A 4n+3 *prime* can't obviously be the sum of two squares.
The important step is that *any* 4n+1 prime is the sum of two
squares (in only one way), and 2 = 1^2 + 1^2 also is.
One quite simple step along the proof :
- If N = a^2 + b^2 with GCD(a,b)=1, then all odd divisors
(prime or not) of N are of the form 4k+1
Proof :
To have a 4k+3 factor, it must have at least one 4n+3 *prime* factor.
Suppose N has a p = 4n+3 prime factor, and let m = 2n+1.
As GCD(a,b)=1 and p divides n, p doesn't divide a nor b.
"N multiple of p" is a^2 = -b^2 (mod p)
and because m is odd, (a^2)^m = -(b^2)^m (mod p) or
a^(2m) = - b^(2m) (mod p)
Little Fermat theorem says :
if 'a' is not a multiple of prime p, then a^(p-1) = 1 (mod p)
Here with 2m = p-1 : a^(2m) = b^(2m) = 1 (mod p)
Hence a contradiction and N can't have a 4n+3 prime factor.
We deduce of that :
- A square free number is the sum of two squares if and only
if it has only prime factors of the form 4k+1, or p=2.
The final result is FCT : (existence part)
A number is the sum of two squares if and only if all its prime
factors of the form 4k+3 have even exponents.
Then the number of ways in which N can be sum of two squares
depends only on the exponents of the 4k+1 primes.
(and for considering non null squares, on the exponent of 2)
In the case of hypothenuse of Pythagorean triangles, we want to get
the *square* of hypothenuse to be a sum of squares.
We deduce that the hypothenuse itself must have at least one 4k+1
prime factor to get a non degenerated triangle (c^2 = c^2 + 0^2 for
any c, uninterresting degenerated case).
For 4k+3 prime factors of hypothenuse, they don't care as they are
squared, hence the exponents in c^2 are always even !
A primitive pythagorean triangle must have only prime factors of the
form 4k+1 in its hypothenuse, and conversedly any product of primes of
the form 4k+1 is the hypothenuse of a primitive Pythagorean triangle.
You may get more detailed proofs (in books or on the web) about sum of
squares, but this requires a minimum mathematical skill.
A few conundrums, reflections and scripts about sum of squares
on my Website : http://mathafou.free.fr/pba_en/pb001.html
Virgil
"Philippe 92" <nos...@free.invalid> wrote:
> The final result is FCT : (existence part)
> A number is the sum of two squares if and only if all its prime
> factors of the form 4k+3 have even exponents.
Express 9 that way. Or 49. Or 121.
The 'only if' holds but the 'if' fails.
It would seem that a necessary condition is that the number have a prime
factor that is expressible as a sum of two squares, i.e., the prime 2 or
a prime of form 4k+1.
Philippe 92
Hi,
9 = 3^2 + 0^2 etc, as already said.
It is not required that the squares are non null !!!
And yes if you require non null squares, it requires the existence of
at least one 4k+1 prime factor, or an odd power of 2.
For instance 36 is only 6^2 + 0^2, just factor 2 doesn't suffice, it
requires odd power.
Jasen Betts
> I understood that FCT stated that a positive integer is expressible as the
> sum of two squares if all its odd prime factors are to an even power.
>
> However, afaics this doesn't seem to apply to 441, which is the product of
> 3exp2 and 7exp2 - both even powers.
>
> Am I missing something obvious?
that's not FCT.
also 21 exp 2 + 0 exp 2,
any number having the form given above will itself be square, or square doubled.
Virgil
"Philippe 92" <nos...@free.invalid> wrote:
> Virgil wrote :
> > In article <mn.4d2b7d9cc...@free.fr>,
> > "Philippe 92" <nos...@free.invalid> wrote:
> >
> >> The final result is FCT : (existence part)
> >> A number is the sum of two squares if and only if all its prime
> >> factors of the form 4k+3 have even exponents.
> >
> > Express 9 that way. Or 49. Or 121.
> >
> > The 'only if' holds but the 'if' fails.
> >
> > It would seem that a necessary condition is that the number have a prime
> > factor that is expressible as a sum of two squares, i.e., the prime 2 or
> > a prime of form 4k+1.
>
> Hi,
>
> 9 = 3^2 + 0^2 etc, as already said.
> It is not required that the squares are non null !!!
>
> And yes if you require non null squares, it requires the existence of
> at least one 4k+1 prime factor, or an odd power of 2.
>
> For instance 36 is only 6^2 + 0^2, just factor 2 doesn't suffice, it
> requires odd power.
As I merely said "necessary" but did not require "sufficient", my
statement was correct, if incomplete.
Stephen Horne
wrote:
>Whoops! Should have been "- - factors of the form 4n+3 - -"
I have my suspicions about old Fermat, anyway. As in he seemed to have
a few ideas where he'd left the proof in his other jacket or whatever,
and IIRC at least one was simply wrong.
Still, it worked - he'll be remembered. Fermats last theorem will no
doubt always be Fermats last theorem, whereas the guy that actually
published a proof - well, what was his name again?