Euclidean Algorithm problem $475x+2018y=1$

Question

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!

Answer 1

Note that from your derivation it is

• $x=-667$
• $y= 157$

and

$$-667\equiv1351\equiv475^{-1} \pmod {2018}$$

Answer 2

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}}$

Answer 3

$$ \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 $$

............