1

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.

Aditya
  • 6,191
  • 2
    Not more clearly, just more words: They showed that $q$ is the sum of an integer multiple of $x$ (namely, $1-pc$ times $x$) and an integer multiple of $m$ (namely, $-pd$ times $m$). If $q$ were a positive integer, then it would be an element of the set of positive integers writable as sum of an integer multiple of $x$ and an integer multiple of $m$. By definition, $r$ is the smallest element of that set. Hence we'd need to have $q\ge r$, but certainly $q<r$. - We conclude that $q$ is not a positive integer. Given its possible range, $0\le q<r$, the only remaining possibility is that $q=0$. – Hagen von Eitzen Oct 16 '22 at 20:34
  • It shows that $q$ is also an integer of the form $cx+dm$, but it is less than $r$. The only choice left is for $q=0$. – Randall Oct 16 '22 at 20:35
  • Since $,c,d,$ can be negative integers, $r$ does not need to be greater than $x$ and $m$. For example, if $x=8$ and $m=9$, then there exist $c=8$ and $d=-7$ such that $r=1=cx+dm,.$ – Angelo Oct 16 '22 at 20:36
  • I guess that Euclid's algorithm is the point. A good point at that. – Matija Oct 16 '22 at 20:46

2 Answers2

2

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$.

Jean-Armand Moroni
  • 5,632
1

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.

ConMan
  • 24,300