Are the solutions of the diophantine equations right?

[evinda]

Hi! (Sun)

I have to solve the diophantine equations:

• $18x+5y=48$
• $158x-57y=7$

for $x,y >0$

That's what I have tried:

• $$gcd(18,5)=1, \text{ so } 18x+5y=48 \text{ has infinite solutions.}$$
  
  $$\text{ As } gcd(18,15)=1, \exists x_0,y_0 \text{ such that } 18x_0+5y_0=1 \Rightarrow 18 (48x_0)+5(48y_0)=48$$
  
  $$\text{So, } x_1=48x_0 , y_1=48y_0 \text{ is a solution of the diophantine equation}$$
  
  The solutions are given by the formulas:
  
  $$x=48x_0+18k , y=48y_0+5k, k \in \mathbb{Z}$$
  
  $$x>0 \Rightarrow 48x_0+18k>0 \Rightarrow k>-\frac{48x_0}{18}$$
  
  $$y>0 \Rightarrow 48y_0+5k>0 \Rightarrow k>-\frac{48y_0}{5}$$
  
  $$ \text{ Therefore, }k> \max \{ -\frac{48x_0}{18}, -\frac{48y_0}{5}\}$$
  
• $$gcd(158,57)=1, \text{ so the diophantine equation } 158x-57y=7 \text{ has infinite solutions.}$$
  
  Since, $gcd(158,57)=1$, $\exists x_0,y_0 \text{ such that } 158x_0+57y_0=1 \Rightarrow 158(7 x_0)-57(-7y_0)=7$
  
  So,$x_1=7x_0 \text{ and } y_1=-7y_0$ is a solution of the diophantine equation.
  
  So,the solutions from $ 158x-57y=7$ are given by the formulas:
  
  $$x=7x_0+158k, y=-7y_0+57k , k \in \mathbb{Z}$$
  
  $$x>0 \Rightarrow k > \frac{-7x_0}{158}$$
  
  $$y>0 \Rightarrow k>\frac{7y_0}{57}$$
  
  Therefore, $k>\max \{ \frac{-7x_0}{158},\frac{7y_0}{57} \}$

Could you tell me if it is right or if I have done something wrong? (Thinking)

 

[evinda]

I thought about it again and now I think that it is like that:

The solutions of the diophantine equation $18x+5y=48$ are given by the formulas:

$$x=48x_0+5k, y=48y_0+18k, \text{ with } k> \max \{ \frac{-48x_0}{18}, \frac{-48y_0}{5}\}$$

and the solutions of the diophantine equation $158x-57y=7$ are given by the formulas:

$$x=7x_0+57k, y=-7y_0+158k, \text{ with } k> \max \{ \frac{-7x_0}{158},\frac{7y_0}{57} \}$$

Am I right? (Blush)

 

[individ]

Equation: \(\displaystyle 18x+5y=48\)

Has the solution:

\(\displaystyle x=5k+1\)

\(\displaystyle y=6-18k\)

equation: \(\displaystyle 158x-57y=7\)

Decisions no.

 

[I like Serena]

Hey! (Smile)

I thought about it again and now I think that it is like that:

The solutions of the diophantine equation $18x+5y=48$ are given by the formulas:

$$x=48x_0+5k, y=48y_0+18k, \text{ with } k> \max \{ \frac{-48x_0}{18}, \frac{-48y_0}{5}\}$$

Let's substitute your solution:
$$18(48x_0+5k)+5(48y_0+18k)=48$$
$$48(18x_0+5y_0)+18\cdot 5k +18\cdot 5k=48$$
Hmm... that left hand side becomes bigger whenever we pick $k$ bigger.
That can't be right! (Worried)

And what are $x_0$ and $y_0$?
Can you apply the Euclidean algorithm? (Thinking)

 

[evinda]

Hey! (Smile)
Let's substitute your solution:
$$18(48x_0+5k)+5(48y_0+18k)=48$$
$$48(18x_0+5y_0)+18\cdot 5k +18\cdot 5k=48$$
Hmm... that left hand side becomes bigger whenever we pick $k$ bigger.
That can't be right! (Worried)

And what are $x_0$ and $y_0$?
Can you apply the Euclidean algorithm? (Thinking)

I found it like that:

$$18=5 \cdot 3+3$$
$$5=3 \cdot 1+ 2$$
$$3= 2 \cdot 1 + 1$$
$$2=2 \cdot 1+0$$

