第一章 整数的可除性

定义

b∣ab\left|a\right. : b整除a，a可以被b整除，a是b的倍数，b是a的因子。
素数：除了平凡因子外无其他因子的数
(a,b)\left(a,b\right) :a,b的最大公因数，如果最大公因数为1则称两数互素或互质
[a,b]\left[a,b\right] :a,b的最小公倍数

定理

  • 如果 p>1p>1 是合数n的因数最小的，则p一定是素数，且 p  ≤  np\;\leq\;\sqrt n ，进而，如果所有素数 p  ≤  np\;\leq\;\sqrt n 都不能整除n则n为素数
    找出小于n的所有素数：删去所有素数 p  ≤  np\;\leq\;\sqrt n 小于n的倍数（除了1倍数），剩下的就是小于n的所有素数

  • 欧几里得除法（带余除法）： a  ∈  Z,  b  ∈  Z+,  ∃(q,  r),  s.t.  a  =  bq  +  r,  0  ≤  r  <  ba\;\in\;Z,\;b\;\in\;Z^+,\;\exists(q,\;r),\;s.t.\;a\;=\;bq\;+\;r,\;0\;\leq\;r\;<\;b
    绝对值最小余数：−  b2  ≤  r  <  b2-\;\frac b2\;\leq\;r\;<\;\frac b2
    b进制转化为十进制：n  =  akbk  +  ak−1bk−1  +  .  .  .  +  a1b  +  a0n\;=\;a_kb^k\;+\;a_{k-1}b^{k-1}\;+\;.\;.\;.\;+\;a_1b\;+\;a_0 ;
    十进制转化为b进制：a=q1b+r1;q1=q2b+r2;q2=q3b+r3;⋯qn=0×b+rn;n=(rn⋯r3r2r1)b\\a=q_1b+r_1;\\q_1=q_2b+r_2;\\q_2=q_3b+r_3;\\\cdots\\q_n=0\times b+r_n;\\n={\left(r_n\cdots r_3r_2r_1\right)}_b

  • a  =  bq  +  c  ⇒  (a,  b)  =  (b,  c)a\;=\;bq\;+\;c\;\Rightarrow\;(a,\;b)\;=\;(b,\;c)
      (a,  b)  =  (a,  ax  +  b)  =  (a  +  bx,  b)\;(a,\;b)\;=\;(a,\;ax\;+\;b)\;=\;(a\;+\;bx,\;b) , x为整数
    辗转相除法：(a,  b)  =  (b,  r2)  =  (r2,  r3)  =  (r3,  r4)  =  .  .  .  =  (rn−2,  rn−1)  =  (rn−1,  rn)  =  rn(a,\;b)\;=\;(b,\;r2)\;=\;(r2,\;r3)\;=\;(r3,\;r4)\;=\;.\;.\;.\;=\;(r_{n-2},\;{r_n}_{-1})\;=\;(r_{n-1},\;r_n)\;=\;r_n
    (2a  −  1,  2b  −  1)  =  2(a,b)  −  1(2^a\;-\;1,\;2^b\;-\;1)\;=\;2^{(a,b)}\;-\;1

  • ∀a,b∈Z+,  ∃s,t∈Z  ,  s.t.  s  ⋅  a  +  t  ⋅  b  =  (a,  b)\forall a,b\in Z^+,\;\exists s,t\in Z\;,\;s.t.\;s\;\cdot\;a\;+\;t\;\cdot\;b\;=\;(a,\;b)
    如果a，b互素，则 ∃s,  t  ∈  Z,  s.t.,  s  ⋅  a  +  t  ⋅  b  =  1\exists s,\;t\;\in\;Z,\;s.t.,\;s\;\cdot\;a\;+\;t\;\cdot\;b\;=\;1
    d  =  (a,  b)  ⇔  (d  ∣  a,  d  ∣  b)  ∧  (e  ∣  a,  e  ∣  b⇒e  ∣  d)d\;=\;(a,\;b)\;\Leftrightarrow\;(d\;\vert\;a,\;d\;\vert\;b)\;\wedge\;(e\;\vert\;a,\;e\;\vert\;b\Rightarrow e\;\vert\;d)
    ∀m  ∈  Z+,(am,  bm)  =  (a,  b)m  ⇒  (  x  (x,  y)  ,  y  (x,  y)  )  =  1  \forall m\;\in\;Z^+,(am,\;bm)\;=\;(a,\;b)m\;\Rightarrow\;(\;\frac x{\;(x,\;y)}\;,\;\frac y{\;(x,\;y)}\;)\;=\;1\;
    (a,  c)  =  1  ⇒  (ab,  c)  =  (b,  c)(a,\;c)\;=\;1\;\Rightarrow\;(ab,\;c)\;=\;(b,\;c) , 进而，如果 (a1,  c)  =  (a2,  c)  =  .  .  .  =  (an,  c)  =  1(a_1,\;c)\;=\;(a_2,\;c)\;=\;.\;.\;.\;=\;(a_n,\;c)\;=\;1 ，则 (a1a2  .  .  .  an,  c)  =  1(a_1a_2\;.\;.\;.\;a_n,\;c)\;=\;1

  • n=p1α1p2α2⋯psαs,(α1,  α2,  .  .  .  ,  αs  ∈  Z+  ,p1  ≤  p2  ≤  p3  ≤  .  .  .  ≤  ps)n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s},(\alpha_1,\;\alpha_2,\;.\;.\;.\;,\;\alpha_s\;\in\;Z^+\;,p_1\;\leq\;p_2\;\leq\;p_3\;\leq\;.\;.\;.\;\leq\;p_s) ,其中p均为素数，且该分解式是唯一的
    n的因数个数为 (1  +  α1)  ⋅  (1  +  α2)  ⋅  .  .  .  ⋅  (1  +  αs)(1\;+\;\alpha_1)\;\cdot\;(1\;+\;\alpha_2)\;\cdot\;.\;.\;.\;\cdot\;(1\;+\;\alpha_s)
    a,b的最大公因数为 (a,  b)  =  p1  min(α1,β1)  ⋅  p2  min(α2,β2)  ⋅  .  .  .  ⋅  ps  min(αs,βs)(a,\;b)\;=\;p_1^{\;min(\alpha_1,\beta_1)}\;\cdot\;p_2^{\;min(\alpha_2,\beta_2)}\;\cdot\;.\;.\;.\;\cdot\;p_s^{\;min(\alpha_s,\beta_s)}
    n∣ab  ,  (n,a)=1  ,  n∣bn\vert ab\;,\;\left(n,a\right)=1\;,\;n\vert b , 特别地，p∣(a1a2.  .  .  an)p\vert(a_1a_2.\;.\;.\;a_n) , p为素数， 则要么 p∣a1p\vert a_1 ,要么 p∣a2p\vert a_2 ,……,要么 p∣anp\vert a_n

  • 若a,b均为正素数，则 [a,b]=ab\left[a,b\right]=ab

  • [a,b]=ab(a,b)\left[a,b\right]=\frac{ab}{\left(a,b\right)}

  • m是a,b的公倍数，则 [a,b]  ∣  m\left[a,b\right]\;\left|\;m\right.

  • [a,b]  =  p1  max(α1,β1)  ⋅  p2  max(α2,β2)  ⋅  .  .  .  ⋅  ps  max(αs,βs)\left[a,b\right]\;=\;p_1^{\;max(\alpha_1,\beta_1)}\;\cdot\;p_2^{\;max(\alpha_2,\beta_2)}\;\cdot\;.\;.\;.\;\cdot\;p_s^{\;max(\alpha_s,\beta_s)}

