1
$\begingroup$

The greatest common divisor of 203 and 147; $gcd(203,147)=7$.
Thus how can we find all the solution in integers $x,y$ of the equation $203x + 147y=7$?

$\endgroup$
2
$\begingroup$

First off we can use the Extended Euclidean Algorithm to find some "first" values of x and y.

$$\begin{array}{rclcrcllr} 1 & \cdot & 203 & + & 0 & \cdot & 147 & = & 203 \\ 0 & \cdot & 203 & + & 1 & \cdot & 147 & = & 147 \\ 1 & \cdot & 203 & - & 1 & \cdot & 147 & = & 56 \\ -2 & \cdot & 203 & + & 3 & \cdot & 147 & = & 35 \\ 3 & \cdot & 203 & - & 4 & \cdot & 147 & = & 21 \\ -5 & \cdot & 203 & + & 7 & \cdot & 147 & = & 14 \\ 8 & \cdot & 203 & - & 11 & \cdot & 147 & = & 7 \\ -21 & \cdot & 203 & + & 29 & \cdot & 147 & = & 0 \\ \end{array}$$ These last two are important! The first tells us one solution of the equation; the second tells us a thing that, when I add it in to the first, doesn't change the right side.

So, our result is: $203x+147y=7 \rightarrow (x,y)=(8-21k,-11+29k)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.