Results 1 to 3 of 3

Math Help - Problems understanding The Euclidean Algorithm

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    27

    Problems understanding The Euclidean Algorithm

    This is from an earlier hw assignment I got wrong

    prove that for all positive integers a and b, a|b if and only if , gcd(a, b) = a

    first I thought since gcd(a, b) = a. Then a divided into itself and b.

    a|b --> b = ac for some int c

    let f - gcd(a, b) = gcd(a, ac)

    Im not sure I have it right to this point or what to do next>?

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Thetheorycase View Post
    This is from an earlier hw assignment I got wrong

    prove that for all positive integers a and b, a|b if and only if , gcd(a, b) = a

    first I thought since gcd(a, b) = a. Then a divided into itself and b.

    a|b --> b = ac for some int c

    let f - gcd(a, b) = gcd(a, ac)

    Im not sure I have it right to this point or what to do next>?

    Thank you
    Recall from the EA that (a,b)=a \Leftrightarrow \exists x,y\in\mathbb{Z}\text{ such that }ax+by=a
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    27
    I looked over my hw i just got back...

    prove that for all positive integers a and b, a|b if and only if , gcd(a, b) = a
    first I thought since gcd(a, b) = a. Then a divided into itself and b.
    a|b --> b = ac for some int c
    let d = gcd(a, b) = gcd(a, ac)

    up to this point she liked but then she didnt like this::

    d = gcd(a, ac) = gcd(1,c) = a(1) =a
    since gcd(1, m) =1 for any positive integer
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 07:53 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 13th 2010, 08:25 PM
  3. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 04:20 AM
  4. Replies: 6
    Last Post: March 31st 2009, 06:44 PM
  5. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 06:46 AM

Search Tags


/mathhelpforum @mathhelpforum