Final answer:
To prove that if two positive integers, m and n, are relatively prime, there exist integers a and b such that am + bn, we can use a proof by contradiction and the well-ordering principle. By assuming that there are no such integers, we arrive at a contradiction and conclude that the assumption was incorrect.
Step-by-step explanation:
To prove that if two positive integers, m and n, are relatively prime, there exist integers a and b such that am + bn, we can use a proof by contradiction. Assume that there are no such integers a and b. Let S be the set of all positive integers of the form am + bn, where a and b are integers. By the well-ordering principle, S has a smallest element, let it be d.
Since d is the smallest element of S, d cannot be expressed as am + bn for any integers a and b. Therefore, d is not equal to 0 and by the division algorithm, we can write m = dq + r, where q and r are integers and 0 <= r < d. Similarly, we can write n = ds + t, where s and t are integers and 0 <= t < d.
Substituting the expressions for m and n into the equation am + bn, we have dq + r = as(d) + bt. Rearranging the terms, we get r = dq - as(d) - bt. Notice that r is a positive integer (since 0 <= r < d) and r can be expressed as am + bn for integers a = -s and b = -t. But this contradicts the assumption that d is the smallest element of S.
Therefore, our assumption was incorrect and there must exist integers a and b such that am + bn.