Question

1. use the euclidean algorithm to find the gcd of 51 and 87, and then to write that gcd as a linear combination of 51 and 87.

Explanation:

Step1: Apply Euclidean Algorithm

We divide the larger number by the smaller one and find the remainders successively.
First, divide \( 87 \) by \( 51 \):
\( 87 = 51\times1 + 36 \)

Step2: Continue with Remainders

Now, divide \( 51 \) by \( 36 \):
\( 51 = 36\times1 + 15 \)

Step3: Next Division

Divide \( 36 \) by \( 15 \):
\( 36 = 15\times2 + 6 \)

Step4: Next Division

Divide \( 15 \) by \( 6 \):
\( 15 = 6\times2 + 3 \)

Step5: Next Division

Divide \( 6 \) by \( 3 \):
\( 6 = 3\times2 + 0 \)
When the remainder is \( 0 \), the previous remainder (\( 3 \)) is the gcd. So, \( \gcd(51, 87)=3 \).

Step6: Work Backwards to Find Linear Combination

We start from the equation where the remainder is \( 3 \):
\( 15 - 6\times2 = 3 \)
But \( 6 = 36 - 15\times2 \), substitute \( 6 \) in the above equation:
\( 15-(36 - 15\times2)\times2 = 3 \)
Simplify:
\( 15 - 36\times2+15\times4 = 3 \)
\( 15\times5 - 36\times2 = 3 \)
Now, \( 15 = 51 - 36\times1 \), substitute \( 15 \):
\( (51 - 36\times1)\times5 - 36\times2 = 3 \)
Simplify:
\( 51\times5 - 36\times5 - 36\times2 = 3 \)
\( 51\times5 - 36\times7 = 3 \)
Now, \( 36 = 87 - 51\times1 \), substitute \( 36 \):
\( 51\times5-(87 - 51\times1)\times7 = 3 \)
Simplify:
\( 51\times5 - 87\times7+51\times7 = 3 \)
\( 51\times12 - 87\times7 = 3 \)

So, the gcd \( 3 \) can be written as \( 3 = 51\times12 - 87\times7 \) (or other equivalent linear combinations).

Answer:

The gcd of \( 51 \) and \( 87 \) is \( 3 \), and it can be written as a linear combination \( 3 = 51\times12 - 87\times7 \) (or other valid combinations like \( 3 = -51\times(- 12)+87\times(-7) \), etc.).