性质

c∣b,  b∣a  ⇒  c∣ac\vert b,\;b\vert a\;\Rightarrow\;c\vert a
c∣a,  c∣b  ⇒  c∣(sa  ±  tb)c\vert a,\;c\vert b\;\Rightarrow\;c\vert(sa\;\pm\;tb) , 进而，c∣a,  c∣b,  xa  +  yb  =  1  ⇒  c  =  ±1c\vert a,\;c\vert b,\;xa\;+\;yb\;=\;1\;\Rightarrow\;c\;=\;\pm1
a∣b,  b∣a  ⇒  a  =  ±ba\vert b,\;b\vert a\;\Rightarrow\;a\;=\;\pm b

第二章 同余

定义

m  ∣(a  −  b)m\;\vert(a\;-\;b) 则称a与b模m同余，记作 a  ≡  b(modm)a\;\equiv\;b(modm) , 可以表示a除以m的余数为b（但b不一定是最小非负余数），也可以表示a，b除以m余数相同
剩余类：Ca={c∣c≡amodm,c∈Z}C_a=\left\{c\vert c\equiv amodm,c\in Z\right\} , a=0,1,2…m−1a=0,1,2\dots m-1
完全剩余系：不同剩余类中的代表元组成的集合，例如，r0  ∈  C0,  r1  ∈  C1,  .  .  .  ,  rm−1  ∈  Cm−1,r_0\;\in\;C_0,\;r_1\;\in\;C_1,\;.\;.\;.\;,\;r_{m-1}\;\in\;C_{m-1}, 则称 {r0,r1,...,rm−1}\left\{r_0,r_1,...,r_{m-1}\right\} 为一个完全剩余系，它们模m两两不同余
完全剩余系可写成 Z/mZ={C0,C1,C2,...,Cm−1}Z/mZ=\left\{C_0,C_1,C_2,...,C_{m-1}\right\} , 定义剩余类之间存在加法、乘法运算：Ca  ⊕  Cb  :=  Ca+b  ,Ca⊙Cb  :=  CabC_a\;\oplus\;C_b\;:=\;C_{a+b}\;,C_a\odot C_b\;:=\;C_{ab} , 其原理为 a(modm)  +  b(modm)  =  (a  +  b)(modm)  ,  a(modm)  ⋅  b(modm)  =  (ab)(modm)a(modm)\;+\;b(modm)\;=\;(a\;+\;b)(modm)\;,\;a(modm)\;\cdot\;b(modm)\;=\;(ab)(modm)
简化剩余类：存在元素与m互素（实际上所有元素都与m互素）的类。φ(m)\varphi\left(m\right) 为m的简化剩余类数，数值上等于小于m与m互素的数的个数，特别地，对于素数p而言 φ(p)  =  p  −  1\varphi(p)\;=\;p\;-\;1
简化剩余系：在简化剩余类中各取一个元素组成的集合。简化剩余系可写成 (Z/mZ)∗={Ca∣0≤a≤m,(a,m)=1}(Z/mZ)\ast=\left\{C_a\vert0\leq a\leq m,(a,m)=1\right\}

