Author |
Topic: Double Square (Read 921 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Double Square
« on: Nov 12th, 2007, 1:38pm » |
 Quote  Modify
|
Consider the equation x2 + y2 = 2z2; if GCD(x,y) = 1 then the solution is primitive.
For example, 72 + 172 = 2.132 is a primitive solution, whereas 22 + 142 = 2.102 is not a primitive solution.
Prove that infinitely many primitive solutions exist.
What about x2 + y2 = 3z2?
Generalise for x2 + y2 = kz2.
|
|
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Double Square
« Reply #1 on: Nov 12th, 2007, 4:13pm » |
Quote Modify
|
on Nov 12th, 2007, 1:38pm, Sir Col wrote:Consider the equation x2 + y2 = 2z2; if GCD(x,y) = 1 then the solution is primitive.
For example, 72 + 172 = 2.132 is a primitive solution, whereas 22 + 142 = 2.102 is not a primitive solution.
Prove that infinitely many primitive solutions exist.
What about x2 + y2 = 3z2?
Generalise for x2 + y2 = kz2. |
|
You're not gonna believe how long this took me.
| hidden: | We can derive the k=2 case from Pythagorean triples. Let a2 + b2 = c2 be a primitive Pythagorean triple with a > b. Then (a + b)2 + (a - b)2 = 2c2 solves your problem with k = 2.
In particular, let a = 2n2+2n, b = 2n+1, and c = 2n2+2n+1. We have
(2n2-1)2 + (2(n+1)2-1)2 = 2(n2+(n+1)2)2.
Any divisor of both 2n2-1 and 2(n+1)2-1 would also divide the sum 4n2+4n = 2 * 2 * n * (n+1). However
* 2n2-1 = -1 mod n;
* 2(n+1)2-1 = -1 mod n+1; and
* both = -1 mod 2.
Thus, 2n2-1 and 2(n+1)2-1 are coprime for all positive integers n, and the result follows. |
Not sure about the generalization yet... Interesting puzzle!
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Double Square
« Reply #2 on: Nov 12th, 2007, 4:41pm » |
Quote Modify
|
Come to think of it, k=3 is obvious.
| hidden: | | Clearly 3z2 = 0 mod 3. But, as squares are never equivalent to 2 mod 3, the only way we can have x2 + y2 = 0 mod 3 is by having both x and y divisible by 3. Thus, no primitive solutions exist; and because 3 is square-free, no solutions exist at all. |
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Double Square
« Reply #3 on: Nov 12th, 2007, 9:40pm » |
Quote Modify
|
Here's one direction for the generalization to arbitrary k.
Fermat's two squares theorem says that the equation x2+y2=n has a solution in integers x,y if and only if all prime divisors of n that are congruent to 3 mod 4 occur to an even power in the factorization of n.
From this we see that x2+y2=kz2 has a solution in integers for fixed z if and only if all prime divisors of k that are congruent to 3 mod 4 occur to an even power in its factorization.
Hence in order for there to be any primitive solutions, it is necessary that all prime divisors of k that are congruent to 3 mod 4 occur to an even power in its factorization.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Double Square
« Reply #4 on: Jan 6th, 2008, 11:31pm » |
Quote Modify
|
Are you sure this is easy? I think it would be if you changed the definition of primitive to GCD(x,y,z)=1.
But anyway, suppose there exists a primitive solution to x2+y2 = kz2. Suppose an odd prime p | k. Since (x,y)=1, WLOG p doesn't divide y, and we have (x/y)2 = -1 mod p, which means p must be 1 mod 4. So the only odd primes dividing k must be 1 mod 4. Also, k can't be divisible by 4, for otherwise both x and y would have to be even.
Now, I'm not sure if there's an easy way to show the converse:
(*) If k is not divisible by 4, nor any primes 3 mod 4, then k = a2+b2, for some relatively prime a,b.
But let's assume this for now. Note that then a,b,k are all pairwise relatively prime.
This isn't the 'easiest' solution (see below) but it's what I originally tried: Let m,n be integers, and define u,v by
u+iv = (a+ib)(m+in)2, i.e.,
u = a(m2-n2) - b(2mn),
v = b(m2-n2) + a(2mn).
Then
u2+v2=(a2+b2)(m2+n2)2 = kw2, where w = m2+n2.
Now suppose we fix n>0 and vary m, viewing u as a polynomial of degree 2 in m, with leading term a. For any prime p | k, a is non-zero mod p, so u has at most 2 roots mod p. If p>2, there must then be a 'safe' value of m mod p for which u is non-zero mod p. By the Chinese remainder theorem, there is an infinite arithmetic progression of m's for which u has no odd prime factor in common with k, and also so that m has opposite parity from n, making w odd.
Now if u,v have a common factor, it must be odd (since k isn't divisible by 4), and therefore relatively prime to k, so it divides w. So we can clear through and get a primitive solution to x2+y2=kz2. And we know that these are distinct solutions, because Arg(x+iy) = Arg(u+iv) = Arg(a+ib)+2Arg(m+in), which changes steadily as m-> .
It still remains to show (*) above. Given a primitive solution for k, and one for k', we can generate a solution for kk' by multiplying Gaussian integers, but the problem is that the new solution is not necessarily primitive. There is a straightforward solution though, but I'm not sure if it's 'easy'.
Write k = 2r  pjsj, where the pj are distinct and 1 mod 4, and r < 2. For each j fix uj,vj so that pj = uj2+vj2. Set
a + ib = (1+i)r (uj+i*vj)sj,
so that k=a2+b2. Now if some prime p|(a,b), then p2|k, so p is odd, and for some j,
p=pj = (uj+ivj)(uj-ivj).
Now, since p | (a,b), we have over the Gaussian integers that (uj-ivj) | a+ib. But (uj-ivj) is prime, and it is not associate to any of the factors in the prime factorization of a+ib above. This contradiction shows that (a,b)=1 as desired.
But given this we can solve the problem directly: first if k is odd, then put
x+iy = (a+bi)2t+1,
where a,b are as above, so that x2+y2 = k*(kt)2, and a similar argument shows that (x,y)=1. Furthermore, (x-y)2 + (x+y)2 = 2k*(kt)2, where (x-y,x+y)=1 because one of x,y is even and the other odd.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print