# Problems understanding The Euclidean Algorithm

• Nov 13th 2010, 03:31 PM
Thetheorycase
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>?(Doh)

Thank you
• Nov 13th 2010, 03:33 PM
Drexel28
Quote:

Originally Posted by Thetheorycase
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>?(Doh)

Thank you

Recall from the EA that $(a,b)=a \Leftrightarrow \exists x,y\in\mathbb{Z}\text{ such that }ax+by=a$
• Nov 13th 2010, 10:12 PM
Thetheorycase
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