跳到主要内容

竞赛数论：原根、剩余与构造

高中数论竞赛的主线是“结构识别”：先看模数结构，再选 CRT、阶、二次剩余或构造法。

一、核心知识点讲解​

1. 中国剩余定理（CRT）​

若模数两两互质：

x≡ai(modmi) (i=1,…,k),(mi,mj)=1, x\equiv a_i\pmod{m_i}\ (i=1,\dots,k),\quad (m_i,m_j)=1,

则存在唯一解模 M=∏miM=\prod m_i。

常用构造：

x≡∑i=1kaiMiNi(modM), x\equiv\sum_{i=1}^k a_iM_iN_i\pmod M,

其中 Mi=MmiM_i=\frac{M}{m_i}，Ni≡Mi−1(modmi)N_i\equiv M_i^{-1}\pmod{m_i}。

2. 阶与原根​

  • 阶：ord⁡n(a)\operatorname{ord}_n(a) 是满足 ak≡1(modn)a^k\equiv1\pmod n 的最小正整数 kk。
  • 重要性质：ord⁡n(a)∣φ(n)\operatorname{ord}_n(a)\mid\varphi(n)。
  • 若 ord⁡n(g)=φ(n)\operatorname{ord}_n(g)=\varphi(n)，则 gg 是模 nn 的原根。
  • 有原根的模数：2,4,pk,2pk2,4,p^k,2p^k（pp 为奇素数）。

3. 二次剩余与勒让德符号​

  • 勒让德符号：
(ap)={1,a≢0 ( mod p) 且 x2≡a ( mod p) 可解;−1,a≢0 ( mod p) 且不可解;0,p∣a. \left(\frac ap\right)=\begin{cases} 1,&a\not\equiv0\ (\bmod p)\text{ 且 }x^2\equiv a\ (\bmod p)\text{ 可解};\\ -1,&a\not\equiv0\ (\bmod p)\text{ 且不可解};\\ 0,&p\mid a. \end{cases}
  • 欧拉判别：
ap−12≡(ap)(modp). a^{\frac{p-1}2}\equiv\left(\frac ap\right)\pmod p.
  • 二次互反律：
(pq)(qp)=(−1)p−12q−12. \left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\frac{q-1}2}.

4. 不定方程 (Indeterminate Equations)​

不定方程是竞赛中考查综合能力的重点，通常要求整数解。

  • 线性不定方程：ax+by=cax + by = c 有整数解的充要条件是 gcd⁡(a,b)∣c\gcd(a, b) \mid c。
  • 勾股方程 (Pythagorean Triples)：x2+y2=z2x^2 + y^2 = z^2 的全部正整数解可表示为： x=k(m2−n2),y=2kmn,z=k(m2+n2)x = k(m^2 - n^2), \quad y = 2kmn, \quad z = k(m^2 + n^2) 其中 m>n>0m > n > 0, gcd⁡(m,n)=1\gcd(m, n) = 1 且 m,nm, n 奇偶性不同。
  • 佩尔方程 (Pell's Equation)：x2−Dy2=1x^2 - Dy^2 = 1（DD 为非平方正整数）。
    • 基本解 (x1,y1)(x_1, y_1) 可通过连分数展开获得。
    • 全部解 (xn,yn)(x_n, y_n) 满足：xn+ynD=(x1+y1D)nx_n + y_n\sqrt{D} = (x_1 + y_1\sqrt{D})^n。
  • 无穷递降法 (Infinite Descent)：证明方程无正整数解的核心手段。若假设存在正整数解，能推导出更小的正整数解，则产生矛盾。

5. 同余构造常见套路​

  • 先降幂（费马/欧拉）；
  • 再拆模（CRT）；
  • 最后回代成最小正解。
竞赛提醒

数论题先问三个问题：模数是否可分解？指数是否可降？目标是否可转成“是否存在”的剩余判定。对于不定方程，优先考虑模运算约束（如 x2≡0,1(mod4)x^2 \equiv 0, 1 \pmod 4）来排除解。

二、经典例题实战​

例题 1：CRT 标准构造​

求解

x≡1(mod4),x≡2(mod5),x≡3(mod7). x\equiv1\pmod4,\quad x\equiv2\pmod5,\quad x\equiv3\pmod7.
点击查看解析与答案

先由前两式设 x=1+4tx=1+4t，代入第二式得 4t≡1(mod5)4t\equiv1\pmod5，故 t≡4(mod5)t\equiv4\pmod5，即

x≡17(mod20). x\equiv17\pmod{20}.

再与第三式联立：设 x=17+20sx=17+20s，代入 (mod7)\pmod 7：

17+20s≡3⇒3+6s≡3⇒s≡0(mod7). 17+20s\equiv3\Rightarrow3+6s\equiv3\Rightarrow s\equiv0\pmod7.

故

x≡17(mod140). x\equiv17\pmod{140}.

例题 2：阶与幂模运算​

求 2100(mod13)2^{100}\pmod{13}。

点击查看解析与答案

因 φ(13)=12\varphi(13)=12 且 212≡1(mod13)2^{12}\equiv1\pmod{13}，

2100=212⋅8+4≡(212)8⋅24≡24=16≡3(mod13). 2^{100}=2^{12\cdot8+4}\equiv(2^{12})^8\cdot2^4\equiv2^4=16\equiv3\pmod{13}.

例题 3：原根判定（小模）​

判断 2 是否为模 11 的原根。

点击查看解析与答案

φ(11)=10\varphi(11)=10，检查 210/d≢1(mod11)2^{10/d}\not\equiv1\pmod{11}（dd 为 10 的素因子 2,5）：

25=32≡−1≢1,22=4≢1(mod11). 2^5=32\equiv-1\not\equiv1,\quad 2^2=4\not\equiv1\pmod{11}.

因此 ord⁡11(2)=10\operatorname{ord}_{11}(2)=10，2 是模 11 的原根。

例题 4：二次剩余判定​

判断同余方程 x2≡3(mod13)x^2\equiv3\pmod{13} 是否有解。

点击查看解析与答案

用欧拉判别：

3(13−1)/2=36=729≡1(mod13), 3^{(13-1)/2}=3^6=729\equiv1\pmod{13},

故 (313)=1\left(\frac{3}{13}\right)=1，方程有解。

枚举可得一组解 x≡±4(mod13)x\equiv\pm4\pmod{13}（因 42=16≡34^2=16\equiv3）。

例题 5：Wilson 定理应用​

证明若 pp 为素数，则

(p−1)!≡−1(modp). (p-1)!\equiv-1\pmod p.
点击查看解析与答案

模 pp 的非零剩余类都可逆。除 1,−11,-1 外，其余元素与各自逆元两两配对，配对乘积全为 1，因此

(p−1)!≡1⋅(−1)≡−1(modp). (p-1)!\equiv1\cdot(-1)\equiv-1\pmod p.

例题 6：无穷递降法 (High Difficulty)​

求方程 x2+y2+z2=3xyzx^2 + y^2 + z^2 = 3xyz 的正整数解。并证明方程 x2+y2+z2=xyzx^2 + y^2 + z^2 = xyz 无正整数解。

点击查看解析与答案

部分证明：关于 x2+y2+z2=xyzx^2 + y^2 + z^2 = xyz 的无解性​

假设存在正整数解 (x,y,z)(x, y, z)。考虑模 3： 若 x,y,zx, y, z 均不被 3 整除，则 x2+y2+z2≡1+1+1≡0(mod3)x^2 + y^2 + z^2 \equiv 1 + 1 + 1 \equiv 0 \pmod 3。 而右边 xyzxyz 可能为 11 或 2(mod3)2 \pmod 3，矛盾。 若其中一个被 3 整除，设 3∣x3 \mid x，则 y2+z2≡0(mod3)⇒3∣yy^2 + z^2 \equiv 0 \pmod 3 \Rightarrow 3 \mid y 且 3∣z3 \mid z（平方数模 3 只有 0 和 1）。 令 x=3x1,y=3y1,z=3z1x = 3x_1, y = 3y_1, z = 3z_1，代入原方程： 9x12+9y12+9z12=27x1y1z1⇒x12+y12+z12=3x1y1z19x_1^2 + 9y_1^2 + 9z_1^2 = 27x_1y_1z_1 \Rightarrow x_1^2 + y_1^2 + z_1^2 = 3x_1y_1z_1。 这是一个著名的马尔可夫方程。而对于 x2+y2+z2=xyzx^2 + y^2 + z^2 = xyz，重复上述过程会导致 x,y,zx, y, z 可以被 3k3^k 任意次整除，故只有零解。

结论​

x2+y2+z2=xyzx^2 + y^2 + z^2 = xyz 无正整数解。

三、配套练习（章节内）​

练习 1（基础）​

求解同余组

x≡2(mod3),x≡3(mod5). x\equiv2\pmod3,\quad x\equiv3\pmod5.
点击查看过程与答案

设 x=2+3tx=2+3t，代入得 3t≡1(mod5)3t\equiv1\pmod5，故 t≡2(mod5)t\equiv2\pmod5。 最小正解 x=8x=8，通解 x≡8(mod15)x\equiv8\pmod{15}。

练习 2（提高）​

求 7222(mod20)7^{222}\pmod{20}。

点击查看过程与答案

72=49≡9, 74≡81≡1(mod20)7^2=49\equiv9,\ 7^4\equiv81\equiv1\pmod{20}，

7222=74⋅55+2≡72≡9(mod20). 7^{222}=7^{4\cdot55+2}\equiv7^2\equiv9\pmod{20}.

练习 3（提高）​

判断 3 是否为模 7 的原根。

点击查看过程与答案

φ(7)=6\varphi(7)=6，检查 32=9≡2≢13^2=9\equiv2\not\equiv1，33=27≡6≢1(mod7)3^3=27\equiv6\not\equiv1\pmod7。 故阶为 6，3 是模 7 的原根。

练习 4（挑战）​

判断 x2≡5(mod11)x^2\equiv5\pmod{11} 是否可解，并给出全部解。

点击查看过程与答案

计算平方剩余：0,1,4,9,5,30,1,4,9,5,3（模 11）。包含 5，故可解。 由 42≡5(mod11)4^2\equiv5\pmod{11}，全部解为

x≡±4(mod11). x\equiv\pm4\pmod{11}.

练习 5（高难度 - 佩尔方程）​

求方程 x2−2y2=1x^2 - 2y^2 = 1 的前三组正整数解。

点击查看过程与答案
  1. 观察或通过连分数求基本解：当 y=2,x=3y=2, x=3 时，32−2(22)=9−8=13^2 - 2(2^2) = 9 - 8 = 1。基本解为 (3,2)(3, 2)。
  2. 利用公式 xn+yn2=(3+22)nx_n + y_n\sqrt{2} = (3 + 2\sqrt{2})^n。
  3. n=2n=2：(3+22)2=9+8+122=17+122(3 + 2\sqrt{2})^2 = 9 + 8 + 12\sqrt{2} = 17 + 12\sqrt{2}。解为 (17,12)(17, 12)。
  4. n=3n=3：(17+122)(3+22)=51+48+(34+36)2=99+702(17 + 12\sqrt{2})(3 + 2\sqrt{2}) = 51 + 48 + (34+36)\sqrt{2} = 99 + 70\sqrt{2}。解为 (99,70)(99, 70)。

答案：(3,2),(17,12),(99,70)(3, 2), (17, 12), (99, 70)。