Euclidean algorithm

• Oct 6th 2012, 12:00 PM
Petrus
Euclidean algorithm
Determine all heltallösningar the Diophantine equation https://webwork.math.su.se/webwork2_...dd8b877591.png such that both x and y is between 100 and 380 (including 100 and 380).
i wanna solve this problem with
Euclidean algorithm
• Oct 6th 2012, 12:04 PM
Petrus
Re: Euclidean algorithm
my guess
5=4*1+1
4=4*1

1=5-4
then im lost
• Oct 7th 2012, 01:55 AM
Petrus
Re: Euclidean algorithm
plz some1 help me i need to solve this question today!
• Oct 7th 2012, 04:02 AM
BobP
Re: Euclidean algorithm
I don't know whether this is the method you're supposed to use, but it works.
You have 5 - 4 = 1 , so, 1000*5 - 1000*4 = 1000. .................... (1)
Also , 4*5 - 5*4 = 0, so 4n*5 - 5n*4 = 0 for any n, .................. (2)
Subract (2) from (1) and you have
(1000 - 4n)*5 - (1000 - 5n)*4 = 1000.
or,
(5n - 1000)*4 - (4n - 1000)*5 = 1000.
Now work out what value(s) you need for n.
• Oct 7th 2012, 04:18 AM
Petrus
Re: Euclidean algorithm
any1 know how i can use this on my way goosh this is geting anoying and im confused
• Oct 7th 2012, 04:55 AM
TheEmptySet
Re: Euclidean algorithm
Quote:

Originally Posted by Petrus
any1 know how i can use this on my way goosh this is geting anoying and im confused

Where are you confused? Bob has given you a way to find the solution! If you don't tell us what you don't understand it is impossible to help you.

Facts you should know from lecture or your text book are:

if $\displaystyle ax+by=c$

The Ecliddean alogrithm can find the GCD of a and b and express them as

(1) $\displaystyle ax_0+by_0=\gcd(a,b)$

If the GCD does not divide c the equation has no integer solutions if it does then there exists an integer q such that

$\displaystyle q \cdot \gcd(a,b)=c$

If we multiply equation (1) by q this gives

$\displaystyle a(x_0q)+b(y_0q)=c$

Now

$\displaystyle x_0q$ and $\displaystyle y_0q$ are a solution of the problem.

All other solutions can be found using the formula (this should also be in your text book or notes)

$\displaystyle x=qx_0+m\cdot \left( \frac{b}{\gcd(a,b)}\right)$ and

$\displaystyle y=qy_0-m\cdot \left( \frac{a}{\gcd(a,b)}\right)$

Where m is some integer.

P.S this is exactly the solution Bob gave you.

Try to work these steps, and if you get stuck post back with your work so we can see what you have tried.
• Oct 7th 2012, 05:13 AM
Petrus
Re: Euclidean algorithm
idk but im familiar with this thing... this is how i use to solve it and teacher solved problem like this.... idk but im really confused what i shall do next on that problem
17x+6y=250
particulate solve:
17x+6y=0
17=2*6+5
6=1*5+1
(backwards)
5=17-2*6
1=6-5
(now we use this backwards)
1=6-5 (we can rewrite 5 with 5=17-2*6)
1=6-(17-2*6)
1=3*6-1*17 (just gather all 6's)
homogeneous solve
17x+6y=250
x=-250+6k (remember the y=-1)
y=750-17k (remember x=3)
• Oct 7th 2012, 06:40 AM
Soroban
Re: Euclidean algorithm
Hello, Petrus!

Here is a very primitive solution . . .

Quote:

Determine all solutions the Diophantine equation: $\displaystyle 4x - 5y \:=\:1000$
such that both $\displaystyle x$ and $\displaystyle y$ are between 100 and 380 inclusive.

I want to solve this problem with the Euclidean algorithm.

Solve for $\displaystyle y\!:\;\;y \:=\:\frac{4x}{5} - 200$ .[1]

Since $\displaystyle y$ is an integer, $\displaystyle x$ must be a multiple of 5: .$\displaystyle x = 5a$

Then [1] becomes: .$\displaystyle y \:=\:4a-200$

Now we have:
. . . . . . . . . .$\displaystyle \begin{array}{c} 100 \:\le\:y \:\le\:380 \\ \\[-4mm] 100 \:\le\:4a-200 \:\le\:380 \\ \\[-4mm] 300 \:\le\:4a \:\le \:580 \\ \\[-4mm] {\color{blue}75 \:\le\:a}\:\le\:145 \end{array}$

We also have:
. . . . . . . . . . . . $\displaystyle \begin{array}{c} 100\:\le\:x\:\le\:380 \\ \\[-4mm] 100 \:\le\:5a\:\le\:390 \\ \\[-4mm] 20 \:\le\:{\color{blue}a\:\le\:76} \end{array}$

Hence: .$\displaystyle 75\,\le\,a\,\le\,76 \quad\Rightarrow\quad a \:=\:75,\,76$

$\displaystyle \text{If }a = 75\!:\;(x,y) \:=\:(375,\,100)$

$\displaystyle \text{If }a = 76\!:\;(x,y) \:=\:(380,\,104)$