Results 1 to 6 of 6

Thread: Gcd

  1. #1
    Junior Member
    Joined
    Dec 2006
    Posts
    48

    Gcd

    Let a = 242, b = 142. Let g be the gretest common divisor of a and b, Find g, and find integers m,n such that g = m*a+n*n

    I found g = 2

    So 2 = 242m + n^2

    how can i find m and n?

    Also what is the fastest way to prove the following:

    if a,b are integers, g is a natural number, and g is the GCD of a and b, then there exist integrs m,n suc that g = m*a+n*b?

    Everywhere i check online they are giving me longgggg solutions,but what if this question was given on an exam that is an hour long, i had it on my midterm this semester
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by ruprotein View Post
    Also what is the fastest way to prove the following:

    if a,b are integers, g is a natural number, and g is the GCD of a and b, then there exist integrs m,n suc that g = m*a+n*b?

    Everywhere i check online they are giving me longgggg solutions,but what if this question was given on an exam that is an hour long, i had it on my midterm this semester
    I don't know if this is the fastest method of proving it, but:

    A way to prove it is by considering the Extended Euclidean Algorithm, which
    gives a decreasing sequence of positive integers g_k:

    g_k=m_k*a+n_k*b

    (with m_k and n_k integers) each of which is divisible by the gcd(a,b), and
    if g_k>g another step can always be performed, so the sequence eventualy
    reaches a k such that g_k=g.

    A not very clear explanation of the EEA can be found here.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, ruprotein!

    Is there a typo in #1?


    Let $\displaystyle a = 242,\;b = 142.$
    Let $\displaystyle g$ be the greatest common divisor of $\displaystyle a$ and $\displaystyle b$.

    (a) Find $\displaystyle g$.

    (b) Find integers $\displaystyle m,\,n$ such that: .$\displaystyle g \:= \:m\cdot a + n\cdot \bf{b}$
    typo?

    (a) You already found that: $\displaystyle GCD(242,\,142)\:=\:2$


    (b) We want integers $\displaystyle m$ and $\displaystyle n$ so that: .$\displaystyle 242m + 142n \:=\:2$ [1]

    We have: .$\displaystyle 121m - 1 \:=\:71n$

    . . Then: .$\displaystyle 121m \:\equiv \:1 \pmod{71} $

    Multiply both sides by $\displaystyle 27\!:\;\;1350m \:\equiv \:27\!\!\pmod{71}\quad\Rightarrow\quad m \:\equiv \:27\!\!\pmod{71}$

    . . Hence: .$\displaystyle \boxed{m \:=\:27 + 71a}$ for any integer $\displaystyle a.$


    Substitute into [1]: .$\displaystyle 242(27 + 71a) + 142n \:=\:2$

    . . Hence: .$\displaystyle \boxed{n \:=\:\text{-}46 - 121a}$ for any integer $\displaystyle a.$

    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    Check

    Substitute into [1]: .$\displaystyle 242m + 142n \:=\:2$

    We have: .$\displaystyle 242(27 + 71a) + 142(-46 - 121a)$

    . . . . . .$\displaystyle = \:6534 + 17182 a - 6532 - 17182a$

    . . . . . .$\displaystyle = \;2$ . . . check!

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10

    Thumbs up

    Quote Originally Posted by ruprotein View Post
    Let a = 242, b = 142. Let g be the gretest common divisor of a and b, Find g, and find integers m,n such that g = m*a+n*n
    Euclidean algorithm,
    $\displaystyle 242=1\cdot 142+100$
    $\displaystyle 142=1\cdot 100+42$
    $\displaystyle 100=2\cdot 42+ 16$
    $\displaystyle 42=2\cdot 16+10$
    $\displaystyle 16=1\cdot 10+6$
    $\displaystyle 10=1\cdot 6+4$
    $\displaystyle 6=1\cdot 4+2$
    $\displaystyle 4=2\cdot 2+0$
    Ah! The gcd is 2.

    That means that,
    $\displaystyle 242/142=[1;1,2,2,1,1,1,2]$

    Thus,
    $\displaystyle p_0=a_0$
    $\displaystyle p_1=a_1a_0+1$
    $\displaystyle p_k=a_kp_{k-1}+p_{k-2}, k\geq 2$
    Using this relations we find,
    $\displaystyle p_0=1$
    $\displaystyle p_1=1\cdot 1 +1=2$
    $\displaystyle p_2=2\cdot 2+1=5$
    $\displaystyle p_3=2\cdot 5+2=12$
    $\displaystyle p_4=1\cdot 12+5=17$
    $\displaystyle p_5=1\cdot 17+12=29$
    $\displaystyle p_6=1\cdot 29+17=46$
    $\displaystyle p_7=2\cdot 46+29=121$
    Und,
    $\displaystyle q_0=1$
    $\displaystyle q_1=a_1$
    $\displaystyle q_k=a_kq_{k-1}+q_{k-2}, k\geq 2$
    Using these relations we find,
    $\displaystyle q_0=1$
    $\displaystyle q_1=1$
    $\displaystyle q_2=2\cdot 1+1=3$
    $\displaystyle q_3=2\cdot 3+1=7$
    $\displaystyle q_4=1\cdot 7+3=10$
    $\displaystyle q_5=1\cdot 10+7=17$
    $\displaystyle q_6=1\cdot 17+10=27$
    $\displaystyle q_7=2\cdot 27+17=54+17=71$

    Now, we can use the identity for continued fractions,
    $\displaystyle p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}=-1$
    Thus,
    $\displaystyle 121(27)-71(46)=1$
    Multiply by 2 (gcd) to make numbers appear,
    $\displaystyle 242(27)-142(46)=2$
    Thus,
    $\displaystyle 242(27)+142(-46)=2$
    Thus,
    $\displaystyle 242x+142y=2$
    For $\displaystyle (x,y)=(27,-46)$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    Euclidean algorithm,
    $\displaystyle 242=1\cdot 142+100$
    $\displaystyle 142=1\cdot 100+42$
    $\displaystyle 100=2\cdot 42+ 16$
    $\displaystyle 42=2\cdot 16+10$
    $\displaystyle 16=1\cdot 10+6$
    $\displaystyle 10=1\cdot 6+4$
    $\displaystyle 6=1\cdot 4+2$
    $\displaystyle 4=2\cdot 2+0$
    Ah! The gcd is 2.

    That means that,
    $\displaystyle 242/142=[1;1,2,2,1,1,1,2]$

    Thus,
    $\displaystyle p_0=a_0$
    $\displaystyle p_1=a_1a_0+1$
    $\displaystyle p_k=a_kp_{k-1}+p_{k-2}, k\geq 2$
    Using this relations we find,
    $\displaystyle p_0=1$
    $\displaystyle p_1=1\cdot 1 +1=2$
    $\displaystyle p_2=2\cdot 2+1=5$
    $\displaystyle p_3=2\cdot 5+2=12$
    $\displaystyle p_4=1\cdot 12+5=17$
    $\displaystyle p_5=1\cdot 17+12=29$
    $\displaystyle p_6=1\cdot 29+17=46$
    $\displaystyle p_7=2\cdot 46+29=121$
    Und,
    $\displaystyle q_0=1$
    $\displaystyle q_1=a_1$
    $\displaystyle q_k=a_kq_{k-1}+q_{k-2}, k\geq 2$
    Using these relations we find,
    $\displaystyle q_0=1$
    $\displaystyle q_1=1$
    $\displaystyle q_2=2\cdot 1+1=3$
    $\displaystyle q_3=2\cdot 3+1=7$
    $\displaystyle q_4=1\cdot 7+3=10$
    $\displaystyle q_5=1\cdot 10+7=17$
    $\displaystyle q_6=1\cdot 17+10=27$
    $\displaystyle q_7=2\cdot 27+17=54+17=71$

    Now, we can use the identity for continued fractions,
    $\displaystyle p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}=-1$
    Thus,
    $\displaystyle 121(27)-71(46)=1$
    Multiply by 2 (gcd) to make numbers appear,
    $\displaystyle 242(27)-142(46)=2$
    Thus,
    $\displaystyle 242(27)+142(-46)=2$
    Thus,
    $\displaystyle 242x+142y=2$
    For $\displaystyle (x,y)=(27,-46)$
    Is it just me or is it every time he does his continued fractions approach it seems like the blackest of magics?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by topsquark View Post
    Is it just me or is it every time he does his continued fractions approach it seems like the blackest of magics?
    This is like the third time somebody make a comment to me like that. The joke that they were saying that each time I respond it always involves continued fractions. I really have no idea why most of my posts involve continued fractions. It is funny I know.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum