+0  
 
0
39
1
avatar

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

 Apr 16, 2022

Best Answer 

 #1
avatar+9369 
+1

Note that \(168|a\) and \(88|a\) by the property of gcd.

 

Take \(a = \operatorname{lcm}(168, 88) = 1848\).

Then \(b = 168\) and \(c = 88\) satisfies the conditions. You can check that gcd(b, c) is minimum in this case because for any positive integers \(k,l\)\(\gcd(kb, lc) = \gcd(k, l)\gcd(b, c)\gcd\left(\dfrac{k}{\gcd(k,l)}, \dfrac{c}{\gcd(b, c)}\right)\gcd\left(\dfrac{b}{\gcd(b, c)},\dfrac{l}{\gcd(k,l)}\right)\geq \gcd(b, c)\), and b = 168k for some positive integer k and c = 88l for some positive integer l.

 

\(\min\gcd(b, c)=\gcd(168, 88) = 8\).

 

For the proof of the gcd identity I used, see here: https://math.stackexchange.com/questions/1394801/prove-that-ab-cd-a-cb-d-left-fracaa-c-fracdb-d-right-left?noredirect=1&lq=1

 Apr 16, 2022
 #1
avatar+9369 
+1
Best Answer

Note that \(168|a\) and \(88|a\) by the property of gcd.

 

Take \(a = \operatorname{lcm}(168, 88) = 1848\).

Then \(b = 168\) and \(c = 88\) satisfies the conditions. You can check that gcd(b, c) is minimum in this case because for any positive integers \(k,l\)\(\gcd(kb, lc) = \gcd(k, l)\gcd(b, c)\gcd\left(\dfrac{k}{\gcd(k,l)}, \dfrac{c}{\gcd(b, c)}\right)\gcd\left(\dfrac{b}{\gcd(b, c)},\dfrac{l}{\gcd(k,l)}\right)\geq \gcd(b, c)\), and b = 168k for some positive integer k and c = 88l for some positive integer l.

 

\(\min\gcd(b, c)=\gcd(168, 88) = 8\).

 

For the proof of the gcd identity I used, see here: https://math.stackexchange.com/questions/1394801/prove-that-ab-cd-a-cb-d-left-fracaa-c-fracdb-d-right-left?noredirect=1&lq=1

MaxWong Apr 16, 2022

8 Online Users

avatar