# $8x +9y = 5$ where $x,y \in \mathbb{Z}$

Solve the following Diophantine equation algebaically: $$8x+9y=5$$ Give 3 possible solutions for the equation

I have the following:

The Diophantine equation has solutions $x,y \iff 8x=5\mod{9}$ has a solution $x \equiv\mod{9}$

Since $\gcd(8,9)=1$, by Bezout's Lemma, for $r,t \in \mathbb{Z}, \gcd(8,9)=1=r(8)+t(9)$ and $x\equiv r(5)\mod{9}$ is a solution for the linear congruence above.

By Euclid's algorithm for determining $\gcd(8,9)$ we have

\begin{align}9 &= 1(8) +1 \\ 8 &=9(1)+0\end{align} so $1=(-1)8 + 1(9)$ and $r=-1 \implies x \equiv(-1)5\mod{9}$.

Now \begin{align}[-5]_9 &= \{-5 + 9k \ | k\in\mathbb{Z} \} \\ &= \{ ..., -5,4,13,... \} \\ &=[4]_9\end{align} $\therefore x \equiv 4 \mod{9}$, that is $x=4+9k$ for all $k \in \mathbb{Z}$ upon which it can be seen that $y= -3 -8k$.

Is this correct?

• Yes, this is correct, and you found all the solutions to the equation, in my opinion. – awllower Nov 17 '14 at 0:22
• I am feeling uncertain about my Euclid's Algorithm for some reason. That is the part I especially felt unsure about – user860374 Nov 17 '14 at 0:23
• I feel very certain that your use of Euclidean algorithm is correct. :) – awllower Nov 17 '14 at 0:24
• Since the problem stated "find three solutions", I would explicitly write out three of them, like $x=4, y = -3$. But otherwise it looks correct. – Arthur Nov 17 '14 at 0:25
• why bother with the euclide thing? in that case, it is obvious that $9-8=1$. – mookid Nov 17 '14 at 0:25

Choose $x$ or $y$ ? Let's solve for $x$: $x = \dfrac{5-9y}{8} = \dfrac{5-y}{8} - y \Rightarrow 5-y = 8k \Rightarrow y = 5 - 8k \Rightarrow x = k - (5-8k) = 9k-5$. Thus:
$(x,y) = (9k-5,5-8k), k \in \mathbb{Z}$
$8x+9y=5\iff8~(x+y)+y=5=8\cdot0+5\iff x+y=0$ and $y=5\iff x=-5$. Then all numbers of the form $x=-5-9k$ and $y=5+8k$ are solutions to the above equation.
• Alternately, $5=8\cdot1-3$. – Lucian Nov 17 '14 at 1:59