find $u,v\in \mathbb Z$ such that $231u+45v=1$. I have to find $u,v\in \mathbb Z$ such that $231u+45v=1$. By Euclide algorithm, 
\begin{align*}
231&amp;=5\cdot 45+6\\
45&amp;=6\cdot 7+3\\
7&amp;=3\cdot 2+1
\end{align*}
The first equation gives $$6=231-5\cdot 45.$$
We put this in the second equation, and we get
$$45=(231-5\cdot 45)\cdot 7+3\implies 3=36\cdot 45-7\cdot 231.$$
Now I replace $3$ in the last equation, and obtain
$$7=2\cdot (36\cdot 45-7\cdot 231)+1\implies 7-72\cdot 45+14\cdot 231=1,$$

but the 7 disturbs me, did I do my algorithm wrong ?
Hint:
$$\gcd(231;45)=3$$
Then $$3|231u+45v$$
Let's calculate the greatest common divisor:
$\left( \begin{array}{lcr}
231 &amp; 1 &amp; 0 \\
45  &amp; 0 &amp; 1 \\
\end{array}
\right) \rightarrow \left( \begin{array}{lcr}
6 &amp; 1 &amp; -5 \\
45  &amp; 0 &amp; 1 \\
\end{array}
\right) \rightarrow \left( \begin{array}{lcr}
6 &amp; 1 &amp; -5 \\
3  &amp; -7 &amp; 36 \\
\end{array}
\right) \rightarrow \left( \begin{array}{lcr}
0 &amp; 15 &amp; -77 \\
3  &amp; -7 &amp; 36 \\
\end{array}
\right) \rightarrow$
Then the greatest common divisor is 3 and its beonzout equation  $3=(231)(-7)+(45)(36)$, then $d=g.c.d(231,45)=3\rightarrow d|(231x+45y)$, which it is imposible, 3 does not divide to 1, then does not exist $u\ and\  v$