So, $gcd(18,5)=1$

So, $\exists x_0,y_0$ such that:
$$18x_0+5y_0=1 \Rightarrow 18(48x_0)+5(48y_0)=48$$

Therefore $\displaystyle{x_1=48x_0 , y_1=48y_0} \text{ is a solution of the diophantine equation } 18x+5y=48 $

So,the solutions of $18x+5y=48$ are given by the formulas:

$$x=x_1+kb_1 ,y=y_1-ka_1$$

$$a_1=18, b_1=5$$

So, $x=48x_0+5k ,y=48y_0-18k$

$$x>0 \Rightarrow k>\frac{-48x_0}{5} , y>0 \Rightarrow k< \frac{48y_0}{18} \Rightarrow \frac{-48x_0}{5}<k<\frac{48y_0}{18}$$

Have I done something wrong? (Thinking) (Thinking) (Thinking)

 

[Nono713]

One way of arriving at a result:
$$18x + 5y = 48 ~ ~ \iff ~ ~ 18(x - 1) + 5y = 30 ~ ~ \iff ~ ~ 18(x - 1) + 5(y - 6) = 0 ~ ~ \iff ~ ~ 18(x - 1) = 5(6 - y)$$
Substitute $u = x - 1$, $v = 6 - y$, then we must solve $18u = 5v$. The intersection of the set $\{ 18u \mid u \in \mathbb{Z} \}$ and $\{ 5v \mid v \in \mathbb{Z} \}$ is the set of integers that are multiples of both $18$ and $5$. Now $\mathrm{lcm}(18, 5) = 18 \times 5 = 90$ since they are coprime, so the intersection consists of the multiples of $90$, that is, the solutions are $(u, v) = (5n, 18n)$ for all $n \in \mathbb{Z}$. Substituting back, $(x, y) = (5n + 1, 6 - 18n)$. And finally, adding the range constraints:
$$5n + 1 > 0 ~ ~ \implies ~ ~ 5n > 1 ~ ~ \implies ~ ~ n \geq 0$$
$$6 - 18n > 0 ~ ~ \implies ~ ~ 18n < 6 ~ ~ \implies n < 1$$
Therefore $0 \leq n < 1$, and so there is a unique solution at $n = 0$, which is $(u, v) = (0, 0)$, so $(x, y) = (1, 6)$.

This is what the first few solutions look like (note no other solution has both $x$ and $y$ positive):

(-9, 42)
(-4, 24)
(1, 6)
(6, -12)
(11, -30)
(16, -48)

Here it's the range constraint that is killing all the solutions except the smallest one: without it, you would indeed have infinitely many solutions. Remember: Bézout's identity considers all integers, both positive and negative (since it operates on a principal ideal domain, in this case the ring of integers) so it does not apply directly to natural numbers - you need to check that separately.

Once you work out a systematic technique to solve a diophantine equation of the form $ax + by = c$ with $\gcd(a, b) = 1$ (and generalized it to handle the case where $\gcd(a, b) > 1$, with constraints on $c$ for the existence of a solution) you will have rediscovered the extended Euclidean algorithm :)

For this problem it was a bit simpler because the linear combination of $18$ and $5$ that gave $48$ was obvious - in the general case you would work out that linear combination via extended Euclid, as said above).​

 

[evinda]

And..that's how I found the solutions for the second diophantine equation:

$$158=57 \cdot 2+44$$

$$57=44 \cdot 1+13$$

$$44=13 \cdot 3+5$$

$$13=5 \cdot 2+3$$
$$5=3 \cdot 1+2$$

$$3=2 \cdot 1+1$$
$$2=2 \cdot 1+ 0$$

So, $gcd(158,57)=1$

$$\text{So , }\exists x_0, y_0 \text{ such that : } 158x_0+57y_0=1 \Rightarrow 158(7x_0)-57(-7y_0)=7 $$

$$\text{So, } x_1=7x_0 , y_1=-7y_0 \text{ is a solution of the diophantine equation: } 158x-57y=7$$

$$a_1=158, b_1=57$$

$$\text{So, } x=7x_0+57k , y=-7y_0+158k \text{ are the solutions of the diophantine equation } 158x-57y=7$$

$$x>0 \Rightarrow 7x_0+57k>0 \Rightarrow k>\frac{-7x_0}{57}, y>0 \Rightarrow -7y_0+158k>0 \Rightarrow k>-\frac{7y_0}{158} \Rightarrow k>\max \{\frac{-7x_0}{57},\frac{7y_0}{158} \}$$

 

