- a,b ∈ Z
- b>0
- q,r ∈ R
- a=qb+r with 0 <= r < b
Prove that GCD(a,b)=GCD(a,r)
My answer:
- Let GCD(a,b)=x and GCD(a,r)=y
- x,y ∈ Z+
- a/x,b/x ∈ Z
- a/x=q(b/x)+r/x ; (Dividing both sides by x) ; holds a=qb+r
- b/y ∈ Z
- a/y=q(b/y)+r/y ; (Dividing both sides by y)
- To hold this a/y ∈ Z
- So y must be also an divisor of a
Is my way to reach the answer correct or does this have another method?