Find integers $\alpha$ and $\beta$ such that $255\alpha + 63546\beta= gcd(255,63546).$

Question

I want to make sure I did the steps correctly ;

I got $\alpha = -249, \beta=1.$

$n= 63546| 255$

$x= 255 | 51$

$q= 249 | 5$

$r= 51 | 0$

$i= -249 | 1$

$j= 1 | 0 $

where $255 \times 0 + 51 \times 1 = 51.$ Then $255 \times -249 + 63546\times 1=51$

Answer 1

You answer is one of many. Let's first find $\gcd(255,63546)$.

Notice that $255=3 \cdot 5 \cdot 17$ and $63546 = 2 \cdot 3 \cdot 7 \cdot 17 \cdot 89$. Then the highest divisor of these two numbers is $3 \cdot 17$. Hence $\gcd(255,63546) = 51.$

Now it is relatively simple to solve the equation.

\begin{align} 255 \alpha + 63546 \beta & = 51 \\ 5 \alpha + 1246 \beta & = 1 \\ 5\alpha & = 1-1246 \beta \\ \alpha& = \frac{1 - 1246 \beta}{5} \\ \end{align}

Notice that we ended up with a linear equation. Any $\{\alpha,\beta\} \in \mathbb Z$ will work as long as the above equation is satisfied.

Your solution, $\{-249,1\}$ works.

\begin{align} \alpha & = \frac{1-1246 \beta}{5} \\ & = \frac {1-1246 \cdot 1}{5} \\ & = -249 \\ \end{align}

In fact, there are infinitely many solutions to this equation, since it is a linear line and it goes on forever.