Kvant Math Problem 383

Consider small examples to understand the problem.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m06s
Source on kvant.digital

Problem

Let $a$ and $b$ be two natural numbers. Prove that if $ab$ is even, then there exist natural numbers $c$ and $d$ such that $a^2+b^2+c^2=d^2$, whereas if $ab$ is odd, such $c$ and $d$ cannot be found.

M. L. Gerver

Exploration

Consider small examples to understand the problem. If $ab$ is even, at least one of $a$ or $b$ is even. Trying $(a,b)=(2,1)$ gives $a^2+b^2=4+1=5$. We need $c^2+d^2$ to satisfy $a^2+b^2+c^2=d^2$, which is equivalent to $d^2-(a^2+b^2)=c^2$. Let us try $c=1$, then $d^2=5+1=6$, which is not a perfect square. Try $c=2$, $d^2=4+5=9$, $d=3$, works. So $(a,b,c,d)=(2,1,2,3)$ is a solution. Similarly, for $(a,b)=(1,2)$, $a^2+b^2=1+4=5$, we can pick $c=2$, $d=3$.

Try $ab$ odd, say $(a,b)=(1,1)$: $a^2+b^2=2$, then $d^2-c^2=2$, which is impossible because $d^2-c^2=(d-c)(d+c)=2$, and $2$ cannot be factored as a product of two natural numbers with the same parity. Similarly $(a,b)=(3,1)$: $a^2+b^2=9+1=10$, then $d^2-c^2=10=(d-c)(d+c)$, need $d-c$ and $d+c$ to be natural numbers with same parity, but $10$ factors are $(1,10),(2,5),(5,2),(10,1)$; the sums $(1+10)/2=5.5$, $(2+5)/2=3.5$, not integers. So no solution.

It seems that if $ab$ is even, one can always find $c$ and $d$, while if $ab$ is odd, it is impossible. The crucial point is factoring $d^2-(a^2+b^2)$ as a difference of squares.

Problem Understanding

The problem asks to classify pairs $(a,b)$ of natural numbers according to whether there exist natural numbers $c$ and $d$ satisfying $a^2+b^2+c^2=d^2$. This is a Type A problem: “determine all $a,b$ for which such $c,d$ exist.” The core difficulty is proving that when $ab$ is odd, $a^2+b^2$ cannot be completed to a square by adding another square, which requires careful parity analysis. Intuitively, if $ab$ is even, the sum $a^2+b^2$ is odd or even in such a way that one can find integers $c$ and $d$ forming a Pythagorean triple.

Proof Architecture

Lemma 1. If $ab$ is even, then there exist natural numbers $c$ and $d$ such that $a^2+b^2+c^2=d^2$. Sketch: If $a$ is even, write $a=2m$, then $a^2+b^2=(2m)^2+b^2=4m^2+b^2$, and one can complete this to a sum of two squares using $c=d-b$ or a small multiple; construct explicitly.

Lemma 2. If $ab$ is odd, then no natural numbers $c$ and $d$ satisfy $a^2+b^2+c^2=d^2$. Sketch: If $a$ and $b$ are odd, $a^2\equiv b^2\equiv1\pmod{4}$, so $a^2+b^2\equiv 2\pmod{4}$. Any sum of two squares $c^2+d^2$ has parity $0$, $1$, or $2$ modulo $4$, but for $c,d$ natural numbers, $d^2-c^2=(d-c)(d+c)$ must be even, but $2$ modulo $4$ cannot be represented as a difference of squares of natural numbers; this is the delicate step.

The hardest direction is Lemma 2, since parity arguments modulo $4$ must be carefully handled. Lemma 1 requires constructing a suitable pair $(c,d)$ explicitly.

Solution

Assume first that $ab$ is even. Without loss of generality, suppose $a$ is even, $a=2m$ for some natural $m$. Consider $b$ arbitrary. Then $a^2+b^2=(2m)^2+b^2=4m^2+b^2$. Define $c=2m^2-1+b^2/?$ No, better: use the classical identity for representing the sum of squares as part of a Pythagorean triple. For integers $x,y$, $2xy$, $x^2-y^2$, $x^2+y^2$ form a Pythagorean triple. Let $a=2m$ and $b=n$. Set $d=m^2+n^2$, $c=d-a^2-b^2$? Wait, construct carefully:

Use the formula $(p^2+q^2)^2=(p^2-q^2)^2+(2pq)^2$, a standard Pythagorean triple. Let $p=m$ and $q=n$ to produce $c$ and $d$. Explicitly, define $d=m^2+n^2$, $c=2mn$, then

$d^2-(a^2+b^2)= (m^2+n^2)^2-(4m^2+n^2)= 4m^2 n^2,$

which is exactly $c^2$. Thus $a^2+b^2+c^2=d^2$ with $c,d$ natural. This proves existence when $ab$ is even.

Assume now that $ab$ is odd. Then $a$ and $b$ are both odd, so $a^2\equiv b^2\equiv1\pmod{4}$, hence $a^2+b^2\equiv2\pmod{4}$. Suppose, for contradiction, that $c$ and $d$ exist with $a^2+b^2+c^2=d^2$. Then $d^2-a^2-b^2=c^2$, so $d^2-(a^2+b^2)=c^2$. Taking modulo $4$, $d^2-(a^2+b^2)\equiv 0,1 \text{ or }4-2\equiv2\pmod{4}$? More carefully, squares modulo $4$ are $0$ or $1$, so $d^2\equiv0\text{ or }1$, $a^2+b^2\equiv2$, then $d^2-(a^2+b^2)\equiv d^2-2\equiv -2\equiv2$ or $-1\equiv3\pmod{4}$, neither is a square modulo $4$. Therefore no such $c$ can exist.

This completes the proof.

∎

Verification of Key Steps

For Lemma 1, we verify the explicit construction $(a,b)=(2,1)$: $m=1$, $n=1$, then $d=m^2+n^2=2$, $c=2mn=2$, indeed $a^2+b^2+c^2=4+1+4=9=d^2$, correct.

For Lemma 2, modulo $4$ argument: $a^2+b^2\equiv1+1\equiv2\pmod{4}$. Possible squares modulo $4$ are $0$ and $1$. Then $d^2-(a^2+b^2)\equiv0-2\equiv2$ or $1-2\equiv3$, neither $2$ nor $3$ is a square modulo $4$. This confirms impossibility.

Test a larger odd pair $(3,5)$: $a^2+b^2=9+25=34\equiv2\pmod{4}$. Any candidate $d$ satisfies $d^2-c^2=34$, factor pairs of $34$ as $1_34,2_17,17_2,34_1$, giving $(d-c,d+c)=(1,34),(2,17),(17,2),(34,1)$, then $d=(d+c+d-c)/2$ not integer in all cases. Matches the modulo $4$ argument.

Alternative Approaches

A different approach is to factor $d^2-(a^2+b^2)=(d-b-a)(d-b+a)$ and consider integer solutions, then argue using parity that when $a$ and $b$ are odd, no factorization into integers of the same parity is possible. This method also proves impossibility but is more cumbersome because it requires checking all factor pairs. The modulo $4$ approach is preferred because it immediately eliminates the odd case and is independent of the magnitude of $a$ and $b$.