Let e, f, g, and h be intergers with e >0. If gh=f + e and e =gcd(g,h), then gcd(f,g)=e.

proof. By the GCD Theorem, we know that e=gx+hy, eu=g, ev=h, for some integers x,y,u,v.

Now, gh=f+e, gh-e=f, (eu)h-e=f, e(uh-1)=f, implies that e divides f.

Also, gh=f+e, e=gh-f, e=g(h)+f(-1).

Furthermore, e divides g given by the problem. Thus, all three requirements, namely ( i. e divides g, ii. e divides f, and iii. e=gx+fy) are satisfied, therefore proven that gcd(f,g)=e.


Is that right?