Proving that d=gcd(a,b) iff 1=gcd(a1,b1)

[mathrocks]

I'm having trouble with gcd proofs in general, but here is a specific problem.

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 statement). 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.

 

[matt grime]

I think you're making it far too complicated.

Let's do this way: suppose that gcd(a1,b1)=e and e is different from 1. Then a1=ea2 and b1=eb2 for some integers a2 and b2, then a=a2ed, and b=b2ed.

So, if d is the gcd, then e cannot be different from 1 as claimed, or de divides both a and b.

For the second part, if ass ume gcd(a1,b1)=1 we can indeed conclude that d=am+bn, but this tells us that gcd(m,n) divides d, since the gcd divides the terms on the right. So d is less than gcd(a,b) since it is some divisor of a and b, and is also divisible by the gcd so it must equal the gcd.

 

[roam]

This was mathrocks' question: $$a,b \in Z$$ $$a,b \neq 0$$, and $$d=gcd(a,b)$$. If $$a=da_1$$ and $$b=db_1$$ for some $$a_1, b_1 \in Z$$ then you want to show that $$gcd(a_1,b_1) = 1$$.

I can't follow matt grime's proof but I know that there is a theorem which states:

Let $$d=gcd(a,b)$$. Then there exists integers x and y such that $$d=ax+by$$.

I want to know how we can prove the problem above using this theorem.

$$d=gcd(a,b)$$

$$d=ax + by$$ and since $$a=da_1$$ and $$b=db_1$$,

$$d=(da_1)x + (db_1)y = (dx)a_1 + (dy)b_1$$

I'm stuck at this point. Can anyone help please?