1

I'm trying to do extra book work to prepare for our final coming up but a lot of the book questions involve topics I'm unsure about.

Prove: $n\in Z$, n=a multiple of gcd(a,b) $\iff$ n is a linear combination of a and b

This question makes no sense to me. How do I prove that and where can I start. What does gcd have to do with linear combinations. We write using formal proof techniques including assumption where necessary so please keep that in mind.

these are the guidelines i use to write most proofs https://i.stack.imgur.com/7q03x.jpg

Mikky Davey
  • 225

1 Answers1

1

Let $gcd(a, b) = d$. We are given that $n = xd$ for some $x \in \mathbb{Z}$.

Now expand $d$ using Bezout's identity. We know $d = sa + tb$ for some $s, t \in \mathbb{Z}$. Hence:

$$n = xd = x(sa + tb) = xsa + xtb$$

And we recognize this as a linear combination of $a$ and $b$.

At least that's one direction of your proof! I'll leave you to the converse :)

Kaj Hansen
  • 33,011