本讲要解决的问题

「偶数加奇数得奇数」是小学知识，但它其实是模 $2$ 的算术：只看除以 $2$ 的余数，就能预测和的奇偶性。本讲把这一观察推广到任意模数，回答三个问题：

1. 哪些运算规则可以照搬到模运算里？
2. 什么时候可以「除以」一个数，也就是求乘法逆元？
3. 多个模数下的余数条件能否同时满足？能的话，解是否唯一、如何求？

第三个问题就是中国剩余定理，它会在编码与密码学中反复出现。

时间轴

同余与带余除法

定义

设 $n$ 为正整数。称 $a$ 与 $b$ 模 $n$ 同余，记作

$$a\equiv b\pmod n,$$

当且仅当 $a-b$ 是 $n$ 的整数倍，即 $n\mid(a-b)$。

带余除法

对任意整数 $a$ 与正整数 $n$，存在唯一的整数 $q$ 与 $r$，使得

$$a=qn+r,\qquad 0\le r<n .$$

$q$ 是商，$r$ 是余数。唯一性来自区间 $[0,n-1)$ 的长度恰为 $n$：若有两组解，相减会得到一个绝对值小于 $n$ 的 $n$ 的倍数，只能是 $0$。

同余等价于余数相等

命题。

$$a\equiv b\pmod n \iff a\bmod n=b\bmod n .$$

证明（$\Leftarrow$）。 设 $a=qn+r$、$b=q'n+r$，两者余数同为 $r$。则

