Let $a$, $b$, and $d$ be positive integers. It is known that $a+b$ is divisible by $d$ and $a\cdot b$ is divisible by $d^2$. Prove that both $a$ and $b$ are divisible by $d$.
Problem
Source: 2017 Polish Junior Math Olympiad Second Round
Tags: number theory
22.05.2023 21:25
Fairly easy. Let $d=\textstyle \prod_{i\le L}p_i^{e_i}$ for primes $p_1<\cdots<p_L$. It suffices to verify $v_{p_i}(a),v_{p_i}(b)\ge e_i$ for any $i$. Assume the contrary. Then there is an $i$ such that $\min\{v_{p_i}(a),v_{p_i}(b)\}\le e_i-1$. Assume wlog $v_{p_i}(a_i) \le e_i-1$. As $v_{p_i}(a\cdot b)=v_{p_i}(a)+v_{p_i}(b)\ge 2e_i$, we find that $v_{p_i}(b)>v_{p_i}(a)$, so that $v_{p_i}(a+b)=v_{p_i}(a)\le e_i-1$. This is a contradiction with $p_i^{e_i}\mid d\mid a+b$.
02.06.2023 01:08
Consider the polynomial $P(x)=x^2-\left(\frac{a+b}{d}\right )x+\frac{ab}{d^2}$. Then obviously $P\in \mathbb Z[x]$ but $\frac{a}{d}$ and $\frac{b}{d}$ are the roots of $P$ so by the rational root theorem we have $d\mid a$ and $d\mid b$.
07.10.2024 16:55
We assume that $\gcd(a, b, d) = k$, and let $a = a'k$, $b = b'k$, and $d = d'k$, where it is clear that $\gcd(a', b', d') = 1$. Now we know that $d'^2 \mid a'b'$ and $d' \mid a' + b'$. We claim that $d' = 1$. Proof: Assume that $d' > 1$. Then, there exists a prime number $p$ such that $p \mid d'$. Thus, we have $$ p \mid a'b' \rightarrow p \mid a' \text{ or } p \mid b'.$$Without loss of generality, assume $p \mid a'$. Then we have: $$ p \mid a' + b' \rightarrow p \mid b'. $$Thus, we get $p \mid a', b', d' \rightarrow p \mid \gcd(a', b', d') = 1$, which leads to a contradiction. Therefore, we conclude that $d' = 1$, which implies that $$d = k \rightarrow d = \gcd(a, b, d) \rightarrow d \mid a, b.$$The statement of the problem is thus proved.