Feedback on Euclidean Algorithm: $gcd(277, 301)$

Question

Ans:

$301 =277 \cdot 1 + 24$

$277 =24 \cdot 11 + 13$

$24 = 13 \cdot 1 + 11$

$13 = 11 \cdot 1 + 2$

$11 = 2 \cdot 5 + 1$

$2 = 1 \cdot 2 + 0$

Is this correct?

Answer 1

Looks correct to me, though it would probably help to put each division on a new line, just as far as readability goes.

Answer 2

GCD(277,301):

• $301 - (277 \times 1) = 24$
• $277 - (24 \times 11) = 13$
• $24 - (13 \times 1) = 11$
• $13 - (11 \times 1) = 2$
• $11 - (2 \times 5) = 1$
• $2 - (1 \times 2) = 0$

Thus the result is $\mbox{GCD}(277, 301) = 1$.

Expressed differently, we have:

• Divisors of $277: 1, 277~$ (that is, a prime)
• Divisors of $301: 1, 7, 43, 301$

What is the greatest common divisor between the two? Answer $ = 1$.