+0

# Number Theory

0
140
1

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

#1
+9461
+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
+9461
+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

MaxWong Apr 16, 2022