Maths WorkshopMaths problems with full solutions
Exercise 740Number theory › Divisibility and gcdL1Added 2 Nov 2026

A divisibility identity for a sum

#divisibility#linearity#sum

Statement

Show that \divisibility(a+b,lcm⁡(a,b))=\divisibility(a,b)\divisibility(a+b,\operatorname{lcm}(a,b))=\divisibility(a,b) for all positive integers a,ba,b.

Hint

Write a=δa′a=\delta a', b=δb′b=\delta b' with \divisibility(a′,b′)=1\divisibility(a',b')=1. Then lcm⁡=δa′b′\operatorname{lcm}=\delta a'b' and a+b=δ(a′+b′)a+b=\delta(a'+b').

Show solutionHide solution

Solution

Reduction. Let δ=\divisibility(a,b)\delta=\divisibility(a,b), a=δa′a=\delta a', b=δb′b=\delta b', \divisibility(a′,b′)=1\divisibility(a',b')=1. Then
a+b=δ(a′+b′),lcm⁡(a,b)=δa′b′.a+b=\delta(a'+b'),\qquad \operatorname{lcm}(a,b)=\delta a'b'.
So
\divisibility(a+b,lcm⁡(a,b))=δ⋅\divisibility(a′+b′,a′b′).\divisibility(a+b,\operatorname{lcm}(a,b))=\delta\cdot\divisibility(a'+b',a'b').

Coprimality. Since \divisibility(a′,b′)=1\divisibility(a',b')=1, any prime dividing a′b′a'b' divides exactly one of a′,b′a',b', hence cannot divide a′+b′a'+b'. Therefore \divisibility(a′+b′,a′b′)=1\divisibility(a'+b',a'b')=1.

Conclusion. \divisibility(a+b,lcm⁡(a,b))=δ=\divisibility(a,b)\divisibility(a+b,\operatorname{lcm}(a,b))=\delta=\divisibility(a,b).