Thread: 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

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

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