Results 1 to 5 of 5

Thread: 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 $\displaystyle \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

    $\displaystyle \begin{array}{lcl}
    \mathrm{gcd}(238965,54735) &=& \mathrm{gcd}(54735,20025)\\
    &=& \mathrm{gcd}(20025,14685)\\
    &=& \mathrm{gcd}(14685,5340)\\
    &=& \mathrm{gcd}(5340,4005)\\
    &=& \mathrm{gcd}(4005,1335)\\
    &=& 1335
    \end{array}
    $
    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 $\displaystyle \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 $\displaystyle u a+v b=c$ with $\displaystyle u,v, a,b,c\in \mathbb{Z}$.
    First, $\displaystyle c$ must be a multiple of $\displaystyle \mathrm{gcd}(u,v)$ for integer solutions $\displaystyle a,b\in\mathbb{Z}$ to exist: because the left side of the equation is obviously an integer multiple of $\displaystyle \mathrm{gcd}(u,v)$, if $\displaystyle a,b\in\mathbb{Z}$
    In your case, with $\displaystyle 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 $\displaystyle u a+vb=0$ and

    2. finding a single, aka. "particular" solution of the original equation $\displaystyle 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 $\displaystyle ua+vb=0$. Obviously $\displaystyle ua$ and $\displaystyle vb$ must be simultaneously integers and multiples of each other. Therefore the "smallest" integer solution has the form $\displaystyle 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 $\displaystyle (x,y)$ of the equation $\displaystyle ux+vy=\mathrm{gcd}(u,v)$. Then you multiply that pair $\displaystyle (x,y)$ of integers with $\displaystyle \tfrac{c}{\mathrm{gcd}(u,v)}$ to get the desired particular solution of the orignal equation. Let's call it $\displaystyle (a_p,b_p)$.

    Finally to write down the general solution of the original equation, which is $\displaystyle 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; Aug 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
    12,028
    Thanks
    848
    Hello, geo2!

    3) Find the solution to the linear congruence: .$\displaystyle 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: .$\displaystyle 54,\!735a + 238,\!965b \;=\;16,\!020$

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

    Solve for $\displaystyle 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 $\displaystyle a$ is an integer, $\displaystyle 4-5b$ must be a multiple of 41.

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

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

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


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

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


    The solutions are: . $\displaystyle \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.


    . . $\displaystyle \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: Sep 30th 2010, 10:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 14th 2010, 06:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 5th 2010, 06:45 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jan 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