I'm having trouble with gcd proofs in general, but here is a specific problem.(adsbygoogle = window.adsbygoogle || []).push({});

Let a and b be integers, not both zero, and let d be a positive integer that divides both a and b. Then there exists a1 and b1 such that a=a1*d and b=b1*d.

Prove that d=gcd(a,b) if and only if 1=gcd(a1,b1)

What I have so far:

Pf: Let a and b be integers and since d|a and d|b then d|gcd(a,b) by definition. So let d*k=gcd(a,b) for some integer k. Then dk=ma+nb where m,n are integers. (I'm not sure if I can do that last statment). Now dk=m(a1*d)+n(b1*d) where a=a1*d and b=b1*d. So dk=d(m*a1+n*b1) and therefore d|(m*a1+n*b1) ....

I'm not sure if I'm heading in the right direction, but after that point I don't know how to get to 1=gcd(a1,b1).

For the second part of the proof I have"

Now assume a and b are integers such that 1=gcd(a1,b1). So there exists m and n that are integers such that 1=ma1+nb1. (Now I multiple by a integer d). Then d=md*a1 + nd*b1, and d=ma+nb where a1*d=a and b1*d=b.

Again, I'm stuck after this point.

**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!

# GCD proof

Loading...

Similar Threads for proof |
---|

I Proof that BB(k) grows faster than any computable function |

I An easy proof of Gödel's first incompleteness theorem? |

I Cantor's decimal proof that (0,1) is uncountable |

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