Hello I have the following proposition to prove.(adsbygoogle = window.adsbygoogle || []).push({});

Prop. Let a,b be integers. If 1 is a linear combination of a and b, then a and b are relatively prime.

I am given the following definition.

Let a and b be integers, not both zero. If gcd(a,b)=1, then a and b are said to be relatively prime. Notice that the only common divisors of relatively prime integers are 1 and -1.

My work so far:

(1) Let a,b be integers.

(2) By definition of linear combination there exist integers x,y such that 1=ax+by.

(3) Because 1 is a common divisor of a,b then 1 must be the gcd(a,b)

(4)Therefore a and b are relatively prime

I need help on (3), I know that I am missing some steps and logic but I am not sure what to do. Am I approaching this correctly? Thank you.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Common Divisor Proof

**Physics Forums | Science Articles, Homework Help, Discussion**