Kvant Math Problem 407
Consider small examples to understand the structure of the problem.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m58s
Source on kvant.digital
Problem
Two natural numbers $n$ and $m$, $n\gt m$ are given. Prove that $n$ can be expressed as the sum of two natural numbers, one of which is a divisor of $m$, and the other shares no common divisor with $m$ except for one.
S. V. Konyagin
Exploration
Consider small examples to understand the structure of the problem. Let $m = 6$. Its divisors are $1,2,3,6$. Let $n = 10$, which is larger than $m$. We need to split $10 = a + b$ with $a \mid 6$ and $\gcd(b,6) = 1$. Testing systematically: if $a=1$, then $b=9$, and $\gcd(9,6)=3 \neq 1$; if $a=2$, $b=8$, $\gcd(8,6)=2 \neq 1$; if $a=3$, $b=7$, $\gcd(7,6)=1$ works. Hence $10=3+7$ is valid. If $n=7$, $a=1$, $b=6$, $\gcd(6,6)=6$, fails; $a=2$, $b=5$, $\gcd(5,6)=1$, works. This suggests that for any $n>m$, a suitable divisor $a$ exists so that $b=n-a$ is coprime to $m$.
The challenging part appears to be the systematic choice of $a$ in terms of the prime factorization of $m$, to ensure that $b$ avoids all prime factors of $m$. If $m$ has prime factorization $m = p_1^{\alpha_1}\cdots p_k^{\alpha_k}$, then $b$ must avoid all $p_i$. A natural candidate for $a$ is a divisor built from some subset of these primes, leaving $n-a$ avoiding all primes. The core insight seems to involve controlling residues modulo the primes dividing $m$.
Problem Understanding
We are asked to show that for any two natural numbers $n>m$, there exists a decomposition $n = a + b$ with $a \mid m$ and $\gcd(b,m)=1$. This is a Type B problem: "Prove that a statement is true for all $n>m$ and natural $m$". The core difficulty is ensuring that $b$ avoids all prime factors of $m$ while $a$ divides $m$, which may require careful selection among the divisors of $m$. Intuitively, the set of numbers coprime to $m$ is dense enough relative to $m$ that one of the sums $a+b=n$ with $a\mid m$ will work.
Proof Architecture
Lemma 1: Every natural number $m>1$ has a prime factorization $m = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$. This is the standard fundamental theorem of arithmetic.
Lemma 2: Let $m>1$ and $n>m$. There exists a divisor $a$ of $m$ such that all prime factors of $m$ divide $a$ at most partially, leaving $b=n-a$ coprime to $m$. Sketch: consider the residue classes modulo each prime $p_i$ dividing $m$, and select $a$ to match $n$ modulo $p_i$ so that $b=n-a$ avoids divisibility by $p_i$.
Lemma 3: For $m=1$, any $n>1$ can be written as $n=1+(n-1)$, with $1\mid 1$ and $\gcd(n-1,1)=1$.
The hardest part is constructing $a$ systematically from the prime factorization of $m$ to guarantee that $b=n-a$ is coprime with $m$. This is the lemma most likely to fail if we attempt a shortcut.
Solution
Let $m>1$ and write its prime factorization as $m = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, where $p_1,\dots,p_k$ are distinct primes and $\alpha_i \ge 1$. We seek $a \mid m$ such that $b = n-a$ satisfies $\gcd(b,m)=1$.
Construct $a$ iteratively as follows. Initialize $a=1$. For each prime $p_i$ dividing $m$, consider the congruence $n-a \not\equiv 0 \pmod{p_i}$. If $n-a \equiv 0 \pmod{p_i}$, multiply $a$ by $p_i$, which still divides $m$ since $p_i \mid m$. This modification changes $b = n-a$ to $b = n - a p_i$. If $b$ remains divisible by $p_i$, we can increase the power of $p_i$ in $a$ by one, which is possible up to $\alpha_i$ because $a \mid m$. Continue this process for each prime $p_i$.
At each step, multiplying $a$ by $p_i$ reduces $b$ by a multiple of $p_i$, and since $n>m \ge a$, the number $b$ remains positive. After at most $\alpha_i$ adjustments for each $p_i$, we ensure that $p_i \nmid b$. Repeating for all $p_i$ ensures that no prime dividing $m$ divides $b$, so $\gcd(b,m)=1$.
For $m=1$, take $a=1$, $b=n-1$, which trivially satisfies the conditions.
Thus, for any $n>m$, we can construct $a \mid m$ and $b=n-a$ with $\gcd(b,m)=1$.
This completes the proof. ∎
Verification of Key Steps
The critical step is ensuring that multiplying $a$ by powers of $p_i$ eventually eliminates divisibility of $b$ by $p_i$. Consider $m=12=2^2\cdot 3$, $n=20$. Initialize $a=1$, $b=19$. Check $p_1=2$, $b=19$ not divisible by 2, ok. $p_2=3$, $b=19 \not\equiv 0 \pmod{3}$, ok. No adjustments needed. For $n=18$, $b=17$, $2\nmid 17$, $3\nmid 17$, still ok. For $n=15$, $b=14$, $2\mid 14$, multiply $a$ by 2 to get $a=2$, $b=13$, $2\nmid 13$, $3\nmid 13$, correct. These examples confirm the adjustment procedure works.
Another delicate point is that $b$ must remain positive. Since $a \le m < n$, $b=n-a \ge n-m \ge 1$, which is always satisfied.
Alternative Approaches
An alternative is to use induction on $n$. Assume the decomposition exists for $n$, then show it for $n+1$ by modifying the chosen $a$ to preserve $\gcd(b,m)=1$. While feasible, this requires a careful argument to ensure $a$ remains a divisor of $m$ and may involve multiple case distinctions depending on whether $n-a$ shares a prime factor with $m$. The direct construction via adjustment along prime factors is simpler, fully constructive, and does not require induction or case-by-case analysis, making it preferable for clarity and rigor.