+0

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

0
659
3
+1773

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

### Best Answer

#1
+85759
+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
Sort:

### 3+0 Answers

#1
+85759
+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
#2
+26640
+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
+92221
+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

### 28 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details