The sum of two positive integers $a$ and $b$ is 1001. What is the largest possible value of $\gcd(a,b)$?

Mellie
Jul 1, 2015

#1**+20 **

Note that 1001 factors as 7 x 11 x 13 = 7 * 143

So.....143 is the greatest proper divisor of 1001

This means that we have 143( m + n) = 143m + 143m = a + b = 1001 .....where ( m + n) = 7 ....and since m + n are two positive integers whose sum = 7, they are relatively prime to each other

Thefore, the two integers 143m, 143n = a, b have only the factor of 143 in common.....and it is the gcd of both.

{Could some other mathematician check my logic, here ??? }

CPhill
Jul 2, 2015

#1**+20 **

Best Answer

Note that 1001 factors as 7 x 11 x 13 = 7 * 143

So.....143 is the greatest proper divisor of 1001

This means that we have 143( m + n) = 143m + 143m = a + b = 1001 .....where ( m + n) = 7 ....and since m + n are two positive integers whose sum = 7, they are relatively prime to each other

Thefore, the two integers 143m, 143n = a, b have only the factor of 143 in common.....and it is the gcd of both.

{Could some other mathematician check my logic, here ??? }

CPhill
Jul 2, 2015