Results 1 to 1 of 1

- January 29th 2008, 10:45 AM #1

- Joined
- Mar 2006
- Posts
- 705
- Thanks
- 2

## GCD problem

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.

Q.E.D.

Is that right?