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

Answer:

Step-by-step 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.