4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes, this is correct, and you found all the solutions to the equation, in my opinion. $\endgroup$ – awllower Nov 17 '14 at 0:22
  • $\begingroup$ I am feeling uncertain about my Euclid's Algorithm for some reason. That is the part I especially felt unsure about $\endgroup$ – user860374 Nov 17 '14 at 0:23
  • $\begingroup$ I feel very certain that your use of Euclidean algorithm is correct. :) $\endgroup$ – awllower Nov 17 '14 at 0:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Arthur Nov 17 '14 at 0:25
  • 1
    $\begingroup$ why bother with the euclide thing? in that case, it is obvious that $9-8=1$. $\endgroup$ – mookid Nov 17 '14 at 0:25
0
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ Alternately, $5=8\cdot1-3$. $\endgroup$ – Lucian Nov 17 '14 at 1:59

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.