Results 1 to 5 of 5

Math Help - Euclidean algorithm

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    14

    Euclidean algorithm

    Please someone help me with this I am confused

    1) find the Highest common Factor of 54735 and 238965
    2) find the Lowest Common Multiple of 54735 and 238965
    3) find the solution to the linear congruence 54735a + 238965b = 16020

    and finally explain why there are an infinite number of solution to this linear congruence and find one more solution?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by geo2 View Post
    Please someone help me with this I am confused

    1) find the Highest common Factor of 54735 and 238965
    To determine \mathrm{gcd}(a,b) you repeatedly replace the larger of the two numbers by the remainder of the larger divided by the smaller .. until the lager is a multiple of the smaller. In your case I get

    \begin{array}{lcl}<br />
\mathrm{gcd}(238965,54735) &=& \mathrm{gcd}(54735,20025)\\<br />
&=& \mathrm{gcd}(20025,14685)\\<br />
&=& \mathrm{gcd}(14685,5340)\\<br />
&=& \mathrm{gcd}(5340,4005)\\<br />
&=& \mathrm{gcd}(4005,1335)\\<br />
&=& 1335<br />
\end{array}<br />
    The last equality sign holds, because 4005 is a multiple of 1335.

    2) find the Lowest Common Multiple of 54735 and 238965
    Just remember that \mathrm{lcm}(a,b)=\frac{a\cdot b}{\mathrm{gcd}(a,b)}

    3) find the solution to the linear congruence 54735a + 238965b = 16020

    and finally explain why there are an infinite number of solution to this linear congruence and find one more solution?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    14
    thanks for the help!!for the third one you know what i have to do??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by geo2 View Post
    Please someone help me with this I am confused

    3) find the solution to the linear congruence 54735a + 238965b = 16020

    and finally explain why there are an infinite number of solution to this linear congruence and find one more solution?
    So let's consider an equation of the form u a+v b=c with u,v, a,b,c\in \mathbb{Z}.
    First, c must be a multiple of \mathrm{gcd}(u,v) for integer solutions a,b\in\mathbb{Z} to exist: because the left side of the equation is obviously an integer multiple of \mathrm{gcd}(u,v), if a,b\in\mathbb{Z}
    In your case, with u=54735, v = 238965, c = 16020, \mathrm{gcd}(u,v)=1335 this condition is satisfied.

    Now you separate the problem of finding the general solution into two parts:
    1. finding the general solution of the associated homogeneous equation u a+vb=0 and

    2. finding a single, aka. "particular" solution of the original equation ua+vb=c.
    Since the difference of two solutions of the original equation is a solution of the associated homogeneous equation, you then have found the general solution of the original equation: which is the sum of your particular solution of the original equation and the general solution of the homogeneous equation.

    Ad 1.: Finding the general solution of the homogeneous equation ua+vb=0. Obviously ua and vb must be simultaneously integers and multiples of each other. Therefore the "smallest" integer solution has the form a := \tfrac{v}{\mathrm{gcd}(u,v)}, b := -\tfrac{u}{\mathrm{gcd}(u,v)}. The general solution of the homogeneous equation is an arbitrary integral multiple of this.

    Ad 2.: You need to execute the extended version of the Euclidian Algorithm to find a solution (x,y) of the equation ux+vy=\mathrm{gcd}(u,v). Then you multiply that pair (x,y) of integers with \tfrac{c}{\mathrm{gcd}(u,v)} to get the desired particular solution of the orignal equation. Let's call it (a_p,b_p).

    Finally to write down the general solution of the original equation, which is a := a_p+\tfrac{v}{\mathrm{gcd}(u,v)}\cdot n, b := b_p-\tfrac{u}{\mathrm{gcd}(u,v)}\cdot n, n\in \mathbb{Z}.
    Last edited by Failure; August 8th 2009 at 10:05 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    645
    Hello, geo2!

    3) Find the solution to the linear congruence: . 54,\!735a + 238,\!965b \:=\: 16,\!020

    Explain why there are an infinite number of solutions to this linear congruence
    and find one more solution.

    We have: . 54,\!735a + 238,\!965b \;=\;16,\!020

    Divide by 1335: . 41a + 179b \;=\;12

    Solve for a\!:\quad{\color{blue}[1]}\;a \:=\:\frac{12-179b}{41} \;=\;-4b + \frac{12-15b}{41} \quad\Rightarrow\quad a \;=\;-4b + \frac{3(4-5b)}{41}

    Since a is an integer, 4-5b must be a multiple of 41.

    . . That is: . 4-5b \:=\:41c \quad\Rightarrow\quad{\color{blue}[2]}\;b \:=\:\frac{4-41c}{5} \quad\Rightarrow\quad b \;=\;-8c + \frac{4-c}{5}

    Since b is an integer, 4-c must be a multiple of 5.

    This happens if: . c \;=\;-1+5m\;\text{ for some integer }m


    Substitute into [2]: . b \;=\;\frac{4-41(-1+5m)}{5} \quad\Rightarrow\quad\boxed{ b \:=\:9-41m }

    Substitute into [1]: . a \;=\;\frac{12 - 179(9-41m)}{41} \quad\Rightarrow\quad\boxed{ a \;=\;\text{-}39 + 179m}


    The solutions are: . \boxed{\begin{array}{ccc}a&=& \text{-}39 + 179m \\ b &=& 9-41m \end{array}\;\text{ for {\color{red}any} integer }m}

    And that's why there is an infinite number of solutions.


    . . \begin{array}{|c|c|} \hline m & (a,b) \\ \hline \hline 0 & (\text{-}39,9) \\ 1 & (140,\text{-}32) \\ \vdots & \vdots \end{array}

    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: September 14th 2010, 06:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  5. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:20 AM

Search Tags


/mathhelpforum @mathhelpforum