Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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)$.

Can you take it from there?

share|cite|improve this answer
p.s. The possible answers are . – Kieren MacMillan Oct 19 '14 at 19:04
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

Your Answer


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.