# Common Divisor Proof

1. Jan 31, 2010

### scottstapp

Hello I have the following proposition to prove.

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.

2. Jan 31, 2010

### mathman

If n (>1) is a common divisor of a and b, then n divides ax+by, but ax+by=1 and n cannot divide 1.

3. Jan 31, 2010

### scottstapp

Would I incorporate this by saying that there exists a common divisor, call it n where n>1, of a and b such that 1= knx+Lny where k and L are integers. so 1=n(kx+Ly). Obviously n cannot divide one, is this saying that therefore the gcd(a,b)=1? Therefore a and b are relatively prime?

Thank you.

4. Jan 31, 2010

### scottstapp

Does anyone know if this is the correct proof:

(1) Let a,b be integers.
(2) By definition of linear combination there exist integers x,y such that 1=ax+by.
(3) there exists a common divisor, call it n where n>1, of a and b such that 1= knx+Lny where k and L are integers. so 1=n(kx+Ly)
(4)From (3) gcd(a,b)=1
(4)Therefore a and b are relatively prime

Thanks

5. Jan 31, 2010

### scottstapp

anyone?

6. Jan 31, 2010

### JSuarez

No, the correct proof would be:

Hipothesis: let a and b be integers, not both zero, such that there are x,y, also integers, such that ax + by = 1.

(1) Any common divisor of a and b must also be a divisor of any linear integer combination af a and b.

(2) Therefore, if d|a and d|b, then d|ax+by, which implies that d|1.

(3) If d is a positive common divisor, then d = 1; in particular gcd(a,b) = 1.

Hopefully, this is will be the last time anyone spells out a proof for you in a non-homework section!

7. Jan 31, 2010

### scottstapp

Thanks for the help, I am new to the site. Maybe next time you could simply point me in the right direction of where to post instead of getting angry.