# Diophantine equation

• Dec 13th 2006, 02:59 PM
math_cali
Diophantine equation
Question:

Find all solutions that are positive integers of the Diophantine equation:

25x + 35y = 380

I need to check my answer. Not sure If I have the correct solutions

x > 0
y > 0

25x + 35 = 380 ==> x = 13.8

25 + 35y = 380 ==> y = 10.14

0 < x < 14
0 < y < 11

25x + 35y = 380 ==> 5x + 7y = 76
25x + 175k + 105 = 380 making
x = 11-7k

25(11) + 35(4) = 275 + 105 = 380
25(4) + 35(8) = 100 + 280 = 380

Solution
K(0,1)
X(11,4)
Y (3,8)

Not sure if I expressed my answer corretly.
• Dec 13th 2006, 05:07 PM
ThePerfectHacker
Quote:

Originally Posted by math_cali
Question:

Find all solutions that are positive integers of the Diophantine equation:

25x + 35y = 380

Now, this is actually the way you can get the answer to the other problem you posted without guessing.
---
There is a cool :eek: way to do these using continued fractions but I do not think you number theory course does those until the end of the semester if not at all.

We need to find,
$\displaystyle \gcd(25,35)$
Apply Euclidean algorithm,
$\displaystyle 35=1\cdot 25+10$
$\displaystyle 25=2\cdot 10+5$
$\displaystyle 10=2\cdot 5 + 0$
Now work backwards,
$\displaystyle 5=25-2\cdot 10$
$\displaystyle 5=25-2(35-25)$
$\displaystyle 5=25-2\cdot 35+2\cdot 25$
$\displaystyle 5=3\cdot 25-2\cdot 35$
Thus,
$\displaystyle 25(3)+35(-2)=5$
Multiply by 76,
$\displaystyle 25(228)+35(-152)=380$
Thus,
$\displaystyle x=228+(35/5)t=228+7t$
$\displaystyle y=-152-(25/5)t=-152-5t$
• Dec 13th 2006, 05:54 PM
math_cali
oh ok thanks alot :) I thought I was suppost to be looking for exact numbers. Now I understand and see how I could apply this in the previous problem I posted
• Dec 13th 2006, 08:47 PM
Soroban
Hello, math_cali!

Quote:

Find all solutions that are positive integers of the Diophantine equation:
. . $\displaystyle 25x + 35y \:= \:380$

I would write them as: .$\displaystyle (x,y) \:=\:(4,8),\:(11,3)$

• Dec 13th 2006, 09:09 PM
math_cali
I kind of understand how I got the solutions when I wrote it out the frist time, but how would you apply the solutions to what ThePerfectHacker showed me when he worked it out?
• Dec 14th 2006, 07:57 AM
Soroban
Hello, math_cali!

Here's a really primitive approach . . .

Quote:

Find all positive integer solutions of: .$\displaystyle 25x + 35y \:= \:380$

Divide by 5: .$\displaystyle 5x + 7y \:=\:76$

Solve for $\displaystyle x\!:\;\;x \:=\:\frac{76-5y}{5}$

This can be written: .$\displaystyle x \:=\:\frac{75+1-10y+3y}{3} \:=\:\frac{75 - 10y + 1 + 3y}{5}\:=\:\frac{75-10y}{5} + \frac{1 + 3y}{5}$

. . Hence: .$\displaystyle x \:=\:15 - 2y + \frac{1+3y}{5}$ [1]

Since $\displaystyle x$ is an integer, $\displaystyle \frac{1+3y}{5}$ must some integer $\displaystyle a.$
. . We have: .$\displaystyle \frac{1+3y}{5}\:=\:a\quad\Rightarrow\quad y \:=\:\frac{5a-1}{3}$

This can be written: .$\displaystyle y \:=\:\frac{3a+2a-3+2}{3}\:=\:\frac{3a-3+2a+2}{3}\:=\:\frac{3a-3}{3} + \frac{2a+2}{3}$

. . Hence: .$\displaystyle y \:=\:a - 1 + \frac{2a+2}{3}$ [2]

Since $\displaystyle y$ is an integer, then $\displaystyle \frac{2a+2}{3}$ must be some integer $\displaystyle b.$

. . We have: .$\displaystyle \frac{2a+2}{3}\:=\:b\quad\Rightarrow\quad a\:=\:\frac{3b-2}{2}$

. . Hence: .$\displaystyle a\:=\:\frac{3b}{2} - 1$ [3]

Since $\displaystyle a$ is an integer, $\displaystyle b$ must be even: .$\displaystyle b\,=\,2k$

Substitute into [3]: .$\displaystyle a \:=\:\frac{3(2k)}{2} - 1\quad\Rightarrow\quad a \:=\:3k-1$

Substitute into [2]: .$\displaystyle y \:=\:(3k-1) - 1 + \frac{2(3k-1) + 2}{3}\quad\Rightarrow\quad y\,=\,5k-2$

Substitute into [1]: .$\displaystyle x\:=\:15 - 2(5k-2) + \frac{1 + 3(5k-2)}{5}\quad\Rightarrow\quad x \:=\:18-7k$

We have found all solutions: .$\displaystyle \begin{Bmatrix}x\:=\:18 - 7k \\ y \:=\:5k-2\end{Bmatrix}$ for any integer $\displaystyle k.$

Since $\displaystyle x$ and $\displaystyle y$ must be positive integers:
. . $\displaystyle \begin{array}{cc}18 - 7k\:>\:0 \\ 5k-2\:>\:0\end{array}\;\;\Rightarrow\;\;\begin{array} {cc}k < \frac{18}{7} \\ k > \frac{2}{5}\end{array}$

And there are only two solutions: .$\displaystyle \begin{array}{cc}k=1: & (11,3) \\ k=2: & (4,8)\end{array}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Of course, this is a long and ponderous method . . . I warned you.

There are far better methods (such as the Euclidean Algorithm).

I wanted to show you that, if desperate,
. . you can baby-talk your way through these problems.

• Dec 14th 2006, 11:13 AM
ThePerfectHacker
Quote:

$\displaystyle x=228+(35/5)t=228+7t$
$\displaystyle y=-152-(25/5)t=-152-5t$
..
We want positive solutions.
$\displaystyle x,y>0$
Thus,
$\displaystyle 228+7t>0$
$\displaystyle -152-5t>0$
Solve,
$\displaystyle t>-32.5.....$
$\displaystyle t<-30.4$
Thus,
$\displaystyle -32.5<t<-30.4$
We need integers.
Those are,
$\displaystyle t=-32,-31$
Put them into the x,y equations to get the two possible solutions.