同余、整除性与算术函数
引入| English | 释义 | 拼音 |
|---|---|---|
| congruence/ˈkɒŋɡruːəns/ | 同余 | tóng yú |
| Chinese remainder theorem/tʃaɪˈniːz rɪˈmeɪndə ˈθɪərəm/ | 中国剩余定理 | zhōng guó shèng yú dìng lǐ |
| totient/ˈtəʊʃənt/ | 欧拉函数 | ōu lā hán shù |
循环对齐之时
- 一个齿轮每 $4$ 分钟重复一次,另一个每 $7$ 分钟重复一次。在第一周期位于位置 $2$,在第二周期位于位置 $3$,意味着寻找时间 $x$ 使得满足条件 $x\equiv2\pmod4$ 和 $x\equiv3\pmod7$。
- 同余(Congruences)描述重复的位置。中国剩余定理(Chinese remainder theorem)将它们结合起来;最大公约数检验、模逆元和素数指数告诉我们哪些代数步骤是有效的。
同余即整除
- 同余是一个陈述,指两个整数除以指定的正整数具有相同的余数。此处所有变量均为整数,且模数满足 $n\geq2$;$a\equiv b\pmod n$ 恰好意味着 $n$ 整除 $a-b$。
- 对于$ax\equiv b\pmod n$,令$d=\gcd(a,n)$。任一解对应某个整数$k$使$ax-b=kn$成立。因$d$同时整除$a$和$n$,必整除$b$;若$d\nmid b$,则无解。
为何最大公约数也计入解的数量
- 条件 $d\mid b$ 也是充分的。贝祖等式(Bézout)给出了整数 $u,v$ 使得成立 $ua+vn=d$;乘以 $b/d$ 表明 $x=u(b/d)$ 是原同余方程的解。
- 若$d<n$,则将系数、目标和模数同除以$d$。简化后的系数在模$n/d$下可逆,给出一个类$x\equiv x_0\pmod{n/d}$。其提升为$x_0+k(n/d)$(对应$k=0,\ldots,d-1$):恰好是模$n$下的$d$个不同剩余类。情形$d=n$将在下文单独处理。
How many solutions modulo 20 does $8x \equiv 12 \pmod{20}$ have?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
The gcd is 4 and divides 12, so there are four residues modulo 20. Reducing gives 2x ≡ 3 (mod 5), hence x ≡ 4 (mod 5). The four lifts are 4, 9, 14 and 19 modulo 20.
约简、求解与提升
- 对于 $6x\equiv9\pmod{15}$,最大公约数为 $3$ 且整除 $9$。将这三个数除以 $3$ 得到 $2x\equiv3\pmod5$。由于 $2^{-1}\equiv3\pmod5$,约简后的解为 $x\equiv4\pmod5$。
- 通过加$5$回代至原模数:剩余类为模$15$下的$4,9,14$。代入后得$24,54,84$,每个均模$15$同余于$9$;解的数量为$3$,而非$1$。
Which congruence is equivalent to $6x\equiv9\pmod{15}$ after dividing by the gcd?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The gcd is 3, so the coefficient 6, target 9 and modulus 15 all divide by 3. The reduced class modulo 5 lifts to three classes modulo 15.
消去法与零系数
- 仅除系数和目标会改变问题:将 $6x\equiv9\pmod{15}$ 替换为 $2x\equiv3\pmod{15}$ 只会得到 $x\equiv9\pmod{15}$,并丢失另外两个解。在除法步骤中模数必须缩小。
- 若$n\mid a$,则对任意$x$有$ax\equiv0\pmod n$。当$n\mid b$成立时有全部$n$个剩余类解,否则无解。因此$0x\equiv0\pmod6$有六个解,而$0x\equiv1\pmod6$无解;无需计算模$1$下的逆元。
共有多少个解?
使用 gcd(a, n) 计算同余方程 ax ≡ b (mod n) 的解的个数。
How many residue classes modulo $6$ satisfy $0x\equiv0\pmod6$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Every residue 0, 1, 2, 3, 4 and 5 works. The gcd is gcd(0, 6) = 6, which divides the target 0.
Solve $18x\equiv30\pmod{42}$ and list every residue solution modulo $42$. Explain why your list is complete.
最大公约数为$\gcd(18,42)=6$,它整除30。将系数、目标和模数除以6得到$3x\equiv5\pmod7$。由于3关于模7的逆元是5,由此得出$x\equiv25\equiv4\pmod7$。模42下的六个提升解为$4,11,18,25,32,39$。每个提升解均满足原同余式。由于简化周期为7而原模数为42,故恰好存在六个互异的提升解。
利用扩展欧几里得算法求逆元
- $a$ 模 $n$ 的逆元存在当且仅当 $\gcd(a,n)=1$。对于 $7$ 和 $26$,欧几里得算法得出 $26=3\cdot7+5$,接着是 $7=5+2$,然后是 $5=2\cdot2+1$;最后一个非零余数是 $1$。
- 由于 $2=7-5$,回代可得 $1=3\cdot5-2\cdot7$。接着利用 $5=26-3\cdot7$ 得到 $1=3\cdot26-11\cdot7$。因此 $7^{-1}\equiv-11\equiv15\pmod{26}$;请验证 $7\cdot15=105\equiv1\pmod{26}$。
Find the inverse of 5 modulo 13 (between 1 and 12).
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
We need 5x ≡ 1 (mod 13). 5 · 8 = 40 = 3 · 13 + 1, so the inverse is 8. (The Euclidean algorithm finds it systematically.)
组合互质周期
- 中国剩余定理指出,模数两两互质的同余方程组在模数的乘积下恰好有一个公共剩余类。对于两个模数,将 $x=r+mk$ 代入 $x\equiv s\pmod n$;系数 $m$ 在模 $n$ 下可逆。
- 在齿轮示例中,写出$x=2+4k$。第二个条件变为$4k\equiv1\pmod7$,于是$k\equiv2\pmod7$和$x\equiv10\pmod{28}$。最小正时间为$10$;整个解集为$10+28t$(其中$t$为整数)。
Find the least positive $x$ with $x \equiv 1 \pmod 3$ and $x \equiv 4 \pmod 5$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
List numbers ≡ 4 (mod 5): 4, 9, 14, … The first, 4, already leaves remainder 1 when divided by 3, so x = 4. By the CRT the solution is unique mod 15.
非互质模数:检验相容性
- 对于 $x\equiv r\pmod m$ 和 $x\equiv s\pmod n$,当且仅当 $\gcd(m,n)$ 整除 $s-r$ 时存在解。代入 $x=r+mk$ 得到 $mk\equiv s-r\pmod n$,因此适用线性最大公约数测试。一个相容的系统给出模 $\operatorname{lcm}(m,n)$ 的一个剩余类。
- 对于$x\equiv1\pmod4$和$x\equiv3\pmod6$,代入$x=1+4k$得$4k\equiv2\pmod6$。化简为$2k\equiv1\pmod3$,得出$k\equiv2\pmod3$和$x\equiv9\pmod{12}$。但模$4$余$0$与模$6$余$3$不相容:前者要求偶数,后者要求奇数。
Find the least positive integer $x$ with $x\equiv3\pmod8$ and $x\equiv7\pmod{12}$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
The gcd is 4, which divides the difference 7 − 3. Put x = 3 + 8k. Then 8k ≡ 4 (mod 12), so 2k ≡ 1 (mod 3) and k ≡ 2 (mod 3). Thus x ≡ 19 (mod 24), with least positive member 19.
周期与最小正解
- 同一系统的两个解之差是两模数的公倍数,即它们的lcm的倍数。反之,将一个解加上lcm后仍满足两个条件。这证明了所声称的周期及剩余类的唯一性。
- 最小非负代表元未必为正。对于$x\equiv0\pmod4$和$x\equiv0\pmod6$,该类模$12$为$0$;其最小正成员为$12$,而非$0$。选择最终代表元前请先阅读所要求的范围。
Solve $x\equiv2\pmod6$, $x\equiv8\pmod{10}$. Give the full residue class and least positive solution. Then explain what changes if the first residue is changed to $1$.
最大公约数为2,且整除$8-2=6$,因此第一个方程组相容。写出$x=2+6k$;进而$6k\equiv6\pmod{10}$,故$3k\equiv3\pmod5$且$k\equiv1\pmod5$。由此得$x\equiv8\pmod{30}$,其中$30=\operatorname{lcm}(6,10)$。其最小正解为8。若首个余数变为1,则所需差值为$8-1=7$,该值不能被最大公约数2整除。等价而言,这两个同余式分别要求奇偶性与偶性,故无解。
欧拉函数:统计可逆剩余类数量
- 欧拉函数是与模数互质的剩余类个数。对于 $n\geq2$,将此计数记作 $\varphi(n)$。若其不同的素因子为 $p$,则 $\varphi(n)=n\prod_{p\mid n}(1-1/p)$:每个素因子在乘积中仅出现一次,无论其在 $n$ 中的指数是多少。
- 由于 $36=2^2\cdot3^2$,我们得到 $\varphi(36)=36\cdot\dfrac12\cdot\dfrac23=12$。对于素数幂,结果为 $\varphi(p^k)=p^k-p^{k-1}$,因为恰好是 $p$ 的倍数不与 $p^k$ 互质。
$\varphi(36)$ equals
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
$36 \cdot \tfrac12 \cdot \tfrac23$.
欧拉定理与费马定理需要正确条件
- 若 $\gcd(a,n)=1$,欧拉定理给出 $a^{\varphi(n)}\equiv1\pmod n$。乘以 $a$ 会对可逆剩余类进行置换;比较它们的乘积并消去可逆部分的乘积即可证明该结论。
- 对于素数 $p$ 及 $p\nmid a$,这成为费马定理 $a^{p-1}\equiv1\pmod p$。形式 $a^p\equiv a\pmod p$ 对任意整数 $a$ 均成立,包括 $p$ 的倍数。例如,$\varphi(10)=4$ 和 $3^{100}=(3^4)^{25}\equiv1\pmod{10}$。
What is $7^{222} \bmod 10$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
φ(10) = 4, 222 ≡ 2 mod 4, 7² = 49.
For integers $a$ and $n\geq2$, $a^{\varphi(n)}\equiv1\pmod n$ holds whenever $\gcd(a,n)=1$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
True. Euler’s theorem requires coprimality. For example, 2 and 8 are not coprime, and $2^4\equiv0\pmod8$ rather than 1.
仅对单位可约减指数
- 对于非负指数 $e$ 及 $\gcd(a,n)=1$,将 $e$ 模 $\varphi(n)$ 约减后,$a^e$ 模 $n$ 的值保持不变。若无互质性,此法可能失效:将 $10$ 模 $\varphi(8)=4$ 约减会错误地将 $2^{10}$ 替换为 $2^2\equiv4\pmod8$。
- 反复平方法无需互质性假设。此处 $2^2\equiv4$,$2^4\equiv0$ 和 $2^8\equiv0\pmod8$。由于 $10=8+2$,实际剩余为 $2^{10}\equiv0\pmod8$。应约减中间乘积,而非对非单位调用欧拉定理。
Since $\varphi(8)=4$, reducing the exponent proves $2^{10}\equiv2^2\pmod8$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Euler exponent reduction requires an invertible base. The actual residues are 2¹⁰ ≡ 0 (mod 8) and 2² ≡ 4 (mod 8), so they differ.
Compute $5^{123}\bmod12$ and $6^{18}\bmod9$. Explain why the same exponent-reduction shortcut does not apply to both.
对于第一个幂次,$\gcd(5,12)=1$和$\varphi(12)=4$。由于$123\equiv3\pmod4$,欧拉定理给出$5^{123}\equiv5^3\equiv5\pmod{12}$。对于第二个幂次,$\gcd(6,9)=3$,因此欧拉约简缺乏依据。应改为$6^2=36\equiv0\pmod9$,故得$6^{18}=(6^2)^9\equiv0\pmod9$。将18模$\varphi(9)=6$约分会错误地将幂次替换为$6^0=1$。
整除问题转化为素数指数不等式
- 对于正整数$M$,令$v_p(M)$为其质因数分解中质数$p$的指数。当且仅当对每个质数$p$都有$v_p(D)\leq v_p(M)$时,正整数$D$才能整除$M$。
- 若$N^k$必须被$D$整除,其中$k$为正整数,则需满足$k\,v_p(N)\geq v_p(D)$。对于整除$D$的质数选取$v_p(N)=\lceil v_p(D)/k\rceil$,对其他质数取零。所有可接受的$N$均为该选择的倍数,因此即为最小正整数解。
平方包含 360 的最小整数
- 因子 $360=2^3\cdot3^2\cdot5$。为使 $N^2$ 能被 $360$ 整除,$N$ 中 $2,3,5$ 的指数必须至少为 $2,1,1$。因此最小选择是 $N=2^2\cdot3\cdot5=60$。
- 验证 $60^2=3600=10\cdot360$。$2$ 在 $N$ 中的指数由 $3/2$ 向上取整至 $2$;不可向下取整。多余的素数或更大的指数会增加 $N$,无法使最小值更优。
What is the least positive integer $N$ such that $108$ divides $N^2$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Since 108 = 2²·3³, N needs at least one factor of 2 and two factors of 3. The least N is 2·3² = 18, and 18² = 324 = 3·108.
补全乘积使其成为完全幂
- 要使 $24N$ 成为完全立方数,从 $24=2^3\cdot3$ 开始。乘积中每个素数的指数都必须是 $3$ 的倍数。$2$ 的指数已符合要求,但 $3$ 的指数还需增加两个副本,因此最小乘数为 $N=3^2=9$。
- 验证 $24\cdot9=216=6^3$。此处使用指数同余关系:$v_p(24)+v_p(N)\equiv0\pmod3$。之前的平方可整除问题使用的是不等式。请选择与题目表述相符的条件。
所提出的步骤是否有效?
检查指数约简、中国剩余定理周期及最小指数的假设条件。
What is the least positive integer $N$ such that $18N$ is a perfect cube?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Factor 18 = 2·3². To make all product exponents multiples of 3, add two factors of 2 and one factor of 3. Thus N = 2²·3 = 12 and 18·12 = 216 = 6³.
Find the least positive integer $N$ such that $540$ divides $N^2$ and $40N$ is a perfect cube. Prove minimality using prime exponents.
写出$540=2^2\cdot3^3\cdot5$和$40=2^3\cdot5$。设N中2、3和5的指数分别为a、b和c。N²的可除性要求$a\geq1$、$b\geq2$和$c\geq1$。立方条件要求$a+3$、b和$c+1$均为3的倍数。因此最小可能的指数为$a=3$、$b=3$和$c=2$,对应$N=2^3\cdot3^3\cdot5^2=5400$。无需额外质因数。所有符合条件的N至少具有这些指数,故不可能更小。验证$5400^2/540=54000$为整数且$40\cdot5400=216000=60^3$。
检查存在性、周期性和最小值
- 对于线性同余方程,测试最大公约数,约简所有三个数并提升每个剩余类。对于方程组,测试相容性并使用最小公倍数作为其周期;最小正解可能与最小非负代表元不同。
- 仅对可逆剩余类使用欧拉定理。对于最小整数整除问题,先进行因式分解,并将每个要求转化为关于每个素数指数的不等式或同余式。