GCD of two positive integers.

Algebra Level 2

If $a$ and $b$ are positive integers and $c$ is the greatest common factor of $a$ and $b$ . In the other words $gcd(a,b)=c$ .

then $c$ must be the greatest common factor of $a$ and which of the following given options?

a+b

2b

ab

b^2

2+b

1 solution

Daniel Xiang
Feb 12, 2018

Here we prove that $\gcd(a, b) = \gcd(a, a+b)$

Suppose $d | a$ and $d| b$ there exists integers $c_1, c_2$ such that $a = dc_1$ and $b= dc_2$ , thus $a+b = dc_1+dc_2 = d(c_1+c_2)$ , and we have $d | (a+b)$ .

Nice solution. Thank you.

Hana Wehbi - 3 years, 3 months ago

GCD of two positive integers.

1 solution

0 pending reports