1

I would like to examine whether the following claim is true:

For the following equation: \begin{equation} ax+by=\text{gcd}(a,b) \end{equation}

where $a,b, \in \mathbb{N}$ and $x,y \in \mathbb{Z}$, there exist $x_1,y_1 \in \mathbb{Z}$ such that $x_1 \neq x, y_1 \neq y$ and

\begin{equation} ax_1+by_1=\text{gcd}(a,b) \end{equation} I believe it holds and that it is also possible to express analytically $x_1, y_1$ in terms of $x,y$. I have reached the following point: \begin{align} ax+by=\text{gcd}(a,b) & \Leftrightarrow ax+ax_1-ax_1+by+by_1-by_1=\text{gcd}(a,b) \Leftrightarrow \\ & a(x-x_1)+b(y-y_1)+(ax_1+by_1)=\text{gcd}(a,b) \Leftrightarrow \\ & a(x-x_1)+b(y-y_1)=0 \end{align} where I used the fact that $(ax_1+by_1)=\text{gcd}(a,b)$. After distinguishing cases I end up with $x>x_1, y<y_1$ (or $x<x_1, y>y_1$) and: \begin{equation} x= -(b/a)(y-y_1)+x_1 \end{equation} But from that point on, I cannot figure out how to continue, since when I try to substitute for $y=(\text{gcd}(a,b)-ax)/b$, I end up with just the relation $ax_1+by_1=\text{gcd}(a,b)$.

There must be some wrong step in my proof but I cannot figure it out.

Bazinga
  • 1,463
  • Not sure what you are asking. There are infinitely many $x,y$ that work. If a given pair $(x_0,y_0)$ works then for any $n\in \mathbb Z$ the pair $(x_0+nb,y_0-na)$ will work. – lulu Feb 13 '18 at 14:52
  • If $(x,y)$ works, then $(x+k\frac{b}{gcd(a,b)},y-k\frac{a}{gcd(a,b)})$ works, see here. – Dietrich Burde Feb 13 '18 at 14:54
  • Thank you for the responses guys! @lulu and DietrichBurde could you please provide the proofs on that? I am curious to see where did I go wrong. – Bazinga Feb 13 '18 at 14:56
  • Hi guys, I visited the possible but there is not linked article (as promised) in the chosen answer to take a look at. Any ideas? – Bazinga Feb 13 '18 at 14:58
  • 1
    The answer is in the wikipedia article, linked in the duplicate. All Bezout coefficients are given there - in particular the ones you want to construct. – Dietrich Burde Feb 13 '18 at 15:14
  • @DietrichBurde Thank you for your help! – Bazinga Feb 13 '18 at 17:30

0 Answers0