Proving the GCD

Question

Let $a= 16673011647$. Let $b = 16213295811$. Using the fact that $a \times −77566962 + b \times 79766315 = 51$, prove that $51$ is the gcd of $a$ and $b$.

The part that is confusing is, using the linear combination to prove it, how would I do this?

Answer 1

The identity proves that $\gcd(a,b)\mid51$. Since $51=3\times17$, one is left with the task of proving that $3\mid a$ (easy, the sum of the digits of $a$ is $42$), that $3\mid b$ (easy, the sum of the digits of $b$ is $39$), that $17\mid a$ and that $17\mid b$.

Answer 2

Hint: Use Euclid algorithm. Just follows the steps & express it in the algebraic way.