Kvant Math Problem 782

Let $a+b=30030$ with $a,b\in \mathbb{N}$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m05s
Source on kvant.digital

Problem

Prove that if the sum of two natural numbers equals $30,030$, then their product is not divisible by $30,030$.

S. V. Fomin

Exploration

Let $a+b=30030$ with $a,b\in \mathbb{N}$. Assume for contradiction that $30030 \mid ab$. Since divisibility by a number is preserved under integer linear combinations, consider

$$(a+b)^2 - 4ab = a^2 + 2ab + b^2 - 4ab = a^2 - 2ab + b^2 = (a-b)^2.$$

Because $30030 \mid (a+b)$ and $30030 \mid ab$, it follows that $30030 \mid (a-b)^2$.

The number $30030 = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$ is squarefree, so divisibility of a square forces divisibility of the base, hence $30030 \mid (a-b)$.

Now both $a+b$ and $a-b$ are multiples of $30030$, which strongly restricts $a$ and $b$. Writing $a$ and $b$ in terms of sum and difference shows they are centered around $15015$, leading to a very rigid structure. Checking compatibility with natural numbers will determine whether any valid pair exists, and whether the assumed divisibility can actually occur.

Problem Understanding

This is a Type B problem.

We must prove that whenever two natural numbers sum to $30030$, their product cannot be divisible by $30030$.

The key difficulty is that the condition $30030 \mid ab$ interacts with the fixed sum constraint in a way that forces strong divisibility conditions on the difference $a-b$, eventually overconstraining the pair $(a,b)$.

Proof Architecture

The proof uses the identity $(a-b)^2 = (a+b)^2 - 4ab$.

First, we show that if $30030 \mid a+b$ and $30030 \mid ab$, then $30030 \mid (a-b)^2$.

Second, we use that $30030$ is squarefree, so $30030 \mid x^2$ implies $30030 \mid x$.

Third, we deduce $30030 \mid (a-b)$.

Fourth, we parametrize $a$ and $b$ via sum and difference and analyze integrality and positivity constraints.

The most delicate point is the transition from divisibility of $(a-b)^2$ to divisibility of $(a-b)$ using the squarefree structure of $30030$.

Solution

Let $a,b\in\mathbb{N}$ satisfy $a+b=30030$. Assume that $30030 \mid ab$.

Consider the identity

$$(a-b)^2 = (a+b)^2 - 4ab.$$

Since $30030 \mid (a+b)$, it follows that $30030 \mid (a+b)^2$. Since $30030 \mid ab$, it follows that $30030 \mid 4ab$. Therefore $30030$ divides their difference, hence

$$30030 \mid (a-b)^2.$$

The number

$$30030 = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$$

is a product of distinct primes. Let $p$ be any of these primes. From $30030 \mid (a-b)^2$ it follows that $p \mid (a-b)^2$, hence $p \mid (a-b)$. Since this holds for each prime divisor of $30030$, it follows that

$$30030 \mid (a-b).$$

Thus there exists an integer $k$ such that $a-b = 30030k$. Solving the system

$$a+b=30030,\quad a-b=30030k$$

gives

$$a = 15015(1+k),\quad b = 15015(1-k).$$

Since $a,b$ are natural numbers, both expressions must be positive integers. The expression for $b$ implies $1-k>0$, hence $k\le 0$.

If $k=0$, then $a=b=15015$, and

$$ab = 15015^2.$$

Since $30030 = 2\cdot 15015$, divisibility of $15015^2$ by $30030$ would require divisibility by $2$, which is impossible because $15015^2$ is odd. Hence $30030 \nmid ab$ in this case.

If $k<0$, write $k=-m$ with $m\in\mathbb{N}$. Then

$$b = 15015(1+m),$$

but the condition $b>0$ holds for all $m\ge 1$, while

$$a = 15015(1-m).$$

For $m\ge 1$, this gives $a\le 0$, contradicting the assumption that $a$ is a natural number. No such case is possible.

Thus no pair of natural numbers with sum $30030$ can satisfy $30030 \mid ab$.

This completes the proof. ∎

Verification of Key Steps

The step transforming $30030 \mid a+b$ and $30030 \mid ab$ into $30030 \mid (a-b)^2$ uses a direct algebraic identity, and both terms on the right-hand side are multiples of $30030$, so their difference is as well.

The transition from $30030 \mid (a-b)^2$ to $30030 \mid (a-b)$ relies on the prime factorization of $30030$. For any prime $p$ dividing $30030$, the condition $p \mid (a-b)^2$ forces $p \mid (a-b)$, since $p$ is prime. Applying this for all six distinct primes yields divisibility by their product.

The parametrization step is checked by direct substitution into the linear system, ensuring no arithmetic inconsistency arises in expressing $a$ and $b$.

Alternative Approaches

One alternative approach works directly modulo each prime divisor of $30030$. Assuming $30030 \mid ab$ and $a+b=30030$, one can reduce modulo $p$ for each $p\in{2,3,5,7,11,13}$ and show that $a\equiv 0$ or $b\equiv 0 \pmod p$ forces incompatible constraints across all primes simultaneously.

Another approach uses symmetry by setting $a=15015+x$, $b=15015-x$ and analyzing the condition $30030 \mid (15015^2-x^2)$, which leads to the same restriction $30030 \mid x^2$ and hence $x$ divisible by $30030$, collapsing to the same contradiction via sign constraints.