Kvant Math Problem 888

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m11s
Source on kvant.digital

Problem

Natural numbers $a$, $b$, $c$, and $d$ satisfy the equality $ab=cd$. Prove that the number $a^{1984}+b^{1984}+c^{1984}+d^{1984}$ is composite.

A. V. Andžāns

All-Russian Mathematical Olympiad for School Students (10th, 1984)

Exploration

Let $ab=cd$. The expression is symmetric in exchanging $(a,b)$ with $(c,d)$, so a factorization should reflect this symmetry. A direct attempt is to search for a common divisor structure implied by $ab=cd$.

A natural idea is to compare prime factorizations: equality of products suggests that primes distribute between $(a,c)$ and $(b,d)$ in a controlled way. This typically leads to a parametrization where $a$ and $c$ share a gcd, and similarly for $b$ and $d$.

Let $g=\gcd(a,c)$. Writing $a=gu$ and $c=gv$ with $\gcd(u,v)=1$, the condition $ab=cd$ becomes $gu\cdot b=gv\cdot d$, hence $ub=vd$. Coprimality of $u$ and $v$ forces divisibility relations that allow further factorization of $b$ and $d$.

This suggests a complete factorization of the whole expression into a product of two symmetric sums, which would immediately imply compositeness if both factors exceed $1$.

Problem Understanding

This is a Type B problem: prove that $a^{1984}+b^{1984}+c^{1984}+d^{1984}$ is composite under the constraint $ab=cd$.

The core difficulty is to exploit the multiplicative constraint $ab=cd$ to force a nontrivial factorization of the sum of large powers. The expected mechanism is a hidden separation of variables leading to a product structure.

Proof Architecture

The proof proceeds by introducing $g=\gcd(a,c)$ and writing $a=gu$, $c=gv$ with $\gcd(u,v)=1$.

From $ab=cd$ one deduces $ub=vd$, which implies $v\mid b$ and $u\mid d$, yielding $b=vt$ and $d=ut$ for some natural $t$.

Substituting these forms into the target expression produces a complete factorization

$$a^{1984}+b^{1984}+c^{1984}+d^{1984}=(u^{1984}+v^{1984})(g^{1984}+t^{1984}).$$

The critical step is the coprimality argument ensuring the divisibility relations.

Solution

Let $g=\gcd(a,c)$. Then there exist coprime natural numbers $u$ and $v$ such that $a=gu$ and $c=gv$ with $\gcd(u,v)=1$.

Substituting into $ab=cd$ gives

$$gu\cdot b = gv\cdot d.$$

Canceling $g$ yields

$$ub = vd.$$

Since $\gcd(u,v)=1$, Euclid’s lemma implies that $v\mid b$. Hence there exists a natural number $t$ such that $b=vt$. Substituting back into $ub=vd$ gives

$$u(vt)=vd,$$

so $d=ut$.

Thus every variable has the form

$$a=gu,\quad b=vt,\quad c=gv,\quad d=ut,$$

with $\gcd(u,v)=1$.

Now compute

$$a^{1984}+b^{1984}+c^{1984}+d^{1984} = g^{1984}u^{1984} + v^{1984}t^{1984} + g^{1984}v^{1984} + u^{1984}t^{1984}.$$

Grouping terms gives

$$= g^{1984}(u^{1984}+v^{1984}) + t^{1984}(u^{1984}+v^{1984}).$$

Factoring out the common term yields

$$a^{1984}+b^{1984}+c^{1984}+d^{1984} = (u^{1984}+v^{1984})(g^{1984}+t^{1984}).$$

Both factors are natural numbers. Since $u,v\ge 1$, we have $u^{1984}+v^{1984}\ge 2$. Since $g,t\ge 1$, we have $g^{1984}+t^{1984}\ge 2$. Therefore both factors exceed $1$, and the number is composite.

Verification of Key Steps

The decisive structural step is the deduction from $ub=vd$ with $\gcd(u,v)=1$ that $v\mid b$. This follows because every prime divisor of $v$ must divide $ub$, and since it cannot divide $u$, it must divide $b$; hence all primes of $v$ divide $b$ with at least the same multiplicity, so $v\mid b$.

A second delicate point is the consistency of the parametrization. Substituting $b=vt$ and $d=ut$ back into $ab=cd$ yields $gu\cdot vt=gv\cdot ut$, which simplifies to an identity, confirming no constraints are lost.

Finally, the factorization step is verified by direct expansion, ensuring each of the four original terms appears exactly once.

Alternative Approaches

An alternative approach is to work directly with prime factorizations of $a,b,c,d$. Matching exponents across $ab=cd$ allows partitioning primes into two groups corresponding to $(a,c)$ and $(b,d)$, leading again to a hidden product structure. However, the gcd-based parametrization is more direct and avoids bookkeeping over primes while producing the factorization in a single step.