# Diophantine equation

• Dec 13th 2006, 03: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, 06: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,
$\gcd(25,35)$
Apply Euclidean algorithm,
$35=1\cdot 25+10$
$25=2\cdot 10+5$
$10=2\cdot 5 + 0$
Now work backwards,
$5=25-2\cdot 10$
$5=25-2(35-25)$
$5=25-2\cdot 35+2\cdot 25$
$5=3\cdot 25-2\cdot 35$
Thus,
$25(3)+35(-2)=5$
Multiply by 76,
$25(228)+35(-152)=380$
Thus,
$x=228+(35/5)t=228+7t$
$y=-152-(25/5)t=-152-5t$
• Dec 13th 2006, 06: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, 09:47 PM
Soroban
Hello, math_cali!

Quote:

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

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

• Dec 13th 2006, 10: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, 08:57 AM
Soroban
Hello, math_cali!

Here's a really primitive approach . . .

Quote:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Since $x$ and $y$ must be positive integers:
. . $\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: . $\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, 12:13 PM
ThePerfectHacker
Quote:

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