Euclidean Algorithm problem $475x+2018y=1$ I thought I was doing this right until I checked my answer online and got a different one. I worked through the problem again and got my original answer a second time so this one is bothering me since the other similar ones I have done checked out okay. Please let me know if I'm doing something wrong, thanks!

Find $x, y$ contained in integers such that $475x+2018y=1$ then find a value for $475\equiv -1$ (mod $2018$).

Since it is in the form of $ax+by=1$ I know that the $\gcd(a,b)=1$. I still did the division algorithm since that helps me with the back substitution. Here is what I got.
Division Algm:


*

*$2018=(4\times 475)+118$

*$475=(4\times 118)+3$

*$18=(39\times 3)+1$
Back Sub:


*

*$1=118-(39\times 3)$

*$1=118-39(475-(4\times 118))$

*$1=(157\times 118)-(39\times 475)$

*$1=157\times (2018-(4\times 475))-(39\times 475)$

*$1=(157\times 2018)-(667\times 475)$
So $x=667$ and $y=157$
The second question I answered from the first part which is $475x$ congruent to $1$(mod $2018$) so that would just be $667$ from the first part. Any help is appreciated, thanks!   
 A: What you get wrong is the task asks you to find integers for $475x+2018y=1$, NOT $-475x+2018y=1.$
For this type of problem, my answer to this problem would be similar to the answer I posted here for the case $73a+89b=3$, the main method is to keep on setting new variables, like so: 


*

*Put $a=\frac{3-89b}{73}=\frac{3-16b}{73}-b$, then $\frac{3-16b}{73} \in \mathbb{Z}$ because $a,b\in \mathbb{Z}$.

*Put $c=\frac{3-16b}{73}$, then $3-16b=73c$ or $b=\frac{3-73c}{16}=\frac{3-9c}{16}-4c$, then $\frac{3-9c}{16} \in \mathbb{Z}$ because $b,c\in \mathbb{Z}$.

*Put $d=\frac{3-9c}{16}$, then $3-9c=16d$ or $c=\frac{3-16d}{9}=\frac{3-7d}{9}-d$, then $\frac{3-7d}{9} \in \mathbb{Z}$ because $c,d\in \mathbb{Z}$.

*Put $e=\frac{3-7d}{9}$, then $3-7d=9e$ or $d=\frac{3-9e}{7}=\frac{3-2e}{7}-e$, then $\frac{3-2e}{7} \in \mathbb{Z}$ because $d,e\in \mathbb{Z}$.

*Put $f=\frac{3-2e}{7}$, then $3-2e=7f$ or $e=\frac{3-7f}{2}=\frac{1-f}{2}+1-3f$, then $\frac{1-f}{2} \in \mathbb{Z}$ because $e,f\in \mathbb{Z}$.
$e$ would be an integer if and only if $f=2k+1$ or $f$ odd
$\Rightarrow e=-7k-2$
$\Rightarrow d=9k+3$
$\Rightarrow c=-16k-5$
$\Rightarrow {\begin{cases}a=-89k-28\\b=73k+23\end{cases}}$
For much larger numbers like $475x+2018y=1$, you would simply do the step above more times, but your trial-and-error method may be true if you haven't misread the problem, the final answer should be

 ${\begin{cases}x=-2018k-667\\y=475k+157\end{cases}}$

A: Note that from your derivation it is


*

*$x=-667$

*$y= 157$


and 
$$-667\equiv1351\equiv475^{-1} \pmod {2018}$$
A: $$ \frac{ 2018 }{ 475 } = 4 +  \frac{ 118 }{ 475 } $$ 
 $$ \frac{ 475 }{ 118 } = 4 +  \frac{ 3 }{ 118 } $$ 
 $$ \frac{ 118 }{ 3 } = 39 +  \frac{ 1 }{ 3 } $$ 
 $$ \frac{ 3 }{ 1 } = 3 +  \frac{ 0 }{ 1 } $$ 
 Simple continued fraction tableau:
 $$ 
 \begin{array}{cccccccccc}
 & & 4 & & 4 & & 39 & & 3 & \\ 
  \frac{ 0 }{ 1 }   &   \frac{ 1 }{ 0 }   & &   \frac{ 4 }{ 1 }   & &   \frac{ 17 }{ 4 }   & &   \frac{ 667 }{ 157 }   & &   \frac{ 2018 }{ 475 }  
 \end{array}
 $$ 
 $$  $$ 
 $$ 2018 \cdot 157 - 475 \cdot 667 = 1 $$
............
