Least positive solution of $ax = by$ is $(x,y) = (b/d,a/d),\ d = \gcd(a,b)$

Question

Let $a,b$ be positive integers. Suppose that $x,y$ are the smallest positive integers such that $ax-by = 0$. Prove that \begin{align*} x = \dfrac{b}{gcd(a,b)} \quad \text{and} \quad y = \dfrac{a}{gcd(a,b)} \end{align*}

This is easy to prove when you set $x=1$ and $y=2$, but that is just an example. How would one prove this in a general sense?

Any tips would be appreciated!

Answer 1

From

$$ax - by = 0 \tag{1}\label{eq1}$$

you can get that

$$x = \frac{by}{a} \tag{2}\label{eq2}$$

$$y = \frac{ax}{b} \tag{3}\label{eq3}$$

First, since $x$ and $y$ are integers, \eqref{eq2} shows that

$$a \mid by \tag{4}\label{eq4}$$

Let

$$d = \gcd(a,b) \tag{5}\label{eq5}$$

$$a = de, \; e \in \mathbb{Z^{+}} \tag{6}\label{eq6}$$

$$b = df, \; f \in \mathbb{Z^{+}} \tag{7}\label{eq7}$$

Note \eqref{eq5}, \eqref{eq6} and \eqref{eq7} shows that

$$\gcd(e,f) = 1 \tag{8}\label{eq8}$$

Using \eqref{eq6} and \eqref{eq7} in \eqref{eq4} gives

$$de \mid dfy \implies e \mid fy \tag{9}\label{eq9}$$

Note \eqref{eq8} means $e \mid y$. Thus, the smallest positive integer $y$ is $y = e$. Using this and \eqref{eq6} in \eqref{eq2} gives

$$x = \frac{be}{de} = \frac{b}{d} = \frac{b}{\gcd(a,b)} \tag{10}\label{eq10}$$

Using a similar procedure, plus from substituting \eqref{eq10} in \eqref{eq3}, you can get that

$$y = \frac{a}{\gcd(a,b)} \tag{11}\label{eq11}$$

Answer 2

Let $\,d\! =\!(a,b).$ $\, a\mid yb\! \iff\! a/d\mid y\,b/d\!\!\! \overset{\color{#c00}{\rm EL}\!\! }\iff a/d\mid y,\,$ so least $\,y\! =\! a/d\,$ $\overbrace{\&\,\ {\rm least}\ x\! =\! b/d}^{\text{by symmetry}}$

Remark $ $ $\color{#c00}{\rm EL}$ = Euclid's Lemma. Conceptually, this boils down to unique fractionization, i.e. every fraction $y/x$ equivalent to $\,a/b\,$ arises by scaling its least terms rep $(a/d)/(b/d).\,$ The linked post has much further discussion of this basic property.

Answer 3

Suppose that $$\newcommand{\lcm}{\operatorname{lcm}} ax-by=0\tag1 $$ Note that $ax=by$ is a common multiple of $a$ and $b$. By the minimality of $x$ and $y$, we must have $$ ax=by=\lcm(a,b)\tag2 $$ In this answer it is shown that $$ ab=\lcm(a,b)\gcd(a,b)\tag3 $$ Equations $(2)$ and $(3)$ tell us that $$ x=\frac{\lcm(a,b)}{a}=\frac{b}{\gcd(a,b)}\tag4 $$ and $$ y=\frac{\lcm(a,b)}{b}=\frac{a}{\gcd(a,b)}\tag5 $$

Answer 4

Well $ax = by$ so $\frac a{\gcd(a,b)}x =\frac b{\gcd(a,b)}y$.

But $\frac a{\gcd(a,b)}$ and $\frac b{\gcd(a,b)}$ are relatively prime.

So $\frac a{\gcd(a,b)}|y$ and $\frac b{\gcd(a,b)}|x$

So $x\ge \frac b{\gcd(a,b)}$ and $y \ge \frac a{\gcd(a,b)}$.

But $x= \frac b{\gcd(a,b)}$ and $y = \frac a{\gcd(a,b)}$ are solutions (because $\frac a{\gcd(a,b)}b = \frac b{\gcd(a,b)}a$), so those are the smallest solutions.