Results 1 to 8 of 8

Math Help - Euclidean algorithm

  1. #1
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Euclidean algorithm

    Determine all heltallösningar the Diophantine equation such that both x and y is between 100 and 380 (including 100 and 380).
    i wanna solve this problem with
    Euclidean algorithm
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Re: Euclidean algorithm

    my guess
    5=4*1+1
    4=4*1

    1=5-4
    then im lost
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Re: Euclidean algorithm

    plz some1 help me i need to solve this question today!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2009
    Posts
    660
    Thanks
    133

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Re: Euclidean algorithm

    any1 know how i can use this on my way goosh this is geting anoying and im confused
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    Re: Euclidean algorithm

    Quote Originally Posted by Petrus View Post
    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 ax+by=c

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

    (1) 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

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

    If we multiply equation (1) by q this gives

    a(x_0q)+b(y_0q)=c

    Now

    x_0q and 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)


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


    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    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)
    Last edited by Petrus; October 7th 2012 at 05:21 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,807
    Thanks
    697

    Re: Euclidean algorithm

    Hello, Petrus!

    Here is a very primitive solution . . .


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

    I want to solve this problem with the Euclidean algorithm.

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

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

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


    Now we have:
    . . . . . . . . . . \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:
    . . . . . . . . . . . . \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: . 75\,\le\,a\,\le\,76 \quad\Rightarrow\quad a \:=\:75,\,76


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

    \text{If }a = 76\!:\;(x,y) \:=\:(380,\,104)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 10:46 AM
  2. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 19th 2010, 11:13 AM
  3. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  4. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 29th 2009, 11:51 AM
  5. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 10th 2008, 08:17 PM

Search Tags


/mathhelpforum @mathhelpforum