[I like Serena]

I found it like that:

$$18=5 \cdot 3+3$$
$$5=3 \cdot 1+ 2$$
$$3= 2 \cdot 1 + 1$$
$$2=2 \cdot 1+0$$

So, $gcd(18,5)=1$

So, $\exists x_0,y_0$ such that:
$$18x_0+5y_0=1 \Rightarrow 18(48x_0)+5(48y_0)=48$$

Sorry. (Blush)

I meant the Extended Euclidean algorithm.
It means you keep track of a linear combination from step to step.

Let me show you:
\begin{array}{| l | r c r l l |}
\hline
\text{Euclidean algorithm} & \text{Extended} \\
\hline
18=5 \cdot 3+3 & 18&=&1 \cdot 18 \\
5=3 \cdot 1+ 2 & 5 &= & && 1 \cdot 5 \\
3= 2 \cdot 1 + 1 & 3 &=& 1\cdot 18 &-& 3 \cdot 5 \\
2=2 \cdot 1+0 & 2 &=& -1 \cdot 18 &+& 4 \cdot 5 \\
& 1 &=& 2 \cdot 18 &-&7 \cdot 5 \\
\hline
\end{array}

Can you see what $x_0$ and $y_0$ should be now? (Thinking)

So,the solutions of $18x+5y=48$ are given by the formulas:

$$x=x_1+kb_1 ,y=y_1-ka_1$$

$$a_1=18, b_1=5$$

So, $x=48x_0+5k ,y=48y_0-18k$

$$x>0 \Rightarrow k>\frac{-48x_0}{5} , y>0 \Rightarrow k< \frac{48y_0}{18} \Rightarrow \frac{-48x_0}{5}<k<\frac{48y_0}{18}$$

Have I done something wrong? (Thinking) (Thinking) (Thinking)

You fixed the minus sign! Much better! (Angel)

 

[evinda]

Sorry. (Blush)

I meant the Extended Euclidean algorithm.
It means you keep track of a linear combination from step to step.

Let me show you:
\begin{array}{| l | r c r l l |}
\hline
\text{Euclidean algorithm} & \text{Extended} \\
\hline
18=5 \cdot 3+3 & 18&=&1 \cdot 18 \\
5=3 \cdot 1+ 2 & 5 &= & && 1 \cdot 5 \\
3= 2 \cdot 1 + 1 & 3 &=& 1\cdot 18 &-& 3 \cdot 5 \\
2=2 \cdot 1+0 & 2 &=& -1 \cdot 18 &+& 4 \cdot 5 \\
& 1 &=& 2 \cdot 18 &-&7 \cdot 5 \\
\hline
\end{array}

Can you see what $x_0$ and $y_0$ should be now? (Thinking)

Oh,yes! Sorry! I forgot it... (Blush) $x_0=2, y_0=-7$

You fixed the minus sign! Much better! (Angel)

So,now it is
$$ \frac{-48x_0}{18}<k<\frac{48y_0}{18} \Rightarrow \frac{-48}{9} < k< -\frac{336}{18}$$

So,there are no solutions,or am I wrong?? (Thinking) (Thinking)

 

[I like Serena]

Oh,yes! Sorry! I forgot it... (Blush) $x_0=2, y_0=-7$

Good!

So,now it is
$$ \frac{-48x_0}{18}<k<\frac{48y_0}{18} \Rightarrow \frac{-48}{9} < k< -\frac{336}{18}$$

So,there are no solutions,or am I wrong?? (Thinking) (Thinking)

Well... (Thinking)
We have:
$$18x+5y=48$$
If we pick $x=1$ and $y=6$ we have a solution! (Doh)

 

[individ]

I don't understand. Why such a simple equation so long to decide?
The solution was recorded immediately!

 

[Nono713]

I don't understand. Why such a simple equation so long to decide?
The solution was recorded immediately!

I think the idea is to convey an understanding of why and how this solution was determined to evinda. Just giving the solution with no explanation is not particularly useful to furthering that understanding, you know, the whole give a man a fish thing (and ILS seems to have taken a liking to tutoring evinda :p)

edit: this isn't the challenge questions subforum

 

[evinda]

Good!

Well... (Thinking)
We have:
$$18x+5y=48$$
If we pick $x=1$ and $y=6$ we have a solution! (Doh)

