General Solution to gcd(a,b)=ax+by

To solve the general equation  
\[gcd(143,17)=143x+17y\]
  where  
\[x, \; y\]
  are integers, use The Euclidean Algorithm.
\[143=8 \times 17+7\]

\[17=2 \times 7+3\]

\[7=2 \times 3+1\]

\[143=8 \times 17+7\]

\[3=3 \times 1+0\]

Hence
\[\begin{equation} \begin{aligned} gcd(143.17) &= 1 \\ &= 7-2 \times 3 \\ &= 7-2 (17-2 \times 7) \\ &= -2 \times 17+5 \times 7 \\ &= -2 \times 17+5(143-8 \times 17) \\ &= 5 \times 143 -42 \times 17 \end{aligned} \end{equation}\]

One solution is  
\[x=5, \; y=-42\]
.
The general solution is  
\[5-17k, \; y=y=-43+143k\]
.

Add comment

Security code
Refresh