互质整数线性组合的贝祖定理

When we are given two intgers, we ask, "What numbers can we make from (linear) combinations of them?"

Bezout's Identity: Given distinct integers $a,b$ with $\gcd(a,b)=d$, there exists integers $x,y$ such that $ax+by=d$.

Proof: Fix $a$ and $b$ (that is, we don't change their values). Consider the set $\mathcal{S}=\left\{s>0:s=ax+by\text{ for some }x,y\in\mathbb{Z} \right\}$. We know that $|a|+|b|$ is in $\mathcal{S}$, and this number is positive. Thus, $\mathcal{S}$ is nonempty. Also, all elements are greater than $0$, so it has a smallest element. Let the smallest element be $s_0$, and let $x_0$ and $y_0$ be such that $s_0=ax_0+by_0$.

By the division algorithm there exists $q,r\in\mathbb{Z}$ such that $a=s_0q+r$ and $0\leq r<s_0$. Since $r<s_0$, $r\notin\mathcal{S}$. But

$$r=a-s_0q=a-(ax_0+by_0)q=a(1-x_0q)+b(-y_0q),$$

so in order for it to not be in $\mathcal{S}$, $r\not\in\mathbb{N}$, but $r\geq 0$, so $r=0$. Thus, $a=s_0q$, and $s_0\mid a$. Similarly, $s_0\mid b$.

Let $\gcd(a,b)=d$. Since $s_0 \mid a$ and $s_0 \mid b$ we have $s_0 \mid d$. Additionally, we have that $d\mid a$ and $d\mid b$, so $d\mid ax_0+by_0=s_0$. Since $s_0$ and $d$ divide each other, they must be equal. Thus, $d=ax_0+by_0$, and we have found $x,y$ such that $ax+by=d$. $\Box$

Additionally, once we found $x$ and $y$, we can form every multiple of $d$ like so:

Let $ax+by=d$. Then, $dk=a(xk)+b(yk)$.

This actually holds for any $k \in \mathbb{Z}$, including the negative values. It just so happens $dk$ might be negative, but there's nothing wrong with that.

An Elegant Proof of Bezout's Identity

Bezout's identity says that, for any two integers $a,b$ there are two integers $x,y$ such that $ax+by=d$. The idea used here is a very technique in olympiad number theory.

Since $\gcd(a,b)=d$, we can assume $a=dm$ and $b=dn$ so that $\gcd(m,n)=1$. Then we just need to prove that $mx+ny=1$ is possible for integers $x,y$.

Let's think on how to do that. The equation can also be stated this way: If we divide $mx$ by $n$, the remainder should be $1$. Now, the problem is reduced even further. And we should check an example to understand what we are asked to do.

Take $m=11$ and $n=6$. We need to check the remainders of $mx=11x$ when divided by $n=6$.

$$\begin{align} 11\cdot1 & = 11\quad\text{ remainder }5\\ 11\cdot2 & = 22\quad\text{ remainder }4\\ 11\cdot3 & = 33\quad\text{ remainder }3\\ 11\cdot4 & = 44\quad\text{ remainder }2\\ 11\cdot5 & = 55\quad\text{ remainder }1 \end{align}$$

Bingo! We need the remainder $1$ and now we have it. Not just that, playing with some more examples, you will see that actually all the remainders from $1$ to $n-1$ appear. Which means, all the remainders of $mx$ divided by $n$ are distinct! This is even a stronger claim.

If $\gcd(m,n)=1$, then the remainder of multiples of $m$ when divided by $n$ are distinct. That is, $mi$ and $mj$ don't have the same remainder when divided by $n$ if $i\neq j$. You should understand how it implies that Bezout's identity holds. Because then we will have the remainder $1$ as well. If the remainder of $mx$ divided by $n$ is $1$ then $mx-1$ is divisible by $n$. If we take $mx-1=nz$ then setting $y=-z$, we get $mx+ny=1$, which was what we wanted. Only the claim is left to prove.

Now let's get to proving this claim. For the sake of contradiction, assume that $mi$ and $mj$ leave the same remainder when divided by $n$. Then the difference $mi-mj$ must be divisible by $n$. This means $n$ divides $m(i-j)$. Since $m$ and $n$ share no factor at all, we can safely say $n$ has to divide $i-j$. We can also say that $1\leq j<i<n$, because even if $j$ or $i$ is greater than $n$, $nq+j$ or $nq+i$ has the same remainder as $j$ or $i$. This assumption gives us $i-j<n$, which is impossible since $n$ divides $i-j$.

Hope now you understand!