Solution to Diophantine equation $19991112x + 2803y = 33$

Question

I already found that $gcd(19991112,2803)=1$ so it does have solution. But I don't know how to find the solution.

Equation: Diophantine equation $19991112x + 2803y = 33$

Answer 1

Using the Euclidean algorithm you can find $a,b$ such that

$$19991112\cdot a + 2803\cdot b = 1.$$

In this case $a = (-1329), b = 9478483$. Therefore you can choose $$x=33\cdot a,y=33\cdot b.$$

Answer 2

meanwhile:

$$ \gcd( 19991112, 2803 ) = ??? $$

$$ \frac{ 19991112 }{ 2803 } = 7132 + \frac{ 116 }{ 2803 } $$ $$ \frac{ 2803 }{ 116 } = 24 + \frac{ 19 }{ 116 } $$ $$ \frac{ 116 }{ 19 } = 6 + \frac{ 2 }{ 19 } $$ $$ \frac{ 19 }{ 2 } = 9 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 7132 & & 24 & & 6 & & 9 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 7132 }{ 1 } & & \frac{ 171169 }{ 24 } & & \frac{ 1034146 }{ 145 } & & \frac{ 9478483 }{ 1329 } & & \frac{ 19991112 }{ 2803 } \end{array} $$ $$ $$ $$ 19991112 \cdot 1329 - 2803 \cdot 9478483 = -1 $$