find $u,v\in \mathbb Z$ such that $231u+45v=1$.

Question

I have to find $u,v\in \mathbb Z$ such that $231u+45v=1$. By Euclide algorithm, \begin{align*} 231&=5\cdot 45+6\\ 45&=6\cdot 7+3\\ 7&=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 ?

Answer 1

Hint:

$$\gcd(231;45)=3$$

Then $$3|231u+45v$$

Answer 2

Answer

$$\gcd(231;45)=3$$

Then $$3|231u+45v$$

BUT $$3\nmid1$$

So No integer solutions

Answer 3

Bezout’s Lemma or the Linear Diophantine Equation Theorem

For all $a, b\in Z$, not both zero, there exists, $x, y\in Z$ such that $ax+by=c$ if and only if $\gcd(a, b)$ divides $c\,$, $$\gcd(231, 45)=3 $$

Answer 4

Let's calculate the greatest common divisor: $\left( \begin{array}{lcr} 231 & 1 & 0 \\ 45 & 0 & 1 \\ \end{array} \right) \rightarrow \left( \begin{array}{lcr} 6 & 1 & -5 \\ 45 & 0 & 1 \\ \end{array} \right) \rightarrow \left( \begin{array}{lcr} 6 & 1 & -5 \\ 3 & -7 & 36 \\ \end{array} \right) \rightarrow \left( \begin{array}{lcr} 0 & 15 & -77 \\ 3 & -7 & 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$

Answer 5

You did not apply the Euclidean algorithm correctly.

Let $a, b \in \mathbb{N}$ with $a \geq b$. Then we apply the Euclidean algorithm as follows. Apply the Division Algorithm to $a$ and $b$ to obtain $$a = q_1b + r_1, 0 \leq r_1 < b$$ If $r_1 = 0$, then $\gcd(a, b) = b$. Otherwise, divide $b$ by $r_1$ to obtain $$b = q_2r_1 + r_2, 0 \leq r_2 < r_1$$ If $r_2 = 0$, then the process stops and $\gcd(a, b) = r_1$. Otherwise, the process continues until some zero remainder appears, at, say, the stage when $r_{n - 1}$ is divided by $r_n$. Then \begin{align*} a & = q_1b + r_1, && \text{$0 < r_1 < b$}\\ b & = q_2r_1 + r_2, && \text{$0 < r_2 < r_1$}\\ r_1 & = q_3r_2 + r_3, && \text{$0 < r_3 < r_2$}\\ & \quad \vdots\\ r_{n - 2} & = q_nr_{n - 1} + r_n, && \text{$0 < r_n < r_{n - 1}$}\\ r_{n - 1} & = q_{n + 1}r_n + 0 \end{align*} where the last non-zero remainder $r_n = \gcd(a, b)$.

When you applied the Euclidean algorithm, you should have obtained \begin{align*} 231 & = 5 \cdot 45 + 6\\ 45 & = 7 \cdot 6 + 3\\ 6 & = 2 \cdot 3 + 0 \end{align*} You made your mistake in the third line, where you used $q_1 = 7$ instead of $r_1 = 6$.

Since the last non-zero remainder is $3$, $\gcd(231, 45) = 3$. As others have pointed out, the left side of the equation $231x + 45y = 1$ is divisible by $3$, while $1$ is not divisible by $3$. Hence, the equation has no solutions in the integers.