Let a and b be nonzero integers. Prove that there is a
natural number m such that
(i) ajm and bjm, and
(ii) if c is an integer such that ajc and bjc, then mjc.
Proof. Let S = fn 2 N : ajn and bjng. Since ab 2 S, S 6= ;. Thus,
by the Least-Natural-Number-Principle, there is a smallest element of
S. Let m be this smallest element. Now suppose ajc and bjc. Then
c 2 S and so c m. So by the division algorithm for integers, there
exist integers p; r such that 0 r < m such that c = mq+r. Since ajm
and bjm, then ajr and bjr. If c 6= 0, then r is an element of S smaller
than m. Thus, r = 0 and mjc.