定理

  • a1  ≡  b1  mod  m,  a2  ≡  b2  mod  m⇒(a1  ±  a2)  ≡  (b1  ±  b2)  mod  ma1\;\equiv\;b1\;mod\;m,\;a2\;\equiv\;b2\;mod\;m\Rightarrow(a1\;\pm\;a2)\;\equiv\;(b1\;\pm\;b2)\;mod\;m
  • a1  ≡  b1  mod  m,  a2  ≡  b2  mod  m⇒(a1  ⋅  a2)  ≡  (b1  ⋅  b2)  mod  ma1\;\equiv\;b1\;mod\;m,\;a2\;\equiv\;b2\;mod\;m\Rightarrow(a1\;\cdot\;a2)\;\equiv\;(b1\;\cdot\;b2)\;mod\;m , 特别地，∀0  ≤  i  ∈  Z,  a  ≡  b  mod  m  =⇒  ai  ≡  bi  mod  m\forall0\;\leq\;i\;\in\;Z,\;a\;\equiv\;b\;mod\;m\;=\Rightarrow\;a^i\;\equiv\;b^i\;mod\;m
    注意：ad  ≡  bd(modm)  ad\;\equiv\;bd(modm)\; 不能推出 a  ≡  b  mod  ma\;\equiv\;b\;mod\;m , （但 (d,m)=1\left(d,m\right)=1 的情况可以成立）
  • x  ≡  y  mod  m,  a0  ≡  b0  mod  m,  a1  ≡  b1  mod  m,  .  .  .  ,  ak  ≡  bk  mod  m  =⇒  (a0  +  a1x  +  a2x2  +  .  .  .  +  akxk  )  ≡  (b0  +  b1y  +  b2y2+  .  .  .  +  bkyk  )  mod  mx\;\equiv\;y\;mod\;m,\;a_0\;\equiv\;b_0\;mod\;m,\;a_1\;\equiv\;b_1\;mod\;m,\;.\;.\;.\;,\;a_k\;\equiv\;b_k\;mod\;m\;=\Rightarrow\;(a_0\;+\;a_1x\;+\;a_2x^2\;+\;.\;.\;.\;+\;a_kx^k\;)\;\equiv\;(b_0\;+\;b_1y\;+\;b_2y^2+\;.\;.\;.\;+\;b_ky^k\;)\;mod\;m
    n为十进制数 n  =  (akak−1  .  .  .  a2a1a0)10n\;=\;{(a_ka_{k-1}\;.\;.\;.\;a_2a_1a_0)}_{10} , 则 n  ≡  (ak  +  ak−1  +  .  .  .  +  a2  +  a1  +  a0)  mod  3n\;\equiv\;(a_k\;+\;a_{k-1}\;+\;.\;.\;.\;+\;a_2\;+\;a_1\;+\;a_0)\;mod\;3
    n为一千进制数 n  =  (akak−1  .  .  .  a2a1a0)1000n\;=\;{(a_ka_{k-1}\;.\;.\;.\;a_2a_1a_0)}_{1000} , 则 n  ≡  (a0  +  a2  +  a4  +  .  .  .)  −  (a1  +  a3  +  a5  +  .  .  .)  mod  7n\;\equiv\;(a_0\;+\;a_2\;+\;a_4\;+\;.\;.\;.)\;-\;(a_1\;+\;a_3\;+\;a_5\;+\;.\;.\;.)\;mod\;7
  • a  ≡  b  mod  m1  a  ≡  b  mod  m2}⇒  a  ≡  b  mod  [m1,  m2]  \left.\begin{array}{r}a\;\equiv\;b\;mod\;m_1\\\;a\;\equiv\;b\;mod\;m_2\end{array}\right\}\Rightarrow\;a\;\equiv\;b\;mod\;\lbrack m_1,\;m_2\rbrack\;
  • (a,m)=1,b∈Z\left(a,m\right)=1,b\in Z ，当 xx 取遍模m的一个完全剩余系时，ax+bax+b 也取遍模m的一个完全剩余系
  • (m1,m2)=1\left(m_1,m_2\right)=1 , 当 x1x_1 取遍模 m1m_1 的一个完全(简化)剩余系时，x2x_2 取遍模 m2m_2 的一个完全（简化）剩余系时,m1x2+m2x1m_1x_2+m_2x_1 取遍模 m1m2m_1m_2 的一个完全（简化）剩余系
  • (a,m)=1\left(a,m\right)=1 ，当 xx 取遍模m的一个简化剩余系时， axax 也取遍模m的一个简化剩余系
  • (a,  m)  =  1,  ∃a0  ∈  Z,  1  ≤  a0  <  m  ,  s.t.  aa0≡1modm(a,\;m)\;=\;1,\;\exists a_0\;\in\;Z,\;1\;\leq\;a_0\;<\;m\;,\;s.t.\;aa_0\equiv1modm
  • Wilson定理：p是素数，则 (p  −  1)!  ≡  −1  mod  p(p\;-\;1)!\;\equiv\;-1\;mod\;p
  • 欧拉函数：φ(pα)  =  pα  −  pα−1=  pα  (1  −  1p  )  \varphi(p^\alpha)\;=\;p^\alpha\;-\;p^{\alpha-1}=\;p^\alpha\;(1\;-\;\frac1p\;)\; , (m,  n)  =  1  ⇒  φ(mn)  =  φ(m)φ(n)(m,\;n)\;=\;1\;\Rightarrow\;\varphi(mn)\;=\;\varphi(m)\varphi(n)
  • n  ∈  Z+,  ∑d∣n  φ(d)  =  nn\;\in\;Z^+,\;{\sum_{}^{}}_{d\vert n}\;\varphi(d)\;=\;n
  • 欧拉定理：1  <  m  ∈  Z,(a,  m)  =  1  ⇒  aφ(m)    ≡  1  mod  m1\;<\;m\;\in\;Z,(a,\;m)\;=\;1\;\Rightarrow\;a^{\varphi(m)}\;\;\equiv\;1\;mod\;m
    费马小定理：ap  ≡  a  mod  pa^p\;\equiv\;a\;mod\;p ，其中p为素数

性质

自反性：a  ≡  a  mod  ma\;\equiv\;a\;mod\;m
对称性：a  ≡  b  mod  m  ⇒  b  ≡  a  mod  ma\;\equiv\;b\;mod\;m\;\Rightarrow\;b\;\equiv\;a\;mod\;m
传递性：a  ≡  b  mod  m,  b  ≡  c  mod  m  ⇒  a  ≡  c  mod  ma\;\equiv\;b\;mod\;m,\;b\;\equiv\;c\;mod\;m\;\Rightarrow\;a\;\equiv\;c\;mod\;m

第三章 同余方程

定义

