Question

Suppose that a, b \in \mathbb{Z}a,b∈Z, not both 00, and let d=\gcd(a, b)d=gcd(a,b). Bezout's theorem states that dd can be written as a linear combination of aa and bb, that is, there exist integers m, n \in \mathbb{Z}m,n∈Z such that d = am + bnd=am+bn. Prove that, on the other hand, any linear combination of aa and bb is divisible by dd. That is, suppose that t = ax + byt=ax+by for some integers x, y \in \mathbb{Z}x,y∈Z. Prove that d \, | \, td∣t.

Answer 1

Explanation:

Recall that we say that d | a if there exists an integer k for which a = dk. So, let d = gcd(a,b) and let x, y be integers. Let t = ax+by.

We know that
`d | a, d | b` so there exists integers k,m such that a = kd and b = md. Then,

`t = ax+by = (kd)x+(md)y = d(kx+my)`. Recall that since k, x, m, y are integers, then (kx+my) is also an integer. This proves that d | t.