Results 1 to 6 of 6

Math Help - 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
    4
    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
    11,914
    Thanks
    779
    Hello, ruprotein!

    Is there a typo in #1?


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

    (a) Find g.

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

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


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

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

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

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

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


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

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

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

    Check

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

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

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

    . . . . . . = \;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,
    242=1\cdot 142+100
    142=1\cdot 100+42
    100=2\cdot 42+ 16
    42=2\cdot 16+10
    16=1\cdot 10+6
    10=1\cdot 6+4
    6=1\cdot 4+2
    4=2\cdot 2+0
    Ah! The gcd is 2.

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

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

    Now, we can use the identity for continued fractions,
    p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}=-1
    Thus,
    121(27)-71(46)=1
    Multiply by 2 (gcd) to make numbers appear,
    242(27)-142(46)=2
    Thus,
    242(27)+142(-46)=2
    Thus,
    242x+142y=2
    For (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
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    Euclidean algorithm,
    242=1\cdot 142+100
    142=1\cdot 100+42
    100=2\cdot 42+ 16
    42=2\cdot 16+10
    16=1\cdot 10+6
    10=1\cdot 6+4
    6=1\cdot 4+2
    4=2\cdot 2+0
    Ah! The gcd is 2.

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

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

    Now, we can use the identity for continued fractions,
    p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}=-1
    Thus,
    121(27)-71(46)=1
    Multiply by 2 (gcd) to make numbers appear,
    242(27)-142(46)=2
    Thus,
    242(27)+142(-46)=2
    Thus,
    242x+142y=2
    For (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