Solve the Challenge: Prime Pair Sum Always Divisible by 12

[Tyger]

Who will be the first to prove that (with one exception) the sum of any Prime Pair is always divisible by twelve?

 

[marcus]

Originally posted by Tyger
Who will be the first to prove that (with one exception) the sum of any Prime Pair is always divisible by twelve?

The first prime pair I happened to think of was 29 and 31
and they add up to 60 which is divisible by 12.

then I stopped to think...hey, I'm not any good at number theory. I think you have proved some result, but not me (except for very easy things as amusement with my son when he was young.)

Another prime pair is 11 and 13------adds up to 24 also divisible by 12.

How come I never heard of this?

I hope someone else knows the proof, or can figure one out.


I see why the sum must be divisible by 6, but not yet why by twelve.

By six:
obviously by 2 since two odd numbers
but neither p nor p+2 is div by 3
therefore p+1 must be div by 3
and the sum = 2p + 2 is divisible by p +1 and therefore by 3.

Maybe I will see why by 12 in a minute, but I will post this
immediately and someone else can have a go

Rats, of course divisble by 12
since p+1 is even
therefore since sum is 2(p + 1) it is div by 4
and since already know div by 3
it must be by 12

 

[Hurkyl]

And the exception is (3, 5). Yay, I finished the proof!

 

[Tyger]

Very good marcus.

Perhaps I should come up with some more teasers.

A couple of years ago I had some very bad flu, not debilitating but hung on for a long time and I was looking for a puzzle to make sure my brain was still working. I fiddled around and found that if a number could be represented as the sum of two squares its factors could also be represented that way. Checked it up to n=1,000 and decided to prove it. Wasn't very difficult, only had to think about it three times. My usual way to solve problems involves working with pencil and paper a little till some kind of progress is made then going on to other things. I usualy wake up at about three in the morning with another part worked out in my head, think about it a little more, maybe hit pencil and paper in the daytime, and a couple of nights later find another part. So I largely do it at a subconsious level and it involves putting the problem in my imagination, and the answer may arrive at the oddest times.

BTW the sum of squares problem was solved long ago by Euler and Fermat, but my proof involved complex notation and made it easier to see how many different ways a number could be so represented.

 

[marcus]

My hunch is that Hurkyl is a bit more in training than I and also that it is his turn.

Maybe you should give an example of what you mean re: sum of squares.

Like...25 = 9+16

So its factors are 25 and 5 and 1
and 5 = 4+1


And...41 = 16 + 25
and its only factors are 1, and 41
and each of them is trivially a sum of squares, considering that 0 is a square.

If Euler and Fermat both proved it, it must be a class act.
I would be cautious about even trying.

Originally posted by Tyger
Perhaps I should come up with some more teasers.

A couple of years ago I had some very bad flu, not debilitating but hung on for a long time and I was looking for a puzzle to make sure my brain was still working. I fiddled around and found that if a number could be represented as the sum of two squares its factors could also be represented that way. Checked it up to n=1,000 and decided to prove it. Wasn't very difficult, only had to think about it three times. My usual way to solve problems involves working with pencil and paper a little till some kind of progress is made then going on to other things. I usualy wake up at about three in the morning with another part worked out in my head, think about it a little more, maybe hit pencil and paper in the daytime, and a couple of nights later find another part. So I largely do it at a subconsious level and it involves putting the problem in my imagination, and the answer may arrive at the oddest times.

BTW the sum of squares problem was solved long ago by Euler and Fermat, but my proof involved complex notation and made it easier to see how many different ways a number could be so represented.

 

[Tyger]

Some examples

65= 8²+1², factors are 13=2²+3², and 5=2²+1² It can also be represented as 49+16.

85=9²+2², factors are 5 and 17=4²+1²

I doubt if Euler of Fermat had to think about it much at all, they probably just wrote the answer out.

OK Hurkyl, do you want to pose a puzzle?

 

[Hurkyl]

Hrm, I must be misunderstanding the puzzle... consider 45:

45 = 3^2 + 6^2

But 3 is a factor of 45, and 3 is not the sum of two squares.

 

[marcus]

Originally posted by Hurkyl
Hrm, I must be misunderstanding the puzzle... consider 45:

45 = 3^2 + 6^2

But 3 is a factor of 45, and 3 is not the sum of two squares.

3 and 6 are not relatively prime

I wonder if there is a fact here

Tyger and I happened to give some examples
where the two summands were relatively prime
and what he said happens did happen

do you have another counterexample

 

[Hurkyl]

The common factor was a crucial point to my method of producing a counterexample; the same trick will work for any other non sum of square number, for instance 7 also yields 7^2 + 14^2 as a counterexample.


I have seen the converse of this question proved before: the product of sums of squares is a sum of squares; let me see if I can still prove it:


(a^2 + b^2)(c^2 + d^2) = a^2 c^2 + a^2 d^2 + b^2 c^2 + b^2 d^2
= (a^2 c^2 + 2abcd + b^2 d^2) + (a^2 d^2 - 2abcd + b^2 c^2)
= (ac + bd)^2 + (ad - bc)^2