Chapter
Theory
The GCD measures the common part of two numbers, while the LCM is the smallest number containing both structures as divisors. In olympiad problems, the GCD is not just something to compute; common divisors can be moved between expressions.
The Euclidean algorithm is based on \(\gcd(a,b)=\gcd(b,a-b)\), and more strongly on \(\gcd(a,b)=\gcd(b,r)\), where \(r\) is the remainder when \(a\) is divided by \(b\).
If two expressions depend on \(n\), try subtracting one from the other or forming a linear combination to lower the degree. Often the GCD divides a small constant.
If the GCD and LCM of two numbers are given, write \(a=dx\), \(b=dy\), \(\gcd(x,y)=1\). Then the LCM is \(dxy\).
Examples
We learn to reduce a pair of numbers without full factorisation.
Problem. Find \(\gcd(252,198)\).
\(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=18\). The answer is \(18\).
Comment. At each step, replace the larger number by its remainder upon division by the smaller one.
Minimum and maximum exponents give the GCD and LCM.
Problem. Find \(\gcd(84,126)\) and \(\operatorname{lcm}(84,126)\).
\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\). Therefore \(\gcd(84,126)=2\cdot3\cdot7=42\), while \(\operatorname{lcm}(84,126)=2^2\cdot3^2\cdot7=252\).
Comment. The GCD takes smaller exponents; the LCM takes larger ones.
The relation \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) often finds an unknown number immediately.
Problem. Find \(n\) if \(\gcd(n,70)=14\) and \(\operatorname{lcm}(n,70)=420\).
For two positive numbers, \(n\cdot70=\gcd(n,70)\operatorname{lcm}(n,70)\). Hence \(70n=14\cdot420\), so \(n=84\). Check: \(\gcd(84,70)=14\), \(\operatorname{lcm}(84,70)=420\).
Comment. The formula applies to exactly two numbers.
A common divisor often divides a small constant.
Problem. Prove that \(\gcd(n^2+1,n+3)\) divides \(10\).
Let \(d=\gcd(n^2+1,n+3)\). Then \(n\equiv -3\pmod d\), so \(n^2+1\equiv 9+1=10\pmod d\). Since \(d\mid n^2+1\), we get \(d\mid10\).
Comment. This is the main move for problems of the form \(\gcd(f(n),g(n))\).
The simplest example of a GCD equal to one.
Problem. Prove that \(\gcd(n,n+1)=1\).
Any common divisor of \(n\) and \(n+1\) divides their difference \((n+1)-n=1\). Hence the only possible common divisor is \(1\).
Comment. The difference of consecutive numbers is the shortest route.
This is one of the most frequently used facts in number theory.
Problem. Let \(\gcd(a,b)=1\) and \(a\mid bc\). Prove that \(a\mid c\).
All prime factors of \(a\) are absent from \(b\), since \(\gcd(a,b)=1\). But \(bc\) is divisible by \(a\), so all prime factors of \(a\), with their needed powers, must occur in \(c\). Therefore \(a\mid c\).
Comment. Later this becomes a precise tool in congruences.
The Euclidean algorithm can be applied to exponents.
Problem. Find \(\gcd(2^{18}-1,2^{30}-1)\).
Use \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Since \(\gcd(18,30)=6\), we get \(2^6-1=63\).
Comment. The formula can be proved by Euclid: \(a^m-1\) is divisible by \(a^d-1\) when \(d\mid m\).
Sometimes the GCD of a whole family is visible from a common factor.
Problem. Find the GCD of all six-digit numbers of the form \(\overline{abcabc}\).
Such a number equals \(1000\cdot\overline{abc}+\overline{abc}=1001\cdot\overline{abc}\). Hence all such numbers are divisible by \(1001\). On the other hand, among three-digit blocks there are coprime ones, for example \(100\) and \(101\), so no extra common factor is forced. The GCD of the whole family is \(1001\).
Comment. This is not a computation for one pair, but a GCD of a family.
Problems
Find \(\gcd(252,198)\) using the Euclidean algorithm.
Repeatedly replace the larger number by the remainder.
\(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=18\). The answer is \(18\).
Find \(\gcd(84,126)\) and \(\operatorname{lcm}(84,126)\).
Factorise both numbers.
\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\). Hence \(\gcd=2\cdot3\cdot7=42\), \(\operatorname{lcm}=2^2\cdot3^2\cdot7=252\).
Let \(a=96\), \(b=180\). Verify \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\).
Find the GCD and LCM by factorisation.
\(96=2^5\cdot3\), \(180=2^2\cdot3^2\cdot5\). Thus \(\gcd=2^2\cdot3=12\), \(\operatorname{lcm}=2^5\cdot3^2\cdot5=1440\). We get \(96\cdot180=17280\) and \(12\cdot1440=17280\).
Prove that \(\gcd(n,n+1)=1\) for every integer \(n\).
A common divisor divides the difference.
If \(d\mid n\) and \(d\mid n+1\), then \(d\mid(n+1)-n=1\). Hence \(d=1\). Therefore \(\gcd(n,n+1)=1\).
Prove that \(\gcd(n,2n+1)=1\) for every integer \(n\).
Subtract \(2n\) from \(2n+1\).
Any common divisor \(d\) of \(n\) and \(2n+1\) divides \(2n\), hence divides \((2n+1)-2n=1\). Therefore \(d=1\), so the GCD is \(1\).
For positive \(n\), find \(\gcd(48n,180n)\) and \(\operatorname{lcm}(48n,180n)\).
Factor out the common factor \(n\).
\(\gcd(48,180)=12\), \(\operatorname{lcm}(48,180)=720\). Since both numbers are multiplied by \(n\), we get \(\gcd(48n,180n)=12n\) and \(\operatorname{lcm}(48n,180n)=720n\).
Find positive \(n\) if \(\gcd(n,90)=18\) and \(\operatorname{lcm}(n,90)=630\).
Use \(90n=\gcd(n,90)\operatorname{lcm}(n,90)\).
We have \(90n=18\cdot630\), so \(n=126\). Check: \(\gcd(126,90)=18\), \(\operatorname{lcm}(126,90)=630\), so the answer is correct.
Prove that \(\gcd(n,n+2)\) divides \(2\). Determine this GCD for even and odd \(n\).
A common divisor divides the difference \(2\).
Let \(d=\gcd(n,n+2)\). Then \(d\mid(n+2)-n=2\), so \(d\in\{1,2\}\). If \(n\) is even, both numbers are even and the GCD is \(2\). If \(n\) is odd, both numbers are odd, so they do not share the divisor \(2\), and the GCD is \(1\).
Prove that \(\gcd(n^2+n+1,n)=1\) for every positive \(n\).
Subtract \(n(n+1)\) from \(n^2+n+1\).
If \(d\mid n\) and \(d\mid n^2+n+1\), then \(d\mid n(n+1)\). Hence \(d\) divides the difference \((n^2+n+1)-n(n+1)=1\). Thus \(d=1\).
Let \(\gcd(a,b)=1\). Prove that \(\gcd(a+b,a-b)\) divides \(2\).
A common divisor of the sum and difference divides their sum and difference.
Let \(d\mid a+b\) and \(d\mid a-b\). Then \(d\mid (a+b)+(a-b)=2a\) and \(d\mid(a+b)-(a-b)=2b\). Since \(\gcd(a,b)=1\), no odd prime can divide \(d\). Therefore \(d\mid2\).
Find all integers \(n\) for which \(\gcd(n+2,n^2+3n+5)>1\).
Reduce the second expression modulo \(n+2\).
Modulo \(n+2\), we have \(n\equiv -2\). Then \(n^2+3n+5\equiv4-6+5=3\). Therefore \(\gcd(n+2,n^2+3n+5)=\gcd(n+2,3)\). It is greater than \(1\) exactly when \(3\mid n+2\), i.e. \(n\equiv1\pmod3\).
Find positive \(n\) if \(\gcd(n,36)=12\) and \(\operatorname{lcm}(n,36)=180\).
Use the product of the GCD and LCM.
\(36n=12\cdot180\), so \(n=60\). Check: \(\gcd(60,36)=12\), \(\operatorname{lcm}(60,36)=180\). The answer is \(60\).
Let \(\gcd(a,b)=1\). Prove that \(\gcd(a+b,ab)=1\).
If a prime \(p\) divides \(ab\), then it divides \(a\) or \(b\).
Suppose a prime \(p\) divides both \(a+b\) and \(ab\). From \(p\mid ab\), we get \(p\mid a\) or \(p\mid b\). If \(p\mid a\), then from \(p\mid a+b\), we get \(p\mid b\), contradicting \(\gcd(a,b)=1\). The case \(p\mid b\) is similar. Thus there are no common prime divisors, and the GCD is \(1\).
Find all integers \(n\) for which \(\gcd(n^2+1,n+3)>1\).
Show that this GCD equals \(\gcd(10,n+3)\).
Modulo \(n+3\), we have \(n\equiv -3\), so \(n^2+1\equiv10\). Hence \(\gcd(n^2+1,n+3)=\gcd(10,n+3)\). This GCD is greater than \(1\) if \(n+3\) is divisible by \(2\) or by \(5\). Thus \(n\) is odd or \(n\equiv2\pmod5\).
Prove that \(\gcd(n^2+n+1,n-1)\mid3\). When is this GCD equal to \(3\)?
Modulo \(n-1\), replace \(n\) by \(1\).
Modulo \(n-1\), we have \(n\equiv1\). Then \(n^2+n+1\equiv1+1+1=3\). Therefore the GCD is \(\gcd(n-1,3)\), so it divides \(3\). It equals \(3\) exactly when \(3\mid n-1\), i.e. \(n\equiv1\pmod3\).
Find \(\gcd(2^{18}-1,2^{30}-1)\).
Use \(\gcd(18,30)=6\).
For numbers of the form \(a^m-1\), \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Hence the required GCD is \(2^6-1=63\).
Prove: if \(\gcd(a,b)=1\), then \(\gcd(a^m,b^n)=1\) for all positive \(m,n\).
Compare the prime divisors of \(a\) and \(b\).
If a prime \(p\) divides \(a^m\), then \(p\mid a\). If the same \(p\) divided \(b^n\), then \(p\mid b\), contradicting \(\gcd(a,b)=1\). Thus \(a^m\) and \(b^n\) have no common prime divisors, and their GCD is \(1\).
Let \(\gcd(a,b)=1\). Prove that \(\gcd(a^2+b^2,a+b)\mid2\).
Modulo \(a+b\), replace \(a\) by \(-b\).
Let \(d=\gcd(a^2+b^2,a+b)\). Then \(a\equiv -b\pmod d\), so \(a^2+b^2\equiv2b^2\pmod d\). Hence \(d\mid2b^2\). But \(\gcd(a+b,b)=\gcd(a,b)=1\), so \(\gcd(d,b)=1\). Therefore \(d\mid2\).
Find all positive \(n\) such that \(\gcd(n^2+4,n+6)>1\).
Reduce \(n^2+4\) modulo \(n+6\).
Modulo \(n+6\), we have \(n\equiv -6\), so \(n^2+4\equiv36+4=40\). Thus the GCD is \(\gcd(n+6,40)\). It is greater than \(1\) if \(n+6\) is divisible by \(2\) or \(5\). Therefore \(n\) is even or \(n\equiv4\pmod5\).
Find the exact value of \(\gcd(n^2+n+1,n^2+2n+3)\) depending on the integer \(n\).
Subtract the first expression from the second.
Let \(d=\gcd(n^2+n+1,n^2+2n+3)\). Then \(d\mid(n^2+2n+3)-(n^2+n+1)=n+2\). Modulo \(d\), we have \(n\equiv-2\), so from \(d\mid n^2+n+1\), we get \(d\mid4-2+1=3\). Hence \(d\) is \(1\) or \(3\). Both expressions are divisible by \(3\) exactly when \(n\equiv1\pmod3\). Therefore the GCD is \(3\) for \(n\equiv1\pmod3\), and \(1\) otherwise.
Prove that for integer \(a>1\) and positive \(m,n\),
\[\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1.\]
Run the Euclidean algorithm on the exponents: if \(m=qn+r\), then \(a^m-1\) modulo \(a^n-1\) is related to \(a^r-1\).
Let \(m\ge n\) and \(m=qn+r\). Since \(a^n\equiv1\pmod{a^n-1}\), we have \(a^m=a^{qn+r}\equiv a^r\pmod{a^n-1}\). Therefore \(\gcd(a^m-1,a^n-1)=\gcd(a^r-1,a^n-1)\). This is exactly the Euclidean step for the exponent pair \((m,n)\). Repeating, we reach \(d=\gcd(m,n)\). The GCD is \(a^d-1\).
Find all unordered pairs of positive integers \((a,b)\) such that \(\gcd(a,b)=12\) and \(\operatorname{lcm}(a,b)=720\).
Set \(a=12x\), \(b=12y\), where \(\gcd(x,y)=1\).
Let \(a=12x\), \(b=12y\), \(\gcd(x,y)=1\). Then \(\operatorname{lcm}(a,b)=12xy=720\), so \(xy=60\). Since \(x\) and \(y\) are coprime, each prime power of \(60=2^2\cdot3\cdot5\) goes entirely to either \(x\) or \(y\). The unordered pairs \((x,y)\) are \((1,60)\), \((3,20)\), \((4,15)\), \((5,12)\). Hence the pairs \((a,b)\) are \((12,720)\), \((36,240)\), \((48,180)\), \((60,144)\).
Three positive perfect cubes are divisible by \(18\). What is the smallest possible value of their common GCD?
If a cube is divisible by \(2\cdot3^2\), what are the smallest possible exponents of \(2\) and \(3\) in it?
In a perfect cube, all prime exponents are multiples of \(3\). For a cube to be divisible by \(18=2\cdot3^2\), the exponent of \(2\) must be at least \(3\), and the exponent of \(3\) must also be at least \(3\). Hence every such cube is divisible by \(2^3\cdot3^3=216\). This value is attainable: take all three cubes equal to \(216=6^3\). Therefore the smallest possible GCD is \(216\).
Find two positive integers \(a,b\) if \(a+b=154\) and \(\operatorname{lcm}(a,b)=840\).
First prove that \(\gcd(a,b)=\gcd(a+b,\operatorname{lcm}(a,b))\).
Let \(d=\gcd(a,b)\), \(a=dx\), \(b=dy\), where \(\gcd(x,y)=1\). Then \(\operatorname{lcm}(a,b)=dxy\), and \(a+b=d(x+y)\). Since \(\gcd(x+y,xy)=1\), we get \(\gcd(a+b,\operatorname{lcm}(a,b))=d\). Therefore \(d=\gcd(154,840)=14\).
Then \(a=14x\), \(b=14y\), \(x+y=11\), and \(\operatorname{lcm}(a,b)=14xy=840\), so \(xy=60\). The numbers \(x,y\) are roots of \(t^2-11t+60=0\), giving \(\{x,y\}=\{5,6\}\). Hence \(\{a,b\}=\{70,84\}\).
Ladders