What is the greatest number that will divide 651 and 1110 leaving the remainders 5 and 8, respectively?

Correct option is A

Given:

When 651 is divided by the greatest number d, the remainder is 5.

When 1110 is divided by the greatest number d, the remainder is 8.

Solution:

GCD of 646 and 1102:

We will use the Euclidean algorithm to find the GCD.

Divide 1102 by 646:

​$$1102 \div 646 = 1 \quad \text{(quotient)} \quad \text{remainder} = 1102 - 646 = 456$$​

Divide 646 by 456:

​$$646 \div 456 = 1 \quad \text{(quotient)} \quad \text{remainder} = 646 - 456 = 190$$​

Divide 456 by 190:

​$$456 \div 190 = 2 \quad \text{(quotient)} \quad \text{remainder} = 456 - 2 \times 190 = 456 - 380 = 76$$​

Divide 190 by 76:

​$$190 \div 76 = 2 \quad \text{(quotient)} \quad \text{remainder} = 190 - 2 \times 76 = 190 - 152 = 3$$​8

Divide 76 by 38:

​$$76 \div 38 = 2 \quad \text{(quotient)} \quad \text{remainder} = 76 - 2 \times 38 =$$​ 0

Since the remainder is now 0, the GCD is the last non-zero remainder, which is 38.

The greatest number d that will divide both 651 and 1110, leaving remainders of 5 and 8, respectively, is 38.

The greatest number is 38.