+0

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

0
879
3
+1793

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
+89953
+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
+89953
+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
#2
+27044
+15

You are correct Chris.

In fact there are 3 pairs of integers that sum to 1001 and and have the largest gcd of 143, namely: (143, 858), (286, 715), (429, 752)   (All multiples of 143).

.

Alan  Jul 2, 2015
#3
+93656
+10

That is great logic Chris.

It is so simple and so logical but I would not have thought of it

Melody  Jul 2, 2015