# Math Help - Problems understanding The Euclidean Algorithm

1. ## 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

2. 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>?

Thank you
Recall from the EA that $(a,b)=a \Leftrightarrow \exists x,y\in\mathbb{Z}\text{ such that }ax+by=a$

3. 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