Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $a,b,c,d\in\mathbb N$ and $a^2+b^2\mid ac+bd$, can it be true that $\gcd(a^2+b^2,c^2+d^2)=1$? or $3$? or $74$?

That problem is complicated. I've tried some approaches, but they're useless. E.g. if $$\gcd(a^2+b^2,c^2+d^2)=1$$ Then $$\gcd((a^2+b^2)(c^2+d^2),ac+bd)=\gcd(a^2+b^2,ac+bd)\gcd(c^2+d^2,ac+bd)$$ So it would be sufficient to show that this equality can't hold. But it won't work.

Also, if $\gcd(a,b)=1$, then $\gcd(a+b,a^2+b^2)=1$ or $2$. So it'd also be sufficient to prove that it can't be true that $$\gcd(a^2+b^2+c^2+d^2,(a^2+b^2)^2+(c^2+d^2)^2)$$ is $1$ or $2$, but you can see how desperate proving this would actually be.

I'm curious to see a solution. I'll see if you could think of one.

And it's a problem from the selection of people for the IMO $2013$ phase (not sure how to say it). I can't find a solution on the Internet. I think knowing how to solve this problem could help me in the future, so I've posted it here.

Thanks.

share|improve this question
1  
Do you know Gaussian integer arithmetic? –  Bill Dubuque Feb 10 at 21:51
    
@BillDubuque I am not. I've also forgot to add that no calculus nor something similar can be used. –  mathh Feb 10 at 21:54
    
74 is certainly a possibility. –  John Habert Feb 10 at 21:55
    
and $3$ certainly is not. –  Hagen von Eitzen Feb 10 at 21:55
    
How can you tell? I'd like to see how you've found that out. –  mathh Feb 10 at 21:57

1 Answer 1

We have the identity $$ b^2\bigl((a^2+b^2)-(c^2+d^2)\bigr) = (a^2+b^2)(c^2-b^2) - (ac-bd)(ac+bd). $$ Hence $(a^2+b^2) \mid (ac+bd)$ forces $(a^2+b^2) \mid b^2(c^2+d^2)$. Since $a^2+b^2 > b^2$ for all $a,b \in \mathbb{N}$, we must have $\gcd(a^2+b^2,c^2+d^2)>1$. Furthermore, $\gcd(a^2+b^2,b^2)$ must divide $a^2\!$, so any prime $p$ involved must divide $\gcd(a,b)$, and hence $p^2 \mid (a^2+b^2)$.

Can you take it from there?

share|improve this answer
    
p.s. The possible answers are oeis.org/A000404 . –  Kieren MacMillan Oct 19 at 19:04
    
I'm not entirely sure how I would continue, only that the case of $\gcd=1$ is now clear. –  mathh Oct 20 at 18:26
    
@mathh: Now apply Fermat's theorem on numbers (esp. primes) which are the sum of two squares, and consider whether $3$ or $74$ are of that form. –  Kieren MacMillan Oct 20 at 20:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.