0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D. Joe Dec 24 '18 at 11:55
  • $\begingroup$ Problem solved. See my edit. Thank you anyway. $\endgroup$ – D. Joe Dec 24 '18 at 15:50
  • $\begingroup$ @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. $\endgroup$ – Mr Pie May 18 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.