Question

Prove the folllowing statement either directly or by contrapositive:

Let a and b be integers. If there exist integers m and n such that an - bm = 1, then a and b are coprime.

Answer 1

The statement can be proven directly by showing that the existence of integers m and n such that an - bm = 1 means a and b are coprime, which is a consequence of Bézout's lemma, as it demonstrates that the GCD of a and b is 1.

Step-by-step explanation:

To prove that if there exist integers m and n such that an - bm = 1, then a and b are coprime, we can proceed with a direct proof.

Two numbers are coprime if their greatest common divisor (GCD) is 1. The fact that there exists an equation an - bm = 1 indicates that there is a linear combination of a and b that equals 1. This is a direct consequence of Bézout's lemma, which states that if a and b are integers and d is their greatest common divisor, then there exist integers m and n such that am + bn = d. In our case, since d = 1, m and n are the coefficients of the linear combination that produces the GCD, which is 1.

Therefore, since a and b are part of such a linear combination resulting in 1, it implies that their GCD is indeed 1, proving that a and b are coprime.