Solve diophantine equation using modular arithemtic Solve for integers, $x, y$
$4258x+147y=369 \implies 4258x \equiv 369 \pmod{147}$
I got this question from SE, but I want to try this approach.
I suppose we will find the inverse modulus of $4258 \pmod{147}$ using Euclid's algorithm. So:
$4258 = 28(147) + 142$
$147 = 1(142) + 5$
$142 =  28(5) + 2$
$5 = 2(2) + 1 \implies 1 = 5 - 2(2)$
$$1 = 5 - 2\bigg( 142 - 28(5)  \bigg) = 5 - 284 + 2(28(5))$$
$$= 5 - 284 + 2\bigg( 28\cdot (147 - 142)   \bigg)$$
$$= 5 - 284 + 2\bigg(  28\cdot(147 - 4258 + 28(147))   \bigg)$$
I still dont understand this.
But I am lost in this algorithm, how should I compute further?
 A: Note that you have got a spare $5$ at the end. It is easier to deal with the brackets as they arise line by line. You will see that each line has two terms
$$1=5-2\cdot (2)$$
Replace $2$
$$1=5-2\cdot (142-28\cdot 5)=-2\cdot(142)+57\cdot (5)$$
Replace $5$
$$1=-2\cdot(142)+57\cdot(147-1\cdot (142))=-59\cdot (142)+57\cdot(147)$$
Replace $142$
$$1=-59\cdot(4258-28\cdot147)+57\cdot(147)\equiv -59\cdot4258 \bmod 147$$
A: The purpose of reverse substitution is to express $1=ar_1+br_2$ where $r_1,r_2$ are some consecutive remainders obtained in the algorithm.
So you need to combine the terms having $5$ after the second step, like so:
$1 = 5 - 2(142 - 28(5)) = 57(5)-2(142)$.


*

*$= 57(147 - 1(142)) - 2(142) = 57(147)-59(142)$.


Also, I have corrected your mistake: $18\to 28$.
Once you express $1=a(147)+b(4258)$, where $a,b$ are integers, take modulo $147$ on both sides, and you will get $b(4258)\equiv 1\quad(\text{mod }147)$. So $b$ is the inverse of $4258$ modulo $147$.
In the original equation, $x\equiv b(4258)x\equiv b(369)\quad(\text{mod }147)$.
To see why, $x=(a\times 147+b\times 4258)\times x$


*

*$=b\times 4258x+ax\times 147=b\times 369+c\times 147+ax\times 147$

*$=b\times 369+(c+ax)\times 147$

