# 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$?

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.

-
Do you know Gaussian integer arithmetic? – Bill Dubuque Feb 10 '14 at 21:51
@BillDubuque I am not. I've also forgot to add that no calculus nor something similar can be used. – user26486 Feb 10 '14 at 21:54
74 is certainly a possibility. – John Habert Feb 10 '14 at 21:55
and $3$ certainly is not. – Hagen von Eitzen Feb 10 '14 at 21:55
Let $a=c$ and $b=d$. Since $74=5^2+7^2$, it is a possibility. – John Habert Feb 10 '14 at 21:58

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)$.
I'm not entirely sure how I would continue, only that the case of $\gcd=1$ is now clear. – user26486 Oct 20 '14 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 '14 at 20:52