Linear Diophantine equations with fractional coefficients

93 Views Asked by At

I would like to find an expression for an equation of the following form

$$a n+bm$$

where $a,b\in\mathbb Q$ are rationals and $n,m\in\mathbb Z$ are integers, such that there is only one integer dependence.

I.e. I would like to find a general expression to identify $r$ such that

$$a n+bm=rn'$$

for all $n'\in\mathbb Z$.

I have found a way to do this, but I am struggling to find resources on this topic, and whether this quantity $r$ has a name and what the simplest way of calculating it is. I would also like to find a way to generalise this to multiple coefficients $a,b,c,\dots$.

Here is a general way of calculating a solution for $r$:

It is possible to turn the original expression into a standard linear Diophantine equation by rewriting $a,b$ as

$$a=u/v\qquad b=x/y$$

Then we have

$$an+bm=\frac{1}{vy}(uyn+xvm)$$

From this we can identify the linear Diophantine equation

$$uyn+xvm=c$$

where $c$ must be an integer multiple of $l=\text{gcd}(uy,xv)$. Equivelantly we could then write

$$uyn+xvm=ln'$$

This allows us to rewrite the original expression as

$$a n+bm=\frac{\text{gcd}(uy,xv)}{vy}n'=rn'$$

My question is, is there some simpler expression to find the coefficient

$$r=\frac{\text{gcd}(uy,xv)}{vy}$$

given two fractions $a,b$ and does it have a name?

1

There are 1 best solutions below

0
On

Let $a,b\in\Bbb{Q}$ be given, and let $r\in\Bbb{Q}$ be the largest rational number such that for all $m,n\in\Bbb{Z}$, there exists some $k\in\Bbb{Z}$ such that $$am+bn=rk.$$ Writing $a=\tfrac uv$ and $b=\tfrac xy$ with $u,v,x,y\in\Bbb{Z}$ and $\gcd(u,v)=\gcd(x,y)=1$, then indeed $$r=\frac{\gcd(uy,vx)}{vy}.$$ Because $\gcd(u,v)=\gcd(x,y)=1$ you have $$\gcd(uy,xv)=\gcd(u,x)\cdot\gcd(v,y).$$ Then from the identity $vy=\gcd(v,y)\cdot\operatorname{lcm}(v,y)$ it follows that $$r=\frac{\gcd(uy,vx)}{vy}=\frac{\gcd(u,x)}{\operatorname{lcm}(v,y)}.$$ I am not aware of any name for this particular expression.