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 - The Fusion of Science and Community**

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

# Common Divisor Proof

Loading...

Similar Threads - Common Divisor Proof | Date |
---|---|

Can anyone give a common-sense explanation of singular values? | Dec 10, 2012 |

Looking for a common solution of two systems | Nov 29, 2012 |

Theorem 1.2.1. Common Divisor | Jun 21, 2012 |

Greatest common divisor | Relatively prime | Jan 7, 2010 |

Greatest common divisor of polynomials | Jul 7, 2009 |

**Physics Forums - The Fusion of Science and Community**