If $a$, $b$, and $c$ are positive integers such that $\gcd(a,b) = 168$ and $\gcd(a,c) = 693$, then what is the smallest possible value of $\gcd(b,c)$?

Creeperhissboom
Apr 26, 2018

#1**0 **

gcd(a,b)=168- this means that a=a_{1}*168, b=b_{1}*168, where a_{1} and b_{1} are coprime.

gcd(a,c)=693, meaning that a=a_{2}*693, c=c_{1}*693, where a_{2} and c_{1} are coprime.

168=2^{3}*3*7, 693=3^{2}*7*11 gcd(168, 693)=3*7=21. Therefore gcd(b,c)>=21. To prove that 21 is the smallest possible value of gcd(b,c) i have to find an example-

a=lcm(168, 693)=5544, b=168, c=693.

check:

gcd(a,b)=gcd(5544,168)=gcd(168*33, 168)=168*gcd(33,1)=168

gcd(a,c)=gcd(5544,693)=gcd(693*8,693)=693*gcd(8,1)=693

gcd(b,c)=gcd(168,693)=21.

Guest Apr 26, 2018

edited by
Guest
Apr 26, 2018