We are tasked with proving that if $a$ and $b$ are positive integers, and there exist integers $x$ and $y$ such that

$ax + by = 1,$

then the greatest common divisor $(a, b) = 1$.

Proof:

The equation $ax + by = 1$ is a linear Diophantine equation. The key point here is that for such an equation to have integer solutions $x$ and $y$, the greatest common divisor of $a$ and $b$ must divide the constant term (which is 1 in this case). Let's analyze this in detail.

1. Assume $d = \gcd(a, b)$: By definition, $d$ is the greatest integer that divides both $a$ and $b$. Therefore, we can write

$a = d \cdot a_1 \quad \text{and} \quad b = d \cdot b_1$

for some integers $a_1$ and $b_1$, where $\gcd(a_1, b_1) = 1$.

2. Substitute $a = d \cdot a_1$ and $b = d \cdot b_1$ into the original equation: Substituting these expressions into $ax + by = 1$ gives

$d \cdot a_1 x + d \cdot b_1 y = 1.$

This simplifies to

$d \cdot (a_1 x + b_1 y) = 1.$

3. Conclude that $d = 1$: The left-hand side is a multiple of $d$, so for the equation to hold true, $d$ must divide 1. Since $d$ is a positive integer, the only possibility is $d = 1$.

4. Conclusion: Therefore, $\gcd(a, b) = d = 1$, which means that $a$ and $b$ are relatively prime.

Thus, we have shown that if there exist integers $x$ and $y$ such that $ax + by = 1$, then $(a, b) = 1$, i.e., $a$ and $b$ are relatively prime.

---

Would you like further clarification or additional steps on any part of the proof? Here are some related questions to explore:

1. How does the Euclidean algorithm help in finding $\gcd(a, b)$?
2. What are some practical applications of linear Diophantine equations?
3. How do we find integer solutions for $ax + by = 1$?
4. How can we extend this idea to solve other linear Diophantine equations with more variables?
5. What is the relationship between the Extended Euclidean Algorithm and solving $ax + by = 1$?

Tip: The Extended Euclidean Algorithm is an efficient way to find integer solutions $x$ and $y$ for $ax + by = 1$, as well as computing the greatest common divisor.