Unable to understand this lemma The lemma is from the book Discrete Mathematics for computer scientists and mathematicians by Joe L Mott, Abraham Kendal, and Theodore P Baker

Suppose $x$ and $m$ are positive integers and $r$ is the smallest positive integer for which there exist integers $c$ and $d$ such that $r = cx + dm$, then $r = gcd(x, m)$

This lemma doesn't make sense to me. Clearly, if all $x, m, c, d$ are integers then $r$ has to be greater than them, then how can $r$ be their gcd? Even if $c$ and $d$ are negative, what even is the point of doing so? The whole thing seems really bizzare. The proof is even more bizarre though

Proof: Suppose $x = pr + q$, where $0 \le q < r$ then, $q = x - pr = x - p(cx + dm) = (1-pc)x + (-pd)m$


Since $r$ is the smallest positive integer of this form, and $0 \le q < r$, it must be that $q = 0$ which is to say r divides x

I don't understand how they managed to derive $q = 0$ from this. If anyone is able to explain it more clearly, I would really appreciate it.
 A: About the lemma: if $c$ and $d$ can be negative, then the lemma is correct.
About the proof: since $q=(1-pc)x+(-pd)m$, $q$ verifies the kind of equation that $r$ verifies: a linear combination of $x$ and $m$ with integer coefficients. But we have supposed that $r$ is the smallest positive integer that verifies this. As $0\le q \lt r$, this implies $q=0$.
A: In terms of understanding what the lemma is trying to achieve, think about what the values of $cx + dm$ are - they're linear combinations of $x$ and $m$. If $x$ and $m$ were, say, two denominations of poker chips, then $cx + dm$ represents the values we can generate from having $c$ of the first chip and $d$ of the second.
If $c$ and $d$ were strictly non-negative, then we would be looking at a coin problem (also known as a McNugget problem). However, the lemma does not put this restriction on $c$ and $d$, so in this case it's possible to owe a certain number of each denomination, in order to expand the range of possible values.
So, for example, if $x = 6$ and $m = 9$, then we can achieve the following values (among others):




$c$
$d$
$cx + dm$




$1$
$1$
$15$


$0$
$3$
$27$


$1$
$-2$
$3$


$-3$
$-2$
$-30$




The lemma then states that the smallest positive such value you can achieve is the GCD of $x$ and $m$. So with my example, you can find a linear combination to make $cx + dm = \gcd(6, 9) = 3$ (which I did in the table), but you cannot make $cx + dm = 1$ or $cx + dm = 2$.
The proof comes by applying the division algorithm - we know that for any positive integers $a$ and $b$ we can always write $a = lb + k$ for some non-negative integer $l$ and $k \in \{0, 1, \ldots, b - 1\}$ (i.e. "$a$ divided by $b$ gives $l$, with remainder $k$").
Applying that to the division of $x$ by $r$ gives $x = pr + q$. We rearrange that to get $q = x - pr$, then substitute $r = cx + dm$ to get $q = x - p(cx + dm) = (1 - pc)x + (-pd)m$. This is also a linear combination of $x$ and $m$, but we have assumed that $r$ is the smallest positive such value, and we have constructed $q$ to be in the set $\{0, 1, \ldots, r - 1\}$, and removing the positive values from that set leaves $q = 0$ as the only possibility.
But then that means $x = pr + q = pr$ thus demonstrating that $r$ divides $x$. Similarly you can prove that $r$ divides $m$, making $r$ a common divisor of $x$ and $m$, and the final step is proving that $r$ must be the greatest such common divisor, which you do by taking $c$ to be any common divisor and showing that $c$ must divide $r$.
What's the point? This is an extremely important result known as Bézout's identity, which underpins a huge amount of number theory. In particular, it forms part of the proof of the Chinese remainder theorem, which is fundamental to things like the RSA encryption algorithm.
