# Euler's method for linear diophantine equations

This should be extremely easy, but I'm having trouble with something. I'm following C.D. Olds "Continued Fractions" book, pages 43/44.

Consider the equation $$8x+5y=81$$. We're searching for integer solutions. We want to find those solutions using Euler's method, that is: let's consider the variable with the smallest coefficient, $$y$$, and solve for it: $$y = \frac{81-8x}{5}$$. Let's consider the biggest multiples of 5 contained in 81 and 8: $$81=5 \cdot 16+1$$ and $$8=5\cdot 1 +3$$. Therefore, $$y = 16 - x + \frac{1-3x}{5}= 16 - x + t$$, with $$t = \frac{1-3x}{5}$$. So, $$3x+5t=1$$. We have obtained a new equation, where the coefficients are now smaller than those of the original equation. As $$x$$ and $$y$$ have to be integers, $$t$$ has to be an integer.

I'm fine with all that. Now, we should replicate this procedure again. Here's what the author does:

$$x=\frac{1-5t}{3}=\frac{1-(2 \cdot 3-1)t}{3}=-2t+\frac{t+1}{3}=-2t+u$$. Since $$x$$ and $$t$$ are integers, $$u$$ has to be an integer. We have $$x=2-5u$$ and $$y=8u+13$$. By inserting here every possible integer value of $$u$$, we find the infinite solutions to our equation.

Why do we perform the substitution $$5=2 \cdot 3 - 1$$ rather than $$5=3 \cdot 1 +2$$? Shouldn't the second one the one we should be doing, in analogy with the first equation?

Moreover, if we perform the substitution $$5= 3\cdot 1 + 2$$, we get $$x=\frac{1-5t}{3}=\frac{1-(3 \cdot 1+2)t}{3}=-t+\frac{1-2t}{3}=-t+u$$, with $$u = \frac{1-2t}{3}$$. By the same reasoning as before, $$u$$ has to be an integer. Therefore, $$x=\frac{1-5t}{3}=\frac{1-5(\frac{1-3u}{2})}{3}=\frac{-1+5u}{2}$$. Which can't be correct: for every integer value of $$u$$ I should get an integer solution, by setting $$u=0$$ that's not the case. What's wrong?

EDIT: nothing's wrong. I simply had to take all the integer values of $$u$$ such that $$x$$ and $$y$$ are integers. $$u=0$$ does not satisfy this requirement. All odd values of $$u$$ do.

I would write $$5y=80-10x+1+2x$$ so $$y=16-2x+\frac{1+2x}{5}$$ with $$\frac{1+2x}{5}=t$$ we get $$x=3t-1+\frac{1-t}{2}$$ Can you finish?
• Yes. $u = \frac{1-t}{2}$, so $t = 1-2u$, $x=2-5u$ and $y=13+8u$, by substituting. What I don't get is how I choose the "form" in which to write the equation. Why should I write $y$ and $x$ the way you did, and not, for example, $x=\frac{5t-1}{2}$? What's wrong with the example I provided in my original post? – D. Joe Dec 24 '18 at 11:55
• @D.Joe here's another method I personally prefer over Euler's. $8x+5y=81$, where $81$ ends in $1$. Note that for some $z$, it follows $81+5z$ will either end in digit $1$ or $6$. Note that any multiple of $8$ must have an even last digit since $8$ is a power of $2$. Therefore, $1$ isn't the last digit of a multiple of $8$, but $6$ is. Intuitively, $8(5k+2)$ has $6$ as a last digit for all multiples of $k$. Now $81-8\times 2 = 65=13\times 5$. Therefore: \begin{align}x&=5k+2 \\ y&=13-8k\end{align} This is the same as the result in your question, given $k=-u$. This method is not rigorous but. – Mr Pie May 18 at 2:34