$$a-b=(q-q')n,$$

是 $n$ 的倍数，故同余。

证明（$\Rightarrow$）。 设 $a=qn+r$、$b=q'n+r'$，且 $a\equiv b$，即 $a-b$ 是 $n$ 的倍数。另一方面

$$a-b=(q-q')n+(r-r').$$

因此 $r-r'$ 也是 $n$ 的倍数。但 $0\le r,r'<n$，所以

$$-n<r-r'<n .$$

在这个开区间内唯一的 $n$ 的倍数是 $0$，故 $r=r'$。$\square$

这个命题把「同余」这个抽象关系翻译成了「做除法看余数」这个具体操作，后面所有算法都建立在这一翻译上。

时钟图像

把 $0,1,\dots,n-1$ 均匀排在钟面上。整数 $k$ 对应从 $0$ 出发走 $k$ 步后落到的位置。

例如模 $7$：$5$ 落在位置 $5$；$12$ 绕一整圈后再走 $5$ 步，也落在位置 $5$，所以 $12\equiv5\pmod7$。模运算不区分绕了几圈，只关心停在哪里。

模运算

加法与乘法

若 $a\equiv a'$、$b\equiv b'\pmod n$，则

$$a+b\equiv a'+b',\qquad ab\equiv a'b'\pmod n .$$

直观做法：先按普通整数算，最后减去若干个 $n$，把结果拉回 $[0,n-1]$。

例（模 $7$）：$10\equiv3$、$12\equiv5$，于是

$$10\cdot12=120\equiv3\cdot5=15\equiv1\pmod7 .$$

核对：$120=17\cdot7+1$ ✓。

为什么可以「先算再取余」？ 因为每个整数都可以写成 $qn+r$，而 $qn$ 这一部分在模 $n$ 下等于 $0$。剩下起作用的只有余数 $r$。

三条代数律

对任意 $a,b,c$ 与模 $n$：

• 结合律：$(a+b)+c\equiv a+(b+c)$，$(ab)c\equiv a(bc)$。
• 交换律：$a+b\equiv b+a$，$ab\equiv ba$。
• 分配律：$a(b+c)\equiv ab+ac$。

这三条与普通整数运算完全一致：因为两边相减都是 $n$ 的倍数。模运算因此构成一个环——这正是下一讲群论的起点。

不是所有规则都能照搬

可以相加、相乘，但不能随意约去。例如模 $6$ 时

$$2\cdot3=6\equiv0,\qquad 2\cdot0=0,$$

所以 $2\cdot3\equiv2\cdot0$，却推不出 $3\equiv0$。约去因子需要该因子可逆，这正是下一节的主题。

乘法逆元

定义与例子

称 $a$ 在模 $n$ 下有乘法逆元，若存在 $b$ 使

$$ab\equiv1\pmod n .$$

模 $7$ 时，$2\cdot4=8\equiv1$，所以 $4$ 的逆元是 $2$，$2$ 的逆元是 $4$。同理 $3\cdot5=15\equiv1$，二者互为逆元。

有了逆元，「除以 $4$」就可以实现为「乘以 $2$」：若已知 $4x\equiv c$，两边乘 $2$ 得 $x\equiv2c$。这正是密码学里「加密后还能解密」的原型——乘以某个数把信息打乱，再乘以它的逆元还原。

关键问题

模 $7$ 时，每个非零元素都有逆元吗？ 逐个查表可以确认：$1,2,3,4,5,6$ 都有。但当模数很大时，不可能写出整张乘法表。于是需要理论回答两个问题：

1. 什么时候存在逆元？
2. 不用查表，怎样算出逆元？

答案要用到最大公因数与欧几里得算法。

最大公因数

$\gcd(a,b)$ 是同时整除 $a$ 与 $b$ 的最大正整数。若没有更大的公因数，它就是 $1$。

暴力算法是从 $1$ 试到 $\min(a,b)$，对大整数完全不可行。需要一个快速算法。

欧几里得算法

引理 1：减去一份不改变最大公因数

设 $b\ge a$，则

$$\gcd(a,b)=\gcd(a,\,b-a).$$

证明。 比较两边的公因数集合。

若 $k\mid a$ 且 $k\mid b$，则 $k\mid(b-a)$，所以 $k$ 也是 $a$ 与 $b-a$ 的公因数。

反之，若 $k\mid a$ 且 $k\mid(b-a)$，则 $b=(b-a)+a$ 也被 $k$ 整除，所以 $k$ 也是 $a$ 与 $b$ 的公因数。

两边的公因数集合完全相同，最大者自然相同。$\square$

逻辑上要注意：不是「$k$ 是某个下界」，而是两边的公因数逐一对应。集合相等比大小相等更强，也更干净。

引理 2：一次减到底

设 $b=qa+r$（带余除法）。反复使用引理 1：

$$\gcd(a,b)=\gcd(a,b-a)=\gcd(a,b-2a)=\cdots=\gcd(a,b-qa)=\gcd(a,r).$$

所以

$$\gcd(a,b)=\gcd(a,\ b\bmod a).$$

一步除法代替了 $q$ 次减法，这是算法快的原因：要么 $a$、$b$ 接近，一次减法就让较大的数减半；要么差距很大，一次取余就让较大的数降到 $a$ 以下。两种情况都让数值迅速变小。

数值例子

计算 $\gcd(46,360)$：

$$\begin{aligned} 360&=7\cdot46+38,\\ 46&=1\cdot38+8,\\ 38&=4\cdot8+6,\\ 8&=1\cdot6+2,\\ 6&=3\cdot2+0. \end{aligned}$$

最后一个非零余数是 $2$，故 $\gcd(46,360)=2$。$\gcd(2,0)=2$，因为 $0$ 被任何正整数整除。

扩展欧几里得与 Bézout 等式

普通算法只保留余数；扩展算法还记录每个余数是如何由原始两数拼出来的。

从上面的例子倒推：

$$\begin{aligned} 38&=360-7\cdot46,\\ 8&=46-38=8\cdot46-360,\\ 6&=38-4\cdot8=5\cdot360-39\cdot46,\\ 2&=8-6=47\cdot46-6\cdot360. \end{aligned}$$

于是找到整数 $s=47$、$t=-6$，使

$$46\cdot47+360\cdot(-6)=2162-2160=2 .$$

一般结论（Bézout）。 对任意整数 $a,b$，存在整数 $s,t$ 使

$$sa+tb=\gcd(a,b).$$

这个等式是一张证书

假设有人只告诉你答案是 $2$。你怎么确认它是最大公因数，而不只是某个公因数？

• 公因数性：$2\mid46$ 且 $2\mid360$，可以直接验算。
• 最大性：设 $k$ 同时整除 $46$ 与 $360$，则由 $2=47\cdot46-6\cdot360$，两边除以 $k$，左边是整数，右边是两个整数之和，也是整数，所以 $k\mid2$，即 $k\le2$。

一个等式同时证明了「是公因数」和「没有更大的公因数」。这就是 Bézout 等式的价值：它把「最大」这个看似需要比较的量，变成了一个可验证的整除关系。

逆元：存在性与计算

为什么模素数时一定有逆元

设 $p$ 为素数，$a\not\equiv0\pmod p$。因为 $p$ 只有 $1$ 与 $p$ 两个正因数，而 $a$ 不是 $p$ 的倍数，所以

$$\gcd(a,p)=1 .$$

由 Bézout，存在 $s,t$ 使

$$as+pt=1 .$$

两边模 $p$，$pt$ 消失：

$$as\equiv1\pmod p .$$

所以 $s$ 就是 $a$ 的逆元。这不仅证明了存在性，还给出了求法：对 $a$ 与 $p$ 跑扩展欧几里得算法，读出 $s$。

非素数模数

条件其实是 $\gcd(a,n)=1$，与 $n$ 是否素数无关。例如模 $6$ 时，$\gcd(5,6)=1$，故 $5$ 有逆元，且 $5\cdot5=25\equiv1$，逆元就是 $5$ 自己。而 $\gcd(2,6)=2\ne1$，$2$ 没有逆元。

例子

模 $7$ 求 $4$ 的逆元：$\gcd(4,7)=1$，扩展算法给出 $4\cdot2+7\cdot(-1)=1$，故逆元是 $2$。

模 $7$ 求 $5$ 的逆元：$\gcd(5,7)=1$，$5\cdot3+7\cdot(-2)=1$，故逆元是 $3$。

中国剩余定理

从谜题开始

一箱金币：按 $5$ 个一组分，剩 $4$ 个；按 $7$ 个一组分，剩 $1$ 个。最少有多少枚？

翻译成同余方程组：

$$n\equiv4\pmod5,\qquad n\equiv1\pmod7 .$$

猜一个解：$29=5\cdot5+4=4\cdot7+1$ ✓。但猜出来的答案需要理论保证：解是否唯一？模数不互素时会怎样？

陈述

设 $\gcd(a,b)=1$。则对任意余数 $r,s$，同余方程组

$$n\equiv r\pmod a,\qquad n\equiv s\pmod b$$

在 $0\le n<ab$ 中有唯一解。

换句话说，映射

$$n\longmapsto\big(n\bmod a,\ n\bmod b\big)$$

是从 $\{0,1,\dots,ab-1\}$ 到「$a$ 种余数 $\times$ $b$ 种余数」的双射。

证明

两侧都是有限集，各含 $ab$ 个元素。只要证明映射单射，由计数即得双射，也就同时证明了存在性与唯一性。

反设 $x\ne y$ 都落在 $[0,ab)$ 内，且两边的余数对完全相同：

$$x\equiv y\pmod a,\qquad x\equiv y\pmod b .$$

于是 $a\mid(x-y)$ 且 $b\mid(x-y)$。由 $\gcd(a,b)=1$，两个互素的数同时整除一个数，它们的乘积也整除它：

$$ab\mid(x-y).$$

但 $x,y\in[0,ab)$ 且 $x\ne y$，所以 $0<|x-y|<ab$，不可能被 $ab$ 整除——矛盾。$\square$

「互素」这一步不能省。 若 $a=6,b=9$，$6\mid N$ 且 $9\mid N$ 只能推出 $18\mid N$，推不出 $54\mid N$：$N=18$ 就是反例，因为两个模数共享因子 $3$。

构造解法

唯一性只是保证；实际求 $n$ 用下面的步骤。

设 $t=s$ 是模 $b$ 的余数，把 $n$ 写成

$$n=kb+t,\qquad 0\le k<a .$$

代入第一个同余式：

$$kb+t\equiv r\pmod a \Longrightarrow kb\equiv r-t\pmod a .$$

因为 $\gcd(b,a)=1$，$b$ 在模 $a$ 下可逆。两边乘 $b^{-1}$：

$$k\equiv b^{-1}(r-t)\pmod a .$$

再由 $0\le k<a$，$k$ 就等于这个余数本身，代回即得 $n$。

例子

$n\equiv4\pmod5$、$n\equiv1\pmod7$。取 $a=5$、$b=7$、$r=4$、$s=t=1$。

先求 $7$ 在模 $5$ 下的逆元：$7\equiv2$，$2\cdot3=6\equiv1$，故 $7^{-1}\equiv3$。

$$k\equiv3\cdot(4-1)=9\equiv4\pmod5 .$$ $$n=4\cdot7+1=29 .$$

与猜出的答案一致。

应用：喷泉码

把一个大文件看成一个巨大的整数 $N$。服务器不发送文件本身，而是持续广播一组消息

$$(a_i,\ N\bmod a_i),$$

其中 $a_i$ 是一批素数。

接收方无论收到哪一组消息，只要

$$\prod a_i>N,$$

就可以由中国剩余定理唯一地还原 $N$（这是两个模数情形的推广）。

好处在于：所有接收者可以收听同一路广播，谁先攒够「乘积超过 $N$」的那一部分，谁就先还原文件，不要求大家收到相同的片段。这正是喷泉码（fountain codes）的核心思想——像喷泉一样持续喷出数据，每个杯子接满即可。真实系统还要处理传输错误，但基本框架已经在这里。

零知识证明：卡片演示

课上用五张牌（三红两黑）做了一个小实验。

• 中间放一张红牌。
• 两位参与者各自决定「是否想看某部电影」：想看，就把自己的红牌放在靠近中间红牌的位置、黑牌放外侧；不想看，则黑牌靠内、红牌靠外。
• 把牌叠起来，各自随机切一次（等价于循环移位）。

结论：两人都想看 $\iff$ 循环排列中出现三张连续的红牌。若只有一人想看，则不会出现三连红。

因此旁观者只能知道「是否两人都同意」，而无法知道具体是谁想看、谁不想看：切牌把所有可区分的信息抹掉了。这就是零知识证明的雏形——证明「我知道某个事实」，却不泄露事实本身。

本节结论

• $a\equiv b\pmod n\iff n\mid(a-b)\iff$ 两者除以 $n$ 的余数相等。
• 模运算保持加法、乘法、结合律、交换律、分配律；但不能随意约去因子。
• $\gcd(a,b)=\gcd(a,b-a)=\gcd(a,b\bmod a)$，由此得到欧几里得算法。
• 扩展欧几里得算法给出 Bézout 等式 $sa+tb=\gcd(a,b)$，它同时是最大性的证书。
• $a$ 在模 $n$ 下可逆 $\iff\gcd(a,n)=1$；逆元由扩展算法读出。
• 中国剩余定理：$\gcd(a,b)=1$ 时，$n\bmod a$ 与 $n\bmod b$ 唯一确定 $n\in[0,ab)$。
• 构造解法：$n=kb+t$，$k\equiv b^{-1}(r-t)\pmod a$。
• 应用：喷泉码用 CRT 从任意足够多的片段还原文件。

理解检验

1. 证明：$a\equiv b\pmod n$ 当且仅当它们除以 $n$ 的余数相等。

参考答案：设 $a=qn+r$、$b=q'n+r'$，其中 $0\le r,r'<n$。若 $r=r'$，则 $a-b=(q-q')n$ 是 $n$ 的倍数，故同余。反之若 $n\mid(a-b)$，则 $a-b=(q-q')n+(r-r')$ 说明 $n\mid(r-r')$；而 $-n<r-r'<n$，该区间内唯一的 $n$ 的倍数是 $0$，故 $r=r'$。

2. 证明 $\gcd(a,b)=\gcd(a,b-a)$（设 $b\ge a$），并说明为什么这样证比「比较大小」更干净。

参考答案：设 $k$ 是 $a,b$ 的公因数，即 $k\mid a$、$k\mid b$，则 $k\mid(b-a)$，故 $k$ 也是 $a,b-a$ 的公因数。反之若 $k\mid a$、$k\mid(b-a)$，则 $k\mid\big((b-a)+a\big)=b$，故 $k$ 也是 $a,b$ 的公因数。两边的公因数集合完全相同，因此最大公因数相同。直接比较大小只能得到一边是另一边的下界，还必须再证反方向；而证明集合相等一次就得到双向结论。

3. 用欧几里得算法计算 $\gcd(46,360)$，再用扩展算法求出 $s,t$，并解释 Bézout 等式为什么是「最大性证书」。

参考答案：$360=7\cdot46+38$；$46=1\cdot38+8$；$38=4\cdot8+6$；$8=1\cdot6+2$；$6=3\cdot2+0$。最后一个非零余数是 $2$，故 $\gcd=2$。倒推：$38=360-7\cdot46$；$8=46-38=8\cdot46-360$；$6=38-4\cdot8=5\cdot360-39\cdot46$；$2=8-6=47\cdot46-6\cdot360$。所以 $s=47,t=-6$。若 $k$ 同时整除 $46$ 和 $360$，则由 $2=47\cdot46-6\cdot360$ 得 $k\mid2$，故 $k\le2$：这证明 $2$ 已是最大公因数，无需与其它数逐一比较。

4. 为什么 $\gcd(a,n)=1$ 时 $a$ 在模 $n$ 下可逆？如何算出逆元？举 $4$ 与 $5$ 在模 $7$ 下的例子。

参考答案：由 Bézout，$\gcd(a,n)=1$ 给出整数 $s,t$ 使 $as+nt=1$。两边模 $n$ 得 $as\equiv1$，故 $s$ 是逆元。算法上对 $a,n$ 跑扩展欧几里得即可读出 $s$。例：$4\cdot2+7\cdot(-1)=1$，故 $4^{-1}\equiv2$；$5\cdot3+7\cdot(-2)=1$，故 $5^{-1}\equiv3$。

5. 证明中国剩余定理（$\gcd(a,b)=1$ 时解在 $[0,ab)$ 内唯一）。

参考答案：考虑映射 $n\mapsto(n\bmod a,n\bmod b)$。若 $x,y\in[0,ab)$ 有相同的余数对，则 $a\mid(x-y)$ 且 $b\mid(x-y)$。因 $\gcd(a,b)=1$，推出 $ab\mid(x-y)$。但 $x\ne y$ 时 $0<|x-y|<ab$，不可能被 $ab$ 整除，矛盾。故映射单射。两侧元素个数同为 $ab$，单射即双射，唯一性与存在性同时成立。

6. 用构造法解 $n\equiv4\pmod5$、$n\equiv1\pmod7$。

参考答案：取 $t=1$，令 $n=7k+1$。代入第一式：$7k+1\equiv4\pmod5$，即 $2k\equiv3\pmod5$。$2$ 的逆元是 $3$（$2\cdot3=6\equiv1$），故 $k\equiv9\equiv4\pmod5$。由 $0\le k<5$ 得 $k=4$，于是 $n=4\cdot7+1=29$。

7. 五张牌的演示为什么能实现「零知识」？切牌起了什么作用？

参考答案：每人的摆法只编码一个比特（想看 / 不想看），但两种摆法在叠牌并循环移位后无法区分。最终公开的只有「是否存在三张连续的红牌」，而这只在两人都想看时出现。切牌的作用是施加随机循环移位，把所有与「谁喜欢、谁不喜欢」相关的具体位置信息全部抹掉，只留下一个对双方对称的判定结果，因此旁观者无法反推出任何一方的私人选择。

与前后课的关系

上一讲是 Chernoff 界；本讲转入数论，建立同余、欧几里得算法与中国剩余定理。下一讲把这些结构抽象成群，讨论群的定义、子群与元素的阶。

这些工具在后续课程中直接用于密码学：RSA 建立在模幂与逆元之上，Diffie–Hellman 建立在有限域的乘法群上，而编码理论中的 Reed–Solomon 码则建立在中国剩余定理的推广（多项式插值）之上。

What this lecture is for

"Even plus odd is odd" is elementary, yet it is already arithmetic modulo $2$: knowing only the remainders after division by $2$ predicts the parity of the sum. This lecture pushes the observation to arbitrary moduli and answers three questions:

1. Which algebraic rules carry over to modular arithmetic?
2. When can one "divide" by a number, i.e. when does a multiplicative inverse exist?
3. Can several congruence conditions with different moduli hold at once, and if so is the solution unique and how is it found?

The third question is the Chinese remainder theorem, which reappears throughout coding and cryptography.

Timeline

Congruences and division with remainder

Definition

Let $n$ be a positive integer. We say $a$ and $b$ are congruent modulo $n$, written

$$a\equiv b\pmod n,$$

exactly when $a-b$ is an integer multiple of $n$, that is $n\mid(a-b)$.

The division algorithm

For any integers $a$ and $n>0$ there are unique integers $q$ and $r$ with

$$a=qn+r,\qquad 0\le r<n .$$

Here $q$ is the quotient and $r$ the remainder. Uniqueness follows because the interval $[0,n-1]$ has length $n$: two solutions would differ by a multiple of $n$ of absolute value less than $n$, hence by $0$.

Congruence equals equality of remainders

Proposition.

$$a\equiv b\pmod n \iff a\bmod n=b\bmod n .$$

Proof ($\Leftarrow$). Write $a=qn+r$ and $b=q'n+r$ with the same remainder $r$. Then

$$a-b=(q-q')n,$$

a multiple of $n$, so the two are congruent.

Proof ($\Rightarrow$). Write $a=qn+r$, $b=q'n+r'$ and assume $a-b$ is a multiple of $n$. On the other hand

$$a-b=(q-q')n+(r-r').$$

Therefore $r-r'$ is also a multiple of $n$. But $0\le r,r'<n$, so

$$-n<r-r'<n .$$

The only multiple of $n$ in this open interval is $0$, hence $r=r'$. $\square$

This proposition translates an abstract relation into a concrete operation — divide and look at the remainder — and every algorithm below relies on the translation.

The clock picture

Place $0,1,\dots,n-1$ evenly around a clock face. An integer $k$ corresponds to the position reached by walking $k$ steps from $0$.

Modulo $7$, for example, $5$ lands on position $5$; $12$ goes once around and then five more steps, landing on $5$ as well, so $12\equiv5\pmod7$. Modular arithmetic does not distinguish how many laps were made, only where you stop.

Arithmetic modulo $n$

Addition and multiplication

If $a\equiv a'$ and $b\equiv b'\pmod n$, then

$$a+b\equiv a'+b',\qquad ab\equiv a'b'\pmod n .$$

The practical procedure: compute with ordinary integers, then subtract enough multiples of $n$ to land in $[0,n-1]$.

Example modulo $7$: $10\equiv3$ and $12\equiv5$, so

$$10\cdot12=120\equiv3\cdot5=15\equiv1\pmod7 .$$

Check: $120=17\cdot7+1$.

Why may one compute first and reduce afterwards? Every integer has the form $qn+r$, and $qn$ is $0$ modulo $n$; only the remainder does any work.

Three algebraic laws

For all $a,b,c$ and modulus $n$:

• Associativity: $(a+b)+c\equiv a+(b+c)$ and $(ab)c\equiv a(bc)$.
• Commutativity: $a+b\equiv b+a$ and $ab\equiv ba$.
• Distributivity: $a(b+c)\equiv ab+ac$.

These match ordinary integer arithmetic because the two sides differ by a multiple of $n$. Modular arithmetic therefore forms a ring — the starting point of the next lecture on groups.

Not every rule survives

Addition and multiplication are safe, but cancellation is not. Modulo $6$,

$$2\cdot3=6\equiv0,\qquad 2\cdot0=0,$$

so $2\cdot3\equiv2\cdot0$ yet $3\not\equiv0$. Cancelling a factor requires that factor to be invertible, which is the subject of the next section.

Multiplicative inverses

Definition and examples

An element $a$ has a multiplicative inverse modulo $n$ if some $b$ satisfies

$$ab\equiv1\pmod n .$$

Modulo $7$, $2\cdot4=8\equiv1$, so $4$ is the inverse of $2$ and vice versa. Likewise $3\cdot5=15\equiv1$.

With an inverse, "dividing by $4$" becomes "multiplying by $2$": from $4x\equiv c$ we get $x\equiv2c$. This is the prototype of encryption and decryption in cryptography — multiply to scramble a message, multiply by the inverse to unscramble it.

The key question

Modulo $7$, does every nonzero element have an inverse? Checking the table confirms that $1,2,3,4,5,6$ all do. But for large moduli no one can write down the whole table, so theory must answer two questions:

1. When does an inverse exist?
2. How is it computed without a table?

The answers involve gcds and Euclid's algorithm.

Greatest common divisors

$\gcd(a,b)$ is the largest positive integer dividing both $a$ and $b$; it is $1$ when no larger common divisor exists.

The brute-force method tries every integer from $1$ to $\min(a,b)$, which is hopeless for large numbers. A fast algorithm is needed.

Euclid's algorithm

Lemma 1: subtracting one copy preserves the gcd

For $b\ge a$,

$$\gcd(a,b)=\gcd(a,\,b-a).$$

Proof. Compare the two sets of common divisors.

If $k\mid a$ and $k\mid b$, then $k\mid(b-a)$, so $k$ is a common divisor of $a$ and $b-a$.

Conversely, if $k\mid a$ and $k\mid(b-a)$, then $b=(b-a)+a$ is also divisible by $k$, so $k$ is a common divisor of $a$ and $b$.

The two sets of common divisors coincide, so their largest elements coincide. $\square$

Logically, this is not a lower-bound argument but a one-to-one match of common divisors; equality of sets is stronger and cleaner than comparing sizes.

Lemma 2: subtract all at once

Write $b=qa+r$ by the division algorithm. Applying Lemma 1 repeatedly,

$$\gcd(a,b)=\gcd(a,b-a)=\gcd(a,b-2a)=\cdots=\gcd(a,b-qa)=\gcd(a,r).$$

Hence

$$\gcd(a,b)=\gcd(a,\ b\bmod a).$$

One division replaces $q$ subtractions, which is why the algorithm is fast: if $a$ and $b$ are close, one subtraction halves the larger; if they are far apart, one remainder operation brings the larger below $a$. Either way the numbers shrink rapidly.

A numerical example

Compute $\gcd(46,360)$:

$$\begin{aligned} 360&=7\cdot46+38,\\ 46&=1\cdot38+8,\\ 38&=4\cdot8+6,\\ 8&=1\cdot6+2,\\ 6&=3\cdot2+0. \end{aligned}$$

The last nonzero remainder is $2$, so $\gcd(46,360)=2$. Indeed $\gcd(2,0)=2$, since every positive integer divides $0$.

The extended algorithm and Bézout's identity

The plain algorithm keeps only remainders; the extended one also records how each remainder is built from the original pair.

Working backwards:

$$\begin{aligned} 38&=360-7\cdot46,\\ 8&=46-38=8\cdot46-360,\\ 6&=38-4\cdot8=5\cdot360-39\cdot46,\\ 2&=8-6=47\cdot46-6\cdot360. \end{aligned}$$

Thus $s=47$ and $t=-6$ satisfy

$$46\cdot47+360\cdot(-6)=2162-2160=2 .$$

Theorem (Bézout). For any integers $a,b$ there exist integers $s,t$ with

$$sa+tb=\gcd(a,b).$$

The identity is a certificate

Suppose someone reports the answer $2$. How can you be sure it is the greatest common divisor rather than merely some common divisor?

• It divides both: $2\mid46$ and $2\mid360$ are checked directly.
• Nothing larger divides both: if $k$ divides $46$ and $360$, then from $2=47\cdot46-6\cdot360$ dividing by $k$ gives an integer on the left and a sum of integers on the right, so $k\mid2$, hence $k\le2$.

One identity establishes both "is a common divisor" and "no larger one exists". That is the value of Bézout: it turns a comparison of sizes into a divisibility check.

Inverses: existence and computation

Why a prime modulus guarantees inverses

Let $p$ be prime and $a\not\equiv0\pmod p$. The only positive divisors of $p$ are $1$ and $p$, and $a$ is not a multiple of $p$, so

$$\gcd(a,p)=1 .$$

By Bézout there are $s,t$ with

$$as+pt=1 .$$

Reducing modulo $p$ kills $pt$:

$$as\equiv1\pmod p .$$

So $s$ is the inverse of $a$. This proves existence and also gives an algorithm: run the extended Euclidean algorithm on $a$ and $p$ and read off $s$.

Non-prime moduli

The real condition is $\gcd(a,n)=1$, independent of whether $n$ is prime. Modulo $6$, $\gcd(5,6)=1$, so $5$ has an inverse, and indeed $5\cdot5=25\equiv1$: it is its own inverse. But $\gcd(2,6)=2\ne1$, so $2$ has no inverse.

Examples

Modulo $7$, the inverse of $4$: $\gcd(4,7)=1$ and $4\cdot2+7\cdot(-1)=1$, so the inverse is $2$.

Modulo $7$, the inverse of $5$: $5\cdot3+7\cdot(-2)=1$, so the inverse is $3$.

The Chinese remainder theorem

Starting from a puzzle

A chest of coins: grouped in fives, four are left over; grouped in sevens, one is left over. What is the smallest possible number?

In congruences:

$$n\equiv4\pmod5,\qquad n\equiv1\pmod7 .$$

Guess $29=5\cdot5+4=4\cdot7+1$. A guess, however, needs theory: is the solution unique, and what happens when the moduli share a factor?

Statement

Let $\gcd(a,b)=1$. Then for any residues $r,s$ the system

$$n\equiv r\pmod a,\qquad n\equiv s\pmod b$$

has a unique solution with $0\le n<ab$.

Equivalently, the map

$$n\longmapsto\big(n\bmod a,\ n\bmod b\big)$$

is a bijection from $\{0,1,\dots,ab-1\}$ onto the $a\times b$ possible residue pairs.

Proof

Both sides are finite sets with $ab$ elements. It suffices to prove the map is injective; counting then upgrades it to a bijection, settling existence and uniqueness at once.

Suppose $x\ne y$ both lie in $[0,ab)$ and have identical residue pairs:

$$x\equiv y\pmod a,\qquad x\equiv y\pmod b .$$

Then $a\mid(x-y)$ and $b\mid(x-y)$. Since $\gcd(a,b)=1$, two coprime numbers dividing the same integer force their product to divide it:

$$ab\mid(x-y).$$

But $0<|x-y|<ab$ when $x\ne y$, so $ab$ cannot divide $x-y$ — a contradiction. $\square$

Coprimality cannot be dropped. With $a=6$ and $b=9$, the conditions $6\mid N$ and $9\mid N$ imply only $18\mid N$, not $54\mid N$; $N=18$ is a counterexample, because the two moduli share the factor $3$.

A constructive solution

Uniqueness is only a guarantee; to compute $n$, proceed as follows.

Let $t=s$ be the residue modulo $b$ and write

$$n=kb+t,\qquad 0\le k<a .$$

Substitute into the first congruence:

$$kb+t\equiv r\pmod a \Longrightarrow kb\equiv r-t\pmod a .$$

Since $\gcd(b,a)=1$, $b$ is invertible modulo $a$. Multiplying by $b^{-1}$:

$$k\equiv b^{-1}(r-t)\pmod a .$$

Because $0\le k<a$, $k$ equals that residue, and substituting back gives $n$.

Example

Solve $n\equiv4\pmod5$, $n\equiv1\pmod7$. Take $a=5$, $b=7$, $r=4$, $s=t=1$.

The inverse of $7$ modulo $5$: $7\equiv2$ and $2\cdot3=6\equiv1$, so $7^{-1}\equiv3$.

$$k\equiv3\cdot(4-1)=9\equiv4\pmod5 .$$ $$n=4\cdot7+1=29 .$$

Matching the guess.

Application: fountain codes

Regard a large file as a huge integer $N$. The server does not transmit the file itself; it continuously broadcasts pairs

$$(a_i,\ N\bmod a_i),$$

where the $a_i$ are distinct primes.

A receiver can reconstruct $N$ from any set of messages whose moduli satisfy

$$\prod a_i>N,$$

by the Chinese remainder theorem (the extension from two moduli to many).

The advantage: every receiver listens to the same broadcast, and each one finishes as soon as it has collected enough — no requirement that all receivers obtain the same pieces. This is the core idea of fountain codes: data sprays out continuously and each cup fills when it has enough. Real systems must also handle transmission errors, but the framework is here.

Zero-knowledge proofs: the card demonstration

Five cards (three red, two black) support a small experiment.

• A red card is placed face up in the middle.
• Each participant decides privately whether they want to watch a certain embarrassing movie. If yes, they place their red card adjacent to the centre card and their black card outside; if no, the order is reversed.
• The cards are stacked and each participant performs a random cut, i.e. a cyclic shift.

The outcome: both want to watch if and only if three red cards appear consecutively in the cyclic order. If only one wants to, there is no run of three reds.

An observer therefore learns only whether both agree, not who wanted what: the cuts erase every distinguishable detail. This is the germ of a zero-knowledge proof — proving that a fact is known without revealing the fact itself.

What this lecture establishes

• $a\equiv b\pmod n\iff n\mid(a-b)\iff$ the remainders on division by $n$ agree.
• Modular arithmetic preserves addition, multiplication, associativity, commutativity and distributivity; cancellation is not always valid.
• $\gcd(a,b)=\gcd(a,b-a)=\gcd(a,b\bmod a)$, which yields Euclid's algorithm.
• The extended algorithm yields Bézout's identity $sa+tb=\gcd(a,b)$, which certifies maximality.
• $a$ is invertible modulo $n$ iff $\gcd(a,n)=1$; the inverse is read off from the extended algorithm.
• Chinese remainder theorem: when $\gcd(a,b)=1$, the residues modulo $a$ and $b$ determine $n\in[0,ab)$ uniquely.
• Construction: $n=kb+t$ with $k\equiv b^{-1}(r-t)\pmod a$.
• Application: fountain codes reconstruct a file from any sufficiently many fragments via CRT.

Comprehension check

1. Prove that $a\equiv b\pmod n$ iff the remainders on division by $n$ are equal.

Reference answer: Write $a=qn+r$ and $b=q'n+r'$ with $0\le r,r'<n$. If $r=r'$, then $a-b=(q-q')n$ is a multiple of $n$, so the numbers are congruent. Conversely, if $n\mid(a-b)$, then $a-b=(q-q')n+(r-r')$ shows $n\mid(r-r')$; since $-n<r-r'<n$, the only multiple of $n$ in that range is $0$, so $r=r'$.

2. Prove $\gcd(a,b)=\gcd(a,b-a)$ for $b\ge a$, and explain why this is cleaner than comparing sizes.

Reference answer: If $k$ divides both $a$ and $b$, then $k$ divides $b-a$, so $k$ is a common divisor of $a$ and $b-a$. Conversely, if $k$ divides $a$ and $b-a$, then $k$ divides $(b-a)+a=b$, so $k$ is a common divisor of $a$ and $b$. The two common-divisor sets coincide, hence so do their maxima. Comparing sizes directly would give only a one-sided bound and require a separate argument for the reverse inequality; proving set equality settles both directions at once.

3. Compute $\gcd(46,360)$ with Euclid's algorithm, find $s,t$ with $46s+360t=2$, and explain why the identity certifies maximality.

Reference answer: $360=7\cdot46+38$; $46=1\cdot38+8$; $38=4\cdot8+6$; $8=1\cdot6+2$; $6=3\cdot2+0$. The last nonzero remainder is $2$, so the gcd is $2$. Back-substituting: $38=360-7\cdot46$; $8=46-38=8\cdot46-360$; $6=38-4\cdot8=5\cdot360-39\cdot46$; $2=8-6=47\cdot46-6\cdot360$. Thus $s=47$, $t=-6$. If $k$ divides both $46$ and $360$, then from $2=47\cdot46-6\cdot360$ it follows that $k\mid2$, hence $k\le2$: no larger common divisor exists, without comparing against other candidates.

4. Why does $\gcd(a,n)=1$ make $a$ invertible modulo $n$? How is the inverse computed? Give examples for $4$ and $5$ modulo $7$.

Reference answer: Bézout gives integers $s,t$ with $as+nt=1$. Reducing modulo $n$ kills $nt$, leaving $as\equiv1$, so $s$ is the inverse. Computationally, run the extended Euclidean algorithm on $a$ and $n$ and read off $s$. Examples: $4\cdot2+7\cdot(-1)=1$, so $4^{-1}\equiv2$; $5\cdot3+7\cdot(-2)=1$, so $5^{-1}\equiv3$.

5. Prove the Chinese remainder theorem (uniqueness in $[0,ab)$ when $\gcd(a,b)=1$).

Reference answer: Consider $n\mapsto(n\bmod a,n\bmod b)$. If $x,y\in[0,ab)$ have identical residue pairs, then $a\mid(x-y)$ and $b\mid(x-y)$. Coprimality forces $ab\mid(x-y)$. But $0<|x-y|<ab$ when $x\ne y$, so $ab$ cannot divide the difference — a contradiction. Hence the map is injective. Both sides have $ab$ elements, so injectivity implies bijectivity, giving existence and uniqueness together.

6. Solve $n\equiv4\pmod5$, $n\equiv1\pmod7$ by the constructive method.

Reference answer: Take $t=1$ and write $n=7k+1$. Substituting into the first congruence, $7k+1\equiv4\pmod5$, i.e. $2k\equiv3\pmod5$. The inverse of $2$ is $3$ since $2\cdot3=6\equiv1$, so $k\equiv9\equiv4\pmod5$. With $0\le k<5$, $k=4$, hence $n=4\cdot7+1=29$.

7. Why does the five-card demonstration achieve zero knowledge? What role does the cut play?

Reference answer: Each participant's arrangement encodes one bit (wants to watch or not), but after stacking and a random cyclic shift the two arrangements are indistinguishable. The only public information is whether three consecutive red cards appear, which happens exactly when both want to watch. The cut applies a random cyclic shift that erases all positional information about who chose what, leaving only a symmetric yes/no answer, so an observer cannot recover either private choice.

Relation to neighbouring lectures

The previous lecture proved Chernoff bounds; this one turns to number theory, establishing congruences, Euclid's algorithm and the Chinese remainder theorem. The next lecture abstracts these structures into groups, covering the definition, subgroups and the order of an element.

The tools are used directly later in cryptography: RSA rests on modular exponentiation and inverses, Diffie–Hellman on the multiplicative group of a finite field, and Reed–Solomon codes on the polynomial form of the Chinese remainder theorem (interpolation).