What is the significance of k being a multiple of 2 or 3?

[dodo]

Let p,q be two different primes from 5 onwards (not 2 or 3). Let p be the biggest of the two.

The difference of squares p^2 - q^2, since p,q are both odd, is always a multiple of 8 (easy to prove). So take the integer k = (p^2 - q^2) / 8.

It turns out that k seems to be (says friend computer) a multiple of 2 or a multiple of 3, or both. I can't find an example where k is divided neither by 2 nor by 3.

Example: p=53, q=31. p^2 - q^2 = 1848 = 8 * 231. And 231 is divisible by 3.

If p and q were not primes, but just odd and coprime, then counterexamples abound. (I use coprimes because, had they a factor in common, one could produce k as a multiple of anything.) For instance: p=45, q=31. p^2 - q^2 = 1064 = 8 * 133; and 133 is not divisible by 2 nor 3.

Any hint as of why would it work only with primes (>= 5)? Or a counterexample?

-----
EDIT: Doh, forget it. It has to do with the numbers being 6n+1 or 6n-1. (If any mod can delete this thread I would be less embarrased.)

 

[Hurkyl]

Let p,q be two different primes from 5 onwards (not 2 or 3). Let p be the biggest of the two.

The difference of squares p^2 - q^2, since p,q are both odd, is always a multiple of 8 (easy to prove). So take the integer k = (p^2 - q^2) / 8.

I'm assuming you're familiar with modular arithmetic -- any two odd numbers have the same square modulo 8.

It turns out that k seems to be (says friend computer) a multiple of 2 or a multiple of 3, or both. I can't find an example where k is divided neither by 2 nor by 3.

If k is again divisible by 2, then you are asserting any two odd primes square to the same thing modulo 16. And if k is divisible by 3, you are asserting that any two odd primes square to the same thing modulo 3.



Using modular arithmetic, it should be easy to prove that k is divisible by 3, and to find an example where k is not divisible by 2.

(aside: if m is relatively prime to n, then there are infinitely many prime numbers equivalent to m modulo n)