Is there an algorithm to simplify solutions of linear Diophantine Equations?

Question

I will use the following equation as an example:

$$3x + 5y = 47$$

We know that $gcd(3,5) = 1 | 47$ so, this equation has a solution. In order to find it, we can use the euclidean algorithm and the Bézout's identity:

$$ 1 = 2 \times 3 + (-1) \times 5$$

From here, we can multiply both sides by 47 and find a solution:

$$94 \times 3 + (-47) \times 5 = 47$$

So $$x_0 = 94$$ and $$y_0 = -47$$ and we get:

$$x=94+5n$$ and $$y = -47 - 3n$$

That is how I have learnt do solve this type of equations. However if I look this solution on Wolfram Alpha it gives me:

$$x = 5n+ 4$$ and $$y= 7 - 3n$$

Wolfram Alpha always gives the smallest constants. In this example, instead of $94$ and $-47$, it found $4$ and $7$, which are easier to work with in some problems.

My question is, is there an algorithm to find this "simpler" solutions?

Answer 1

I don't very well understand your question but I hope this is what you are looking for:

Take $\textrm{mod}\ 5$ on the equation (or $\textrm{mod}\ 3 $, whichever suits), we get $\newcommand{\Mod}[3]{#1\equiv #2\ (\textrm{mod}\ #3)}$$\Mod{3x}{2}{5}$ or $\Mod{3x}{12}{5}$ giving $\Mod{x}{4}{5}$, which gives $x=5m+4$. Putting this back yields $y=7-3m$, as desired.

Other than that, your solution can also be refined as $$x=94+5n=5(18+n)+4$$ $$y=-47-3n=-3(18+n)+7$$ With quick redefining $m=18+n$, you get the same solution as WolframAlpha.

Hope this helps. :)

Answer 2

If you're mostly dealing with small coefficients, simple brute force can work. If you look at $47-5y$, it's pretty quick to find two values of $y$ that make the expression divisible by $3$, i.e., $y = 1, 4$ giving $x=14, 9$, for a general solution of $(x=9+5n, y=4-3n)$.

Separately, you can look at $(x=94+5n, y = -47-3n)$ and set $n$ to a value that gives small solutions, plus a new variable. If we let $n = k-18$ here, you get the solution delivered by W|A, with $k$ in place of $n$.

Answer 3

Yes, there is a simple algorithm. By here we can reduce the linear Diophantine equation to an equivalent linear congruence $\!\bmod 5,\,$ then apply well-known methods using modular arithmetic.

Reducing the equation $\!\bmod 5,\,$ noting $\color{#4bf}{47}\bmod 5 = \color{#4bf}{-3}\,$ yields an equivalent congruence, viz.

$$\begin{align} 3x+5y=\color{#4bf}{47}\iff 3x&\equiv \color{#4bf}{-3}\!\!\pmod{\!5}\\[.2em] \iff\,\ x&\equiv -1\!\!\pmod{\!5}\\[.2em] \iff\, \ x&\in\!\!\!\! \underbrace{-1\,+\,5\:\!\Bbb Z}_{\!\!\!\textstyle \ldots \color{#c00}{{-}1},\,\color{#0a0}4,\,9\,\ldots}\end{align}\qquad\qquad\!\!$$

The "simplest" solution $\,x\,$ depends on the definition: the least $\rm\color{#0a0}{nonegative}$ solution is $\,\color{#0a0}{x\equiv 4},\,$ but the least $\rm\color{#c00}{magnitude}$ solution is $\,\color{#c00}{x\equiv -1}.\,$ Given any solution $\,x_0\equiv -1\pmod{5}\,$ the least nonnegative solution is simply its remainder $\,r = x_0\bmod 5,\,$ which is also a least magnitude solution if $\, r \le 2\, (= \lfloor 5/2\rfloor)$; else it is $\,r-5,\,$ e.g. $\,r = 3\,$ has $\,3-5 = -2\,$ as least magnitude.

If we seek to do further arithmetic $\!\bmod 5\,$ with $x$ then "simpler" may be context dependent, e.g. calculating $\,x^n\equiv (\color{#c00}{-1})^n$ is simpler than $\,\color{#0a0}4^n,\,$ but $\,x/2\equiv \color{#0a0}4/2\,$ is simpler than $\:\!\color{#c00}{-1}/2$. This freedom to choose the most convenient residue ("remainder") is one of the advantages that $\!\bmod\!$ the congruence relation has vs. $\!\bmod\!$ the binary operation (see here for much further discussion).

Exactly the same method above works generally, e.g. see this answer.

See here on least-magnitude and other complete sets of residue systems (residue normal forms).