模m的同余式：f(x)  =  anxn  +  an−1xn−1  +  ⋅  ⋅  ⋅  +  a1x  +  a0  ≡  0  mod  mf(x)\;=\;a_nx^n\;+\;a_{n-1}x^{n-1}\;+\;\cdot\;\cdot\;\cdot\;+\;a_1x\;+\;a_0\;\equiv\;0\;mod\;m 若a是该方程的一个解，则a所在的剩余类中的任意元素均满足该同余式，因此把解记作 x  ≡  a  mod  mx\;\equiv\;a\;mod\;m
同余式的解数：满足同余式的模m的剩余类的个数
逆元：若 aa0  ≡  1  mod  maa_0\;\equiv\;1\;mod\;m ，则称 a0a_0 为模m的可逆元或乘法逆，当 (a,m)=1(a,m)=1 时 a0a_0 唯一 ， 因此，a是m的简化剩余等价于a是m的可逆元
同余方程组：{f1(x)=0modm1f2(x)=0modm2⋮fk(x)=0modmk\left\{\begin{array}{l}f_1\left(x\right)=0modm_1\\f_2\left(x\right)=0modm_2\\\vdots\\f_k\left(x\right)=0modm_k\end{array}\right. 若a是该方程组的一个解，则a所在的剩余类中的任意元素均满足该同余方程组，令 m  =  [m1,  m2,  .  .  .  ,  mk]m\;=\;\lbrack m_1,\;m_2,\;.\;.\;.\;,\;m_k\rbrack ,把解记作 x  ≡  a  mod  mx\;\equiv\;a\;mod\;m
同余方程组的解数：满足同余方程组的模m的剩余类的个数
同余恒等式：h(x)  ≡  0  mod  mh(x)\;\equiv\;0\;mod\;m 对于任意整数都成立，例如 xp  −  x  ≡  0  mod  px^p\;-\;x\;\equiv\;0\;mod\;p p为素数

一次同余方程

  • ax  ≡  b  mod  max\;\equiv\;b\;mod\;m 有解,且 m  ∣  a,  d  =  (a,  m)⇔d  ∣  bm\cancel{\;\vert\;}a,\;d\;=\;(a,\;m)\Leftrightarrow d\;\vert\;b ，解数必为d
    求解一次同余方程步骤：

d=(a,m)⇒{d  ∣  b  ,  no  answerd  ∣  b⇒ad,md,bd⇒find  s  ,s.t.ad⋅s    ≡  1modmd⇒x≡s⋅bdmodmd⇒x=s⋅bd+k⋅md,k=0,1,2…d−1d=\left(a,m\right)\Rightarrow\left\{\begin{array}{l}d\cancel{\;\vert\;}b\;,\;no\;answer\\d\;\vert\;b\Rightarrow\frac ad,\frac md,\frac bd\Rightarrow find\;s\;,s.t.\frac ad\cdot s\;\;\equiv\;1mod\frac md\Rightarrow x\equiv s\cdot\frac bdmod\frac md\Rightarrow x=s\cdot\frac bd+k\cdot\frac md,k=0,1,2\dots d-1\end{array}\right.

由此可知，ax  ≡  1  mod  max\;\equiv\;1\;mod\;m 有唯一解当且仅当 (a,  m)  =  1(a,\;m)\;=\;1 ，且解为 x  ≡  s  ⋅  b  mod  mx\;\equiv\;s\;\cdot\;b\;mod\;m
其中，s用可逆元的形式可表示为 s=(ad)−1modmds=\left(\frac ad\right)^{-1}mod\frac md

一次同余方程组

  • 中国剩余定理：( mim_i 两两互素)

{x≡b1modm1x=b2modm2⋮x=bkmodmk,(m1,m2…mk)=1⇒x=M1M1′b1+M2M2′b2+…MkMk′bkmodm  ,  m=m1m2m3…mk,  Mi=mmi  ,MiMi′=1modmi\left\{\begin{array}{l}x\equiv b_1modm_1\\x=b_2modm_2\\\vdots\\x=b_kmodm_k\end{array}\right.,\left(m_1,m_2\dots m_k\right)=1\Rightarrow x=M_1M_1'b_1+M_2M_2'b_2+\dots M_kM_k'b_kmodm\;,\;m=m_1m_2m_3\dots m_k,\;M_i=\frac m{m_i}\;,M_iM_i'=1modm_i

且该解唯一
若 p、q互素，n=pqn=pq ，要求 xcmodnx^cmodn 可以先求解 {y≡b1modpy≡b2modq\left\{\begin{array}{l}y\equiv b_1modp\\y\equiv b_2modq\end{array}\right. 这也为 mim_i 不互素提供了解决方案
若 b1,b2…bkb_1,b_2\dots b_k 分别遍历 m1,m2…mkm_1,m_2\dots m_k 的完全剩余系，则 x    ≡    M0′M1b1  +  M2′M2b2  +  .    .    .    +  Mk′Mkbk    mod  mx\;\;\equiv\;\;M_0'M_1b_1\;+\;M_2'M_2b_2\;+\;.\;\;.\;\;.\;\;+\;M_k'M_kb_k\;\;mod\;m 遍历m的完全剩余系;相反的，存在唯一的一组整数 b1,b2…bkb_1,b_2\dots b_k 使得 M0′M1b1  +  M2′M2b2  +  .    .    .    +  Mk′Mkbk≡bmodmM_0'M_1b_1\;+\;M_2'M_2b_2\;+\;.\;\;.\;\;.\;\;+\;M_k'M_kb_k\equiv bmodm , 进一步 (b,m)=1⇔(bi,mi)=1\left(b,m\right)=1\Leftrightarrow\left(b_i,m_i\right)=1

高次同余方程

同余方程的规约：

  • f(x)  ≡  0  mod  m  ⇔  f(x)+ms(x)  ≡  0  mod  mf(x)\;\equiv\;0\;mod\;m\;\Leftrightarrow\;f(x)+ms(x)\;\equiv\;0\;mod\;m
  • f(x)  ≡  0  mod  m  ⇔  f(x)  +  s(x)  ≡  s(x)  mod  mf(x)\;\equiv\;0\;mod\;m\;\Leftrightarrow\;f(x)\;+\;s(x)\;\equiv\;s(x)\;mod\;m
  •   (a,m)=1,  af(x)  ≡  0  mod  m⇔f(x)  ≡  0  mod  m\;\left(a,m\right)=1,\;af(x)\;\equiv\;0\;mod\;m\Leftrightarrow f(x)\;\equiv\;0\;mod\;m ,则有 anxn  +  an−1xn−1  +  .  .  .  +  a1x  +  a0  ≡  0  mod  m⇔xn  +  an−1an−1xn−1  +  .  .  .  +  an−1a1x  +  an−1a0  ≡  0  mod  ma_nx_n\;+\;a_{n-1}x_{n-1}\;+\;.\;.\;.\;+\;a_1x\;+\;a_0\;\equiv\;0\;mod\;m\Leftrightarrow x_n\;+\;a_n^{-1}a_{n-1}x_{n-1}\;+\;.\;.\;.\;+\;a_n^{-1}a_1x\;+\;a_n^{-1}a_0\;\equiv\;0\;mod\;m (此处也可看作同时乘以anmodma_nmodm 的乘法逆)
  • 如果有同余恒等式h(x),整系数多项式q(x)使得 f(x)  =  q(x)h(x)  +  r(x)f(x)\;=\;q(x)h(x)\;+\;r(x) 成立，则 f(x)≡0modm⇔r(x)≡0modmf\left(x\right)\equiv0modm\Leftrightarrow r\left(x\right)\equiv0modm q(x)可通过欧几里得多项式除法得到
  • 设d为m的正因子，则 f(x)  ≡  0  mod  mf(x)\;\equiv\;0\;mod\;m 有解的必要条件是 f(x)  ≡  0  mod  df(x)\;\equiv\;0\;mod\;d 有解

高次同余方程解的个数：

  • 当 m1,m2…mkm_1,m_2\dots m_k 两两互素，m=m1m2…mkm=m_1m_2\dots m_k 时， f(x)  ≡  0  mod  m  ⇔{f(x)  ≡  0  mod  m1f(x)  ≡  0  mod  m2⋮f(x)  ≡  0  mod  mkf(x)\;\equiv\;0\;mod\;m\;\Leftrightarrow\left\{\begin{array}{l}f(x)\;\equiv\;0\;mod\;m_1\\f(x)\;\equiv\;0\;mod\;m_2\\\vdots\\f(x)\;\equiv\;0\;mod\;m_k\end{array}\right.
    对方程组的每个方程单独求解，可以得到 {x  ≡  b1  mod  m1x  ≡  b2  mod  m2⋮x  ≡  bk  mod  mk\left\{\begin{array}{l}x\;\equiv\;b_1\;mod\;m_1\\x\;\equiv\;b_2\;mod\;m_2\\\vdots\\x\;\equiv\;b_k\;mod\;m_k\end{array}\right. 再根据中国剩余定理， 解可以写成 x=M1M1′b1+M2M2′b2+…MkMk′bkmodmx=M_1M_1'b_1+M_2M_2'b_2+\dots M_kM_k'b_kmodm 的形式。
    因此解的个数为 T=T1T2…TkT=T_1T_2\dots T_k TiT_i 即为方程组中每个方程解的个数

  • 如果 x  ≡  c1,  c2,  c3,  .  .  .  ,  ck  mod  px\;\equiv\;c_1,\;c_2,\;c_3,\;.\;.\;.\;,\;c_k\;mod\;p 是同余方程 f(x)  ≡  0  mod  pf(x)\;\equiv\;0\;mod\;p 的k个不同解，则有 f(x)  ≡  (x  −  c1)(x  −  c2)(x  −  c3).  .  .(x  −  ck)fk(x)  mod  p.f(x)\;\equiv\;(x\;-\;c_1)(x\;-\;c_2)(x\;-\;c_3).\;.\;.(x\;-\;c_k)f_k(x)\;mod\;p. 解数 k  ≤  min(p,  n)k\;\leq\;min(p,\;n) 。特例：当f(x)次数小于p的同余方程 f(x)  ≡  0  mod  pf(x)\;\equiv\;0\;mod\;p 有p个解则都p整除f(x)每项系数

  • 若系数为1 f(x)  =  xn  +  an−1x  n−1  +  .  .  .  +  a2x2  +  a1x  +  a0,  n  ≤  p,  xp  −  x  =  f(x)q(x)  +  r(x)f(x)\;=\;x^n\;+\;a_{n-1}x^{\;n-1}\;+\;.\;.\;.\;+\;a_2x^2\;+\;a_1x\;+\;a_0,\;n\;\leq\;p,\;x^p\;-\;x\;=\;f(x)q(x)\;+\;r(x) ， 同余方程 f(x)  ≡  0  mod  pf(x)\;\equiv\;0\;mod\;p 有n个解当且仅当r(x)的系数均为p的倍数

求解模为素数幂的同余方程：
f(x)  ≡  0  mod  pαf(x)\;\equiv\;0\;mod\;p^\alpha , p为素数
原理: f(a)≡0modpα⇒f(a)≡0modpα−1f(c)≡0modpα−1}    ⇒a≡cmodpα−1⇒a=kpα−1+c\left.\begin{array}{r}f\left(a\right)\equiv0modp^\alpha\Rightarrow f\left(a\right)\equiv0modp^{\alpha-1}\\f\left(c\right)\equiv0modp^{\alpha-1}\end{array}\right\}\;\;\Rightarrow a\equiv cmodp^{\alpha-1}\Rightarrow a=kp^{\alpha-1}+c\\
求解k：解一次同余方程 f′(c)  ⋅  k  ≡  −f(c)pα−1    mod  pf'(c)\;\cdot\;k\;\equiv\;\frac{-f(c)}{p^{\alpha-1}}\;\;mod\;p

{d=(f′(c),p)=1,  only  one  solutiond=(f′(c),p)=p{p  ∣  −f(c)pα−1  ,no  solutionp∣−f(c)pα−1  ,p  solutions,  k=0,1,2…,p−1\left\{\begin{array}{l}d=\left(f'\left(c\right),p\right)=1,\;only\;one\;solution\\d=\left(f'\left(c\right),p\right)=p\left\{\begin{array}{l}p\cancel{\;\vert\;}\frac{-f\left(c\right)}{p^{\alpha-1}}\;,no\;solution\\p\vert\frac{-f\left(c\right)}{p^{\alpha-1}}\;,p\;solutions,\;k=0,1,2\dots,p-1\end{array}\right.\end{array}\right.

由此算法，可从 f(x)  ≡  0  mod  pf(x)\;\equiv\;0\;mod\;p 的解递推至 f(x)  ≡  0  mod  pαf(x)\;\equiv\;0\;mod\;p^\alpha 的解

第四章 二次剩余

定义

二次剩余（平方剩余）：设素数p>2, x2≡amodpx^2\equiv amodp 有解，则称a是一个模p的二次剩余，否则称a为一个模p的二次非剩余。一般来说，x  ≡  0  mod  px\;\equiv\;0\;mod\;p 两者都不属于。
勒让德符号(只有p为素数时才有意义)：(ap)={1⇒a  is  the  square  remainder  modulo  p−1⇒a  is  a  square  non−residue  modulo  p0⇒p∣a\left(\frac ap\right)=\left\{\begin{array}{l}1\Rightarrow a\;is\;the\;square\;remainder\;modulo\;p\\-1\Rightarrow a\;is\;a\;square\;non-residue\;modulo\;p\\0\Rightarrow p\vert a\end{array}\right.\\
雅可比符号：(am)=(ap1)⋅(ap2)⋅⋯⋅(apn)\left(\frac am\right)=\left(\frac a{p_1}\right)\cdot\left(\frac a{p_2}\right)\cdot\dots\cdot\left(\frac a{p_n}\right) ,其中 (api)\left(\frac a{p_i}\right) 为勒让德符号，m=p1p2…pnm=p_1p_2\dots p_n ,

二次同余方程解的存在性

  • p为奇素数，p的简化剩余系中恰有 p−12\frac{p-1}2 个二次剩余，p−12\frac{p-1}2 个二次非剩余，如果a是模p的二次剩余，则 x2≡amodpx^2\equiv amodp 解数为2。
  • p为奇素数，(a,p)=1\left(a,p\right)=1 ,a是模p的平方剩余 ⇔ap−12≡1modp\Leftrightarrow a^\frac{p-1}2\equiv1modp , a是模p的平方非剩余 ⇔ap−12≡−1modp\Leftrightarrow a^\frac{p-1}2\equiv-1modp

勒让德符号

  • p为奇素数，ap−12≡(ap)modpa^\frac{p-1}2\equiv\left(\frac ap\right)modp
  • 性质：
    (a+kpp)≡(ap)\left(\frac{a+kp}p\right)\equiv\left(\frac ap\right)
    a  ≡  b  mod  p  ⇒  (  ap  )  =  (  bp  )a\;\equiv\;b\;mod\;p\;\Rightarrow\;(\;\frac ap\;)\;=\;(\;\frac bp\;)
    (  abp  )  =  (  ap  )(  bp  )(\;\frac{ab}p\;)\;=\;(\;\frac ap\;)(\;\frac bp\;)
    (a,p)=1⇒(a2p)=1(a,p)=1\Rightarrow \left ( \frac{a^{2} }{p} \right ) =1
    (1p)=1\left(\frac1p\right)=1 , (−1p)=(−1)p−12\left(\frac{-1}p\right)=\left(-1\right)^\frac{p-1}2
    (2p)=(−1)p2−18\left ( \frac{2}{p} \right )=\left ( -1 \right )^{\frac{p^{2}-1}{8} }
  • 高斯引理：p为奇素数，(a,p)=1(a,p)=1 , a⋅1,a⋅2,…,a⋅p−12a \cdot 1, a \cdot 2, \ldots, a \cdot \frac{p-1}{2} 模p后最小正剩余大于 p2\frac{p}{2} 的个数是m，则 (ap)=(−1)m\left(\frac{a}{p}\right)=(-1)^{m}
  • 二次互反律：若p，q均为奇素数，则 (pq)=(−1)p−12q−12(qp)\left ( \frac{p}{q} \right ) =\left ( -1 \right )^{\frac{p-1}{2} \frac{q-1}{2}} \left ( \frac{q}{p} \right )

雅可比符号

  • 性质：
    (m,n)>1,  (mn)=(nm)=0\left(m,n\right)>1,\;\left(\frac mn\right)=\left(\frac nm\right)=0
    (a+kmm)=(am)\left(\frac{a+km}m\right)=\left(\frac am\right)
    (abm)=(am)(bm)\left(\frac{ab}m\right)=\left(\frac am\right)\left(\frac bm\right)
    (a,m)=1,  (a2m)=1\left(a,m\right)=1,\;\left(\frac{a^2}m\right)=1
    (1m)=1\left(\frac1m\right)=1 , (−1m)=(−1)m−12\left(\frac{-1}m\right)=\left(-1\right)^\frac{m-1}2
    (2m)=(−1)m2−18\left(\frac2m\right)=\left(-1\right)^\frac{m^2-1}8
  • 二次互反律：若m，n均为奇素数的乘积，且 (m,n)=1(m,n)=1 ,则 (mn)=(−1)m−12n−12(nm)\left(\frac mn\right)=\left(-1\right)^{\frac{m-1}2\frac{n-1}2}\left(\frac nm\right)
  • 注意：(nm)=1⇒  x2≡nmodm\left(\frac nm\right)=1\cancel\Rightarrow\;x^2\equiv nmodm 有解

二次同余方程求解

模素数p

  • p=4k+3:x≡±ak+1modp=±ap+14modpp=4k+3:x\equiv\pm a^{k+1}modp=\pm a^\frac{p+1}4modp
  • 求解 x2≡amodpx^2\equiv amodp (p为素数)通用方法：
  1. 判断勒让德符号 (ap)\left(\frac ap\right) 是否等于1来判断是否有解
  2. p−1=2t⋅sp-1=2^t\cdot s , 求出t,s, a−1a^{-1}
  3. 取模p的一个平方非剩余n,计算 b=nsmodpb=n^smodp
  4. i=1,2,…,t,代入以下循环，直到i=t,可求得两个解 x=±x0x=\pm x_0

y2t−i  ≡  1  mod  p{i=1⇒xt−1  =  as+12⇒a−1xt−1i≠1⇒(a−1xt−i+1)2t−i={1modp⇒xt−i=xt−i+1⇒a−1xt−i−1modp⇒xt−i=xt−i+1b2i−2⇒a−1xt−iy^{2^{t-i}}\;\equiv\;1\;mod\;p\left\{\begin{array}{l}i=1\Rightarrow x_{t-1}\;=\;a^\frac{s+1}2\Rightarrow a^{-1}x_{t-1}\\i\neq1\Rightarrow{(a^{-1}x_{t-i+1})}^{2^{t-i}}=\left\{\begin{array}{l}1modp\Rightarrow x_{t-i}=x_{t-i+1}\Rightarrow a^{-1}x_{t-i}\\-1modp\Rightarrow x_{t-i}=x_{t-i+1}b^{2^{i-2}}\Rightarrow a^{-1}x_{t-i}\end{array}\right.\end{array}\right.

模奇素数幂
详见第三章
模2的幂
x2≡amod2δx^2\equiv amod2^\delta

{δ=2→2solutions:±1δ≥3→only  when  a≡1mod8  has  4  solutions→x4=±(1+22t3)  satisfies  x2≡amod24→t3≡a−18mod2→x5=±(x4+23t4  )  satisfies  x2≡amod25→t4≡a−x4224mod2→⋯→x=±(xδ+2δ−1tδ)(tδ−1=0,1,2… )\left\{\begin{array}{l}\delta=2\rightarrow2solutions:\pm1\\\delta\geq3\rightarrow only\;when\;a\equiv1mod8\;has\;4\;solutions\rightarrow x_4=\pm(1+2^2t_3)\;satisfies\;x^2\equiv amod2^4\rightarrow t_3\equiv\frac{a-1}8mod2\rightarrow x_5=\pm(x_4+2^3t_{4\;})\;satisfies\;x^2\equiv amod2^5\rightarrow t_4\equiv\frac{a-x_4^2}{2^4}mod2\rightarrow\dots\rightarrow x=\pm(x_\delta+2^{\delta-1}t_\delta)(t_{\delta-1}=0,1,2\dots)\end{array}\right.

其中，ti≡a−xi22imod2t_i\equiv\frac{a-x_i^2}{2^i}mod2

模合数m
结合第二、三种情况

第五章 原根与指标

定义

指数：as  ≡  1  mod  ma^s\;\equiv\;1\;mod\;m a,m互素，e为s的最小值，称为a对模m的指数，记为 ordm(a)ord_m(a)
原根：如果 ordm(a)=φ(m)ord_m(a)=\varphi(m) ，则称a为m的原根
指标：g是模p的原根，a是模p的一个简化剩余系，gr≡amodpg^r\equiv amodp ,称r为以g为底a对模p的指标，记为 indgaind_ga 或 indainda

指数的性质与定理

  • a,m互素，ad≡1modm⇔ordm(a)∣da^d\equiv1modm\Leftrightarrow ord_m(a)\vert d 因此，必有 ordm(a)∣  φ(m)ord_m(a)\vert\;\varphi(m)
    为了求a的指数可以直接在 φ(m)\varphi(m) 的因子里找
  • a,m互素，n∣m⇒ordn(a)∣ordm(a)n\vert m\Rightarrow ord_n(a)\vert ord_m(a)
  • a,m互素，b≡amodm⇒ordm(b)=ordm(a)b\equiv amodm\Rightarrow ord_m(b)=ord_m(a)
  • a,m互素 ab  ≡  1  mod  m⇒ordm(a)  =  ordm(b)ab\;\equiv\;1\;mod\;m\Rightarrow ord_m(a)\;=\;ord_m(b)
  • 当a是m的原根时，a0,a1…aφ(m)−1a^0,a^1\dots a^{\varphi(m)-1} 是m的一个简化剩余系
  • ak≡almodm⇔k≡l  mod  ordm(a)a^k\equiv a^lmodm\Leftrightarrow k\equiv l\;mod\;ord_m(a)
  • a,m互素 ,m>1, k≥0k\geq0 ,ordm(ak)=ordm(a)(ordm(a),k)ord_m(a^k)=\frac{ord_m(a)}{(ord_m(a),k)}
    推论：当a是m的原根时，若 (k,ordm(a))=1\left(k,ord_m(a)\right)=1 ,则 aka^k 也是m的原根，即从m的简化剩余系中随机取一个数是模m原根的概率是 φ(ordm(a))φ(m)=φ(φ(m))φ(m)\frac{\varphi(ord_m(a))}{\varphi(m)}=\frac{\varphi(\varphi(m))}{\varphi(m)}
  • ordm(ab)  =  ordm(a)  ⋅  ordm(b)  ⇔  (ordm(a),  ordm(b))  =  1ord_m(ab)\;=\;ord_m(a)\;\cdot\;ord_m(b)\;\Leftrightarrow\;(ord_m(a),\;ord_m(b))\;=\;1 ；若 (ordm(a),  ordm(b))  ≠  1(ord_m(a),\;ord_m(b))\;\neq\;1 ,则存在c，ordm(c)  =  [ordm(a),  ordm(b)]ord_m(c)\;=\;\lbrack ord_m(a),\;ord_m(b)\rbrack
  • a，m，n两两互素，ordmn(a)  =  [ordm(a),  ordn(a)]ord_{mn}(a)\;=\;\lbrack ord_m(a),\;ord_n(a)\rbrack ；当a≠ba\neq b 时，a,b与mn互素，ordmn(c)  =  [ordm(a),  ordn(b)]ord_{mn}(c)\;=\;\lbrack ord_m(a),\;ord_n(b)\rbrack
    推论：a，m互素，m  =  2  α1  p2  α2  p3  α3  .  .  .  ps  αsm\;=\;2^{\;\alpha_1}\;p_2^{\;\alpha_2}\;p_3^{\;\alpha_3}\;.\;.\;.\;p_s^{\;\alpha_s} , ordm(a)  =  [ord2α1  (a),  ordp2α2  (a),  .  .  .  ,  ordpsαs  (a)]ord_m(a)\;=\;\lbrack ord_{2^{\alpha_1}\;}(a),\;ord_{p_2^{\alpha_2}\;}(a),\;.\;.\;.\;,\;ord_{p_s^{\alpha_s}}\;(a)\rbrack
  • ord2l  (a)∣2  l−2  (l  ≥  3)ord_{2^l}\;(a)\vert2^{\;l-2}\;(l\;\geq\;3) ,结合上一条定理，ordm(a)∣[2  α1−2  ,φ(p2α2  ),  φ(p3α3  ),  .  .  .  ,  φ(psαs  )]ord_m(a)\vert\lbrack2^{\;\alpha_1-2}\;,\varphi(p_2^{\alpha_2}\;),\;\varphi(p_3^{\alpha_3}\;),\;.\;.\;.\;,\;\varphi(p_s^{\alpha_s}\;)\rbrack
  • p是奇素数，m存在原根 ⇔m=1/2/4/pα/2pα\Leftrightarrow m=1/2/4/p^\alpha/2p^\alpha

模素数p的原根

  • 设p为奇素数，q1,  q2,  .  .  .  ,  qsq_1,\;q_2,\;.\;.\;.\;,\;q_s 是p-1的所有素因数，g是模p的原根当且仅当 gp−1qi≠  1(  mod  p),  i  =  1,  2,  .  .  .  ,  sg^\frac{p-1}{q_i}\neq\;1(\;mod\;p),\;i\;=\;1,\;2,\;.\;.\;.\;,\;s
  • 若g为 pα+1p^{\alpha+1} 的原根，则g必为 pαp^\alpha 的原根
  • 若g为模 pαp^\alpha 的原根，则必有 ordpα+1(g)=φ(pα)ord_{p^{\alpha+1}}(g)=\varphi(p^\alpha) 或 ordpα+1(g)=φ(pα+1)ord_{p^{\alpha+1}}(g)=\varphi(p^{\alpha+1})
  • g是模奇素数p的原根，且g满足 gp−1≡1+rp(p  ∣  r)g^{p-1}\equiv1+rp(p\cancel{\;\vert\;}r) ,则g是模 pαp^\alpha 的原根
  • 设 g′g' 是模奇素数p的原根，则 g=g′,g=g′+p,g=g′+2p,…g=g′+(p−1)pg=g',g=g'+p,g=g'+2p,\dots g=g'+(p-1)p 都是模p的原根，且只有一个不满足条件 gp−1≡1+rp(p  ∣  r)g^{p-1}\equiv1+rp(p\cancel{\;\vert\;}r) ，其余都满足

指标

前提：g是模p的原根，a是模p的一个简化剩余系

  • gs  ≡  a  mod  m  ⇒  s  ≡  indga  mod  φ(m)g^s\;\equiv\;a\;mod\;m\;\Rightarrow\;s\;\equiv\;ind_ga\;mod\;\varphi(m)
  • indg(a1  .  .  .  an)  ≡  indga1  +  .  .  .  +  indgan  mod  φ(m)ind_g(a_1\;.\;.\;.\;a_n)\;\equiv\;ind_ga_1\;+\;.\;.\;.\;+\;ind_ga_n\;mod\;\varphi(m)
  • φ(m)  =  (φ(m),  indga)  ⋅  ordm(a)\varphi(m)\;=\;(\varphi(m),\;ind_ga)\;\cdot\;ord_m(a) ,由此推论，若a是模m的原根，则 (φ(m),  indga)  =  1(\varphi(m),\;ind_ga)\;=\;1
  • 模m的简化剩余系中，指数等于e的整数个数就是 φ(e)\varphi(e)
  • xn  ≡  a  mod  mx^n\;\equiv\;a\;mod\;m 有解 ⇔  (n,  φ(m))∣indga\Leftrightarrow\;(n,\;\varphi(m))\vert ind_ga ,有解的话解数为 (n,  φ(m))(n,\;\varphi(m)) ,进一步地，a是模m的n次剩余 ⇔aφ(m)(n,φ(m))≡1modm\Leftrightarrow a^\frac{\varphi(m)}{(n,\varphi(m))}\equiv1modm

第六章 素性检验

定义

伪素数：设n是一个合数，如果存在与n互素的数b，bn−1≡1modnb^{n-1}\equiv1modn 则称n为基于b的伪素数
卡米切尔数：n是一个合数，但对n简化剩余系中的所有数，都有 bn−1≡1modnb^{n-1}\equiv1modn
Euler伪素数：n是一个合数，存在与n互素的数b使得 bn−12≡(bn)modnb^\frac{n-1}2\equiv\left(\frac bn\right)modn ，称n是基b的Euler伪素数
强伪素数：n是一个合数，存在与n互素的数b满足 bn−1−1=b2st−1=(bt−1)(bt+1)(b2t+1)(b22t+1)…(b2s−1t+1)≡0modnb^{n-1}-1=b^{2^st}-1=\left(b^t-1\right)\left(b^t+1\right)\left(b^{2t}+1\right)\left(b^{2^2t}+1\right)\dots\left(b^{2^{s-1}t}+1\right)\equiv0modn 存在一个括号内等于0，称n是基b的强伪素数

伪素数

  • 存在无穷多个基于2的伪素数
  • 设n是一个奇合数，则n是基于b的伪素数 ⇔ordn(b)∣n−1\Leftrightarrow ord_n(b)\vert n-1
  • 设n是一个奇合数，n是一个基a的伪素数，基b的伪素数，则n是对于基ab的伪素数
  • 设n是一个奇合数，n是一个基b的伪素数，则n也是基b^{-1}的伪素数
  • bib_i 属于模n的简化剩余系，则有 ≥12\geq\frac12 的概率使得 bin−1≠1modnb_i^{n-1}\neq1modn

Euler伪素数

  • n是基b的Euler伪素数可以推出n为基于b的伪素数，反之不然

强伪素数

  • 存在无穷多个基2的强伪素数
  • n是基b的强伪素数，则n是基b的Euler伪素数，则n是基b的伪素数
  • n是合数，则随机选取与n互素的b，n是基b的强伪素数的概率至多为 14\frac14
  • 强伪素数的检验方法可以检验出卡米切尔数为合数

第七章 连分数

定义

有限简单连分数：x0+1x1+1x2+1⋱xi−1+1xix_0+\frac1{x_1+{\displaystyle\frac1{x_2+{\displaystyle\frac1{\ddots x_{i-1}+{\displaystyle\frac1{x_i}}}}}}}\\\\ ，x0x_0 是整数，x1,x2…xix_1,x_2\dots x_i 是正整数。可以记为 [x0,x1…xi]\left[x_0,x_1\dots x_i\right]
第k个渐进分数：[x0,x1…xk]=PkQk\left[x_0,x_1\dots x_k\right]=\frac{P_k}{Q_k}
无限简单连分数：[x0,x1…xn−1,… ]\left[x_0,x_1\dots x_{n-1},\dots\right],若 lim⁡k→∞[x0,x1…xk]=θ\lim_{k\rightarrow\infty}\left[x_0,x_1\dots x_k\right]=\theta 则称收敛，若不存在极限则称发散。
例如，2=[1,2,2,2… ]\sqrt2=\left[1,2,2,2\dots\right] ，是收敛的。
n阶连分数：n条分数线
纯循环连分数：类似 5+12=[1,1,1… ]=[1‾]\frac{\sqrt5+1}2=\left[1,1,1\dots\right]=\left[\overline1\right] ,刚开始就循环
实二次无理数：α=r+sd\alpha=r+s\sqrt d r,s（s不为0）为有理数，d为非平方数，则 α\alpha 为实二次无理数

有理分数的简单连分数表示

  • pq=[⌊pq⌋,⌊qr0⌋,⌊r0r1⌋…⌊rk−1rk⌋],rk+1=0\frac pq=\left[\left\lfloor\frac pq\right\rfloor,\left\lfloor\frac q{r_0}\right\rfloor,\left\lfloor\frac{r_0}{r_1}\right\rfloor\dots\left\lfloor\frac{r_{k-1}}{r_k}\right\rfloor\right],r_{k+1}=0
  • 有理分数的简单连分数表示是唯一的

有限连分数

  • 嵌套：[x0,x1,…xn,xn+1,xn+2…xn+r]=[x0,x1,…xn,[xn+1,xn+2…xn+r]]=[x0,x1,…xn,xn+1+1[xn+2…xn+r]]\left[x_0,x_1,\dots x_n,x_{n+1},x_{n+2}\dots x_{n+r}\right]=\left[x_0,x_1,\dots x_n,\lbrack x_{n+1},x_{n+2}\dots x_{n+r}\rbrack\right]=\left[x_0,x_1,\dots x_n,x_{n+1}+\frac1{\lbrack x_{n+2}\dots x_{n+r}\rbrack}\right]
  • 偶数阶连分数加t（或t阶）递增
  • 奇数阶连分数加t（或t阶）递减
  • θn∈[θ0,θ1]\theta_n\in\lbrack\theta_0,\theta_1\rbrack
  • 对第n个渐进分数 PnQn\frac{P_n}{Q_n} , 满足 Pn={xnPn−1+Pn−2,  n≥01,n=−10,n=−2P_n=\left\{\begin{array}{l}x_nP_{n-1}+P_{n-2},\;n\geq0\\1,n=-1\\0,n=-2\end{array}\right. , Qn={xnQn−1+Qn−2,  n≥00,n=−11,n=−2Q_n=\left\{\begin{array}{l}x_nQ_{n-1}+Q_{n-2},\;n\geq0\\0,n=-1\\1,n=-2\end{array}\right.
  • 对第n个渐进分数 PnQn\frac{P_n}{Q_n} , 满足 PnQn−1  −  Pn−1Qn  =  (−1)n+1  P_nQ_{n-1}\;-\;P_{n-1}Q_n\;=\;{(-1)}^{n+1}\;
  • 对第n个渐进分数 PnQn\frac{P_n}{Q_n} , 满足 PnQn−2  −  Pn−2Qn  =  (−1)n    xnP_nQ_{n-2}\;-\;P_{n-2}Q_n\;=\;{(-1)}^n\;\;x^n
  • P0Q0<⋯<P2n−2Q2n−2<P2nQ2n<⋯<P2n+1P2n+1<P2n−1Q2n−1⋯<P1Q1\frac{P_0}{Q_0}<\dots<\frac{P_{2n-2}}{Q_{2n-2}}<\frac{P_{2n}}{Q_{2n}}<\dots<\frac{P_{2n+1}}{P_{2n+1}}<\frac{P_{2n-1}}{Q_{2n-1}}\dots<\frac{P_1}{Q_1}

无限连分数

  • 无限简单连分数一定是收敛的
  • θ\theta 是循环简单分数 ⇔\Leftrightarrow θ\theta 是实二次无理数
  • 连分数的因式分解法：
    方法一：列出渐进分数表 ，若存在 i≠j,  Pi2  ≡  Pj2modni\neq j,\;P_i^2\;\equiv\;P_j^2modn ,令 x  =  (Pi  mod  n)  ⋅  (Pj  mod  n)  ,    y  =  Pi2  mod  n  =  Pj2  mod  nx\;=\;(P_i\;mod\;n)\;\cdot\;(P_j\;mod\;n)\;,\;\;y\;=\;P_i^2\;mod\;n\;=\;P_j^{2\;}mod\;n 若 (x+y,n)≠n(x+y,n)\neq n 且 (x−y,n)≠n(x-y,n)\neq n 则它们即为n的真因数
    方法二：若无法找到这样的i，j，则列出渐进分数表，令 Bk=Pk2−nQk2B_k=P_k^2-nQ_k^2 ,若 BkB_k 为平方数，则有 n∣(Pk−Bk)(Pk+Bk)n\vert\left(P_k-\sqrt{B_k}\right)\left(P_k+\sqrt{B_k}\right) ,同理可得其真因数