Practice
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\}\).