A.6 · Congruences, divisibility and arithmetic functions
GRE Subject Test · GRE Mathematics Topic 12 3:36 English narration · English + 中文 subtitles burned in
Chapters
Transcript
This unit solves linear congruences using gcd conditions, combines coprime congruences with the Chinese remainder theorem, applies Euler's theorem only to invertible residues, and uses prime exponents to find least admissible integers.
本单元用最大公约数条件解线性同余方程，用中国剩余定理合并互素模的同余式，只对可逆剩余应用欧拉定理，并用素数指数求最小的满足条件的整数。
a x congruent to b modulo n has a solution exactly when d, the gcd of a and n, divides b.
ax ≡ b (mod n) 有解，当且仅当 d = gcd(a, n) 整除 b。
Then divide a, b and n by d: one residue solution modulo n over d, and d solutions modulo n.
然后把 a、b、n 都除以 d：模 n/d 有一个解，模 n 有 d 个解。
Dividing the coefficient but leaving the modulus loses solutions.
只除系数而保留原模数会丢解。
Prime exponents give a separate tool: each exponent of n must be at least a over k, rounded up.
素数指数是另一种工具：n 的每个素数指数至少为 a/k 向上取整。
The extended Euclidean algorithm writes the gcd as u a plus v n; when it is 1, u is an inverse.
扩展欧几里得算法把最大公约数写成 ua + vn；当它为 1 时，u 就是逆元。
For 7 and 26, 15 is the inverse of 7.
对 7 和 26，7 的逆是 15。
For coprime moduli the Chinese remainder theorem gives one solution modulo the product.
对互素的模，中国剩余定理给出模乘积的唯一解。
If the moduli are not coprime, the residues must agree modulo the gcd, and uniqueness is modulo the lcm.
若模不互素，各剩余必须模 gcd 一致，唯一性是模最小公倍数。
Euler's totient phi of n counts residues coprime to n: n times the product of 1 minus 1 over p.
欧拉函数 φ(n) 计数与 n 互素的剩余：n 乘以 (1 − 1/p) 之积。
Euler's theorem gives a to the phi of n congruent to 1 only when a is coprime to n; the prime case is Fermat's little theorem.
欧拉定理只在 a 与 n 互素时给出 a^{φ(n)} ≡ 1；素数情形是费马小定理。
A nonunit can become zero under repeated powers instead.
非单位的幂反复相乘反而可能变成零。
The gcd of 6 and 15 is 3, which divides 9.
6 和 15 的最大公约数是 3，它整除 9。
Divide all three quantities: 2x congruent to 3 modulo 5, so x is congruent to 4 modulo 5.
三者都除以 3：2x ≡ 3 (mod 5)，所以 x ≡ 4 (mod 5)。
The original solutions modulo 15 are 4, 9 and 14.
原方程模 15 的解是 4、9、14。
Separately, x equals 2 plus 4k with 4k congruent to 1 modulo 7 gives k equals 2, so x is 10 modulo 28.
另外，x = 2 + 4k，4k ≡ 1 (mod 7) 给出 k = 2，所以 x ≡ 10 (mod 28)。
The expression a to the phi of n congruent to 1 is false for arbitrary a.
a^{φ(n)} ≡ 1 对任意 a 并不成立。
For example, 2 is not invertible modulo 8, and 2 to the 4 is zero modulo 8.
例如 2 模 8 不可逆，而 2⁴ 模 8 等于零。
The gcd is four and divides 12; dividing gives 2x congruent to 3 modulo 5, so x is 4 modulo 5, and the four answers modulo 20 are 4, 9, 14 and 19.
最大公约数是 4，整除 12；除后得 2x ≡ 3 (mod 5)，所以 x ≡ 4 (mod 5)，模 20 的四个解是 4、9、14、19。
Since 7 times 3 is 21, the inverse of 7 is 3.
因为 7 × 3 = 21，7 的逆是 3。
Although phi of 20 is 8, 2 is not a unit, and 2 to the 8 is 16, not 1.
尽管 φ(20) = 8，但 2 不是单位，2⁸ ≡ 16，不是 1。
The residues agree modulo the gcd, three.
两个剩余模最大公约数 3 一致。
Put x equals 2 plus 6k: then 6k is 3 modulo 9, so k is 2 modulo 3, and x is 14 modulo 18, the lcm, not 54.
令 x = 2 + 6k：则 6k ≡ 3 (mod 9)，所以 k ≡ 2 (mod 3)，x ≡ 14 (mod 18)，模的是最小公倍数，不是 54。
For the divisibility problem, the prime exponents must satisfy 3a at least 5 and 3b at least 7, so the least n is 4 times 27, which is 108.
对整除问题，素数指数需满足 3a ≥ 5、3b ≥ 7，所以最小的 n 是 4 × 27 = 108。
Check yourself.
自我检测。
6x congruent to 9 modulo 15 has solutions 4, 9 and 14.
6x ≡ 9 (mod 15) 的解是 4、9、14。
The inverse of 7 modulo 26 is 15.
7 模 26 的逆是 15。
2 to the 4 is zero modulo 8.
2⁴ 模 8 为零。
Moduli 6 and 9 give uniqueness modulo 18.
模 6 和 9 的唯一性是模 18。
And the least n is 36.
最小的 n 是 36。