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