Question

Prove that if there exists x and y for which ax +by=1, then gcd(a, b)=1

Answer 1

where are you stuck?

Answer 2

....pretty much at the beginning lol.

Answer 3

i know that it's true because I have seen several problems like that before, but i am TERRIBLE with proofs

Answer 4

start with...

assume c| a and c|b

you need to show c=1

Answer 5

c|a="c divides a"

Answer 6

or a is divisible by c

Answer 7

ok but how does that help when you already know c=1

Answer 8

if c divides a and c divides b then c divides any linear combination of a and b

ie c|(ax+by)

Answer 9

but ax+by=1 so c|1.

which positive integers can divide 1?

Answer 10

does that mean then that the gcd=c=1?