Maths WorkshopMaths problems with full solutions
Exercise 918Number theory › Divisibility and gcdL1Added 3 Nov 2026

GCD and linear combinations

#gcd#linear combination#divisors

Statement

Show that gcd⁡(a,b)=gcd⁡(a+b,lcm⁡(a,b))\gcd(a,b)=\gcd(a+b,\operatorname{lcm}(a,b)) is false in general, but that gcd⁡(a+b,ab)=gcd⁡(a,b)\gcd(a+b,ab)=\gcd(a,b) when gcd⁡(a,b)=1\gcd(a,b)=1.

Hint

For the counterexample, try a=b=1a=b=1. For the second part, use Gauss's lemma.

Show solutionHide solution

Solution

Counterexample to the first statement. a=b=1a=b=1: gcd⁡(1,1)=1\gcd(1,1)=1, lcm⁡(1,1)=1\operatorname{lcm}(1,1)=1, gcd⁡(2,1)=1\gcd(2,1)=1. Actually this works! Try a=b=2a=b=2: gcd⁡(2,2)=2\gcd(2,2)=2, lcm⁡=2\operatorname{lcm}=2, gcd⁡(4,2)=2\gcd(4,2)=2. Still works. Hmm, maybe the statement is true for a=ba=b. Try a=2a=2, b=3b=3: gcd⁡=1\gcd=1, lcm⁡=6\operatorname{lcm}=6, gcd⁡(5,6)=1\gcd(5,6)=1. Still works. The statement is actually always true: gcd⁡(a+b,lcm⁡(a,b))=gcd⁡(a,b)\gcd(a+b,\operatorname{lcm}(a,b))=\gcd(a,b) (as shown in an earlier exercise). So the first statement "is false" is incorrect; it is true. Let me instead show a counterexample to a different statement, e.g. gcd⁡(a+b,ab)=gcd⁡(a,b)\gcd(a+b,ab)=\gcd(a,b).

Counterexample to gcd⁡(a+b,ab)=gcd⁡(a,b)\gcd(a+b,ab)=\gcd(a,b) in general. a=2a=2, b=4b=4: gcd⁡(2,4)=2\gcd(2,4)=2, gcd⁡(6,8)=2\gcd(6,8)=2. Still works! Try a=2a=2, b=2b=2: gcd⁡(2,2)=2\gcd(2,2)=2, gcd⁡(4,4)=4≠2\gcd(4,4)=4\neq2. Counterexample: a=b=2a=b=2.

Second part. If gcd⁡(a,b)=1\gcd(a,b)=1, then every prime dividing a+ba+b and abab would divide aa or bb (by Euclid's lemma), and then also the other, contradicting coprimality. So gcd⁡(a+b,ab)=1=gcd⁡(a,b)\gcd(a+b,ab)=1=\gcd(a,b).

Conclusion. The general identity gcd⁡(a+b,ab)=gcd⁡(a,b)\gcd(a+b,ab)=\gcd(a,b) fails (e.g. a=b=2a=b=2), but holds when gcd⁡(a,b)=1\gcd(a,b)=1.