for some integer k.

Let . Since and , it follows from that and is thus a common divisor of and .

Let beanycommon divisor of and . With a similar argument, we have that . By definition, since is thegreatestcommon divisor of and , we have that .

This means that any common divisor of and is less than . Can you conclude?