But..how can this be? (Thinking) Isn't it $\frac{-48}{9}<k<\frac{-16}{3}$ ? So,do we take $k=\frac{-16}{3}$, and this will be the only $k$, for which we have a solution??

 

[I like Serena]

But..how can this be? (Thinking) Isn't it $\frac{-48}{9}<k<\frac{-16}{3}$ ? So,do we take $k=\frac{-16}{3}$, and this will be the only $k$, for which we have a solution??

There must be a mistake somewhere! (Sweating)

What would the value of $k$ be that would yield $x=1$ and $y=6$?

What would you get if you fill in $k=\frac{-16}3$?

 

[evinda]

There must be a mistake somewhere! (Sweating)

What would the value of $k$ be that would yield $x=1$ and $y=6$?

What would you get if you fill in $k=\frac{-16}3$?

I tried it again and I found:

$$x=2 \cdot 48+5k, y=-7 \cdot 48-18k$$

$$x>0 \Rightarrow k> \frac{-96}{5}$$

$$y>0 \Rightarrow k<\frac{-56}{3}$$

So,it is:

$$\frac{-96}{5}<k< \frac{-56}{3} \Rightarrow k=-19$$

$$\text{For } k=-19, \text{ we get : } x=1,y=6 \text{ ! } $$

(Happy)

 

[evinda]

I tried also again to solve the second diophantine equation.
That's what I did:

$$158x-57y=7$$

$$gcd(158,57)=1, \text{ so } \exists x_0,y_0 \text{ such that } 158x_0+57y_0=1$$

From the Extended Euclidean algorithm,it is like that:

$$(-22) \cdot 158-57 \cdot (-61)=1 \Rightarrow x_0=-22 , y_0=-61$$

$$(-22 \cdot 7) \cdot 158-57 \cdot (-7 \cdot 61)=7$$

So, $\displaystyle{x_1=-154 , y_1=-427} \text{ is a solution of the diophantine equation.}$

Therefore,the solutions are given by the formulas:

$$x=-154+57k , y=-427+158k $$

$$x>0 \Rightarrow k>\frac{154}{57} \Rightarrow k \geq 3$$

$$y>0 \Rightarrow k>\frac{427}{158} \Rightarrow k \geq 3$$

So,it must be $k \geq 3$.

Is it right or have I done something wrong? (Thinking)

 

[I like Serena]

$$\text{For } k=-19, \text{ we get : } x=1,y=6 \text{ ! } $$

(Happy)

Good! (Nod)

I tried also again to solve the second diophantine equation.
That's what I did:

$$158x-57y=7$$

$$gcd(158,57)=1, \text{ so } \exists x_0,y_0 \text{ such that } 158x_0+57y_0=1$$

From the Extended Euclidean algorithm,it is like that:

$$(-22) \cdot 158-57 \cdot (-61)=1 \Rightarrow x_0=-22 , y_0=-61$$

$$(-22 \cdot 7) \cdot 158-57 \cdot (-7 \cdot 61)=7$$

So, $\displaystyle{x_1=-154 , y_1=-427} \text{ is a solution of the diophantine equation.}$

Therefore,the solutions are given by the formulas:

$$x=-154+57k , y=-427+158k $$

$$x>0 \Rightarrow k>\frac{154}{57} \Rightarrow k \geq 3$$

$$y>0 \Rightarrow k>\frac{427}{158} \Rightarrow k \geq 3$$

So,it must be $k \geq 3$.

Is it right or have I done something wrong? (Thinking)

Looks good... (Sweating)

Which solution do you get if you fill in $k=3$?
Does the solution fit the original equation? (Wondering)

How about $k=4$? (Wondering)

 

[evinda]

Good! (Nod)

Looks good... (Sweating)

Which solution do you get if you fill in $k=3$?
Does the solution fit the original equation? (Wondering)

How about $k=4$? (Wondering)

For $k=3$,we get:

$$x=17, y=47$$

$$158x-57y=158 \cdot 17-57 \cdot 47=7 \checkmark$$

For $k=4$,we get:

$$x=74, y=205$$

$$158 \cdot 74-57 \cdot 205=7 \checkmark $$

So,is it right? (Nerd)

 

[I like Serena]

Yep!
You have just verified that you did not make mistakes. (Mmm)

 

[evinda]

Yep!
You have just verified that you did not make mistakes. (Mmm)

Great! (Clapping)(Clapping) Thank you very much! (Smile)