数论

前言

读研也逃不过数学，一直以来数学都是我的弱项。好记性不如烂笔头，复习的时候受算法笔记的启发，准备记录一波数论的关键知识。

第一章 因式分解

1.1 带余除法

• 定理1(带余除法)

  若a,b均为整数，$b \neq 0$，则存在唯一的整数q和r使得$$a=bq+r, 0\le r\lt \vert b \vert$$

  其中r称为余数，q称为不完全商

  证明

  数轴上以b为单位划分空间，则a必然落在某小段之中，则向左取最靠近的bq并剩余r，于是有了上述定理。

1.2 辗转相除与贝祖等式

• 定义1 最大公因子

  $gcd(a, b)$为最大公因子

  当$gcd(a, b)=1$时称a与b互素

• 定理1 若$a=bq+r$ ,a,b,r为整数(a,b不全为零) 则有$$(a, b) = (r, b)$$

  简单理解: a,r属于一个剩余类

  由该定理可以得知 辗转相除法最后得到的余数即最大公因子

• 定理2(重点) 贝祖等式 任意两整数a,b的正最大公因子$d=(a, b)$是唯一存在的, 即$d=r_s$. 而且存在整数u,v使$$ua+vb=d$$

  系1 两整数a,b互素当且仅当存在整数u,v使得$$ua+vb=1$$

• 定理3 多个整数的正最大公因子d存在且唯一有

  $$(a_1,…,a_{s-1},a_s) = ((a_1,…,a_{s-1}),a_s)$$

  $$u_1a_1+…+u_sa_s=d (贝祖等式)$$

1.3 唯一析因定理

• 定理1 算数基本定理(重点)

  任意整数都可以写为有限个素数之积,且写法是唯一的,也就是说n可以写为$$n=p_1p_2p_3…p_t$$

  其中$p_i$为素数

• 引理1

  (1)设p为素数, 若$p 不整除 a$, 则$(p, a)=1$

  (2)设p为素数, 若$p|ab$, 则$p|a或p|b$

• 定义1 最小公倍数$lcm[x]$ , 任意公倍数必然是最小公倍数的倍数

• 定理2

• 定理3 素数的个数是无穷的

• 定理4 $n!$的拆解

  对每一个$n!$的素因子, 可以通过求$$v_p(n!)= \lfloor {n\over p} \rfloor+ \lfloor{ n\over p^2} \rfloor + …$$

  比如$11!$, 素因子2的指数为$\lfloor {11\over 2} \rfloor + \lfloor {11\over 4} \rfloor + \lfloor {11\over 8} \rfloor = 5+2+1 = 8$

1.4 线性丢番方程

• 定理1 对于二元一次方程 $ax+by=c$

  (1)(证明?)方程有解当且仅当$(a,b)|c$, 有解时可以有$a’x+b’y=c’$ 其中abc'为abc被$gcd(a, b)整除的值, 且可由辗转相除得到相同解.

  (2)若方程有特别解$x=x_0,y=y_0$ 则可推出方程整数解为$$ \begin{cases} x=x_0+kb’ \\ y=y_0+ka’ \end{cases}$$

• 定理2 对于多元一次不定方程$$a_1x_1+…a_sx_s=n$$有解当且仅当$(a_1,…,a_s)|n$

1.5 多项式的分解

主要是将前面章节 从带余除法开始, 把多项式作为一个整体, 将各类性质带入。

1.6 总结

• 判断ax+by=c有解当且仅当(a,b)|c

第二章 同余与同余类

2.1 整数同余

• 定义1 $m|(a-b) 意味着 a \equiv b (mod m)$
• 定理1 同余符号具有以下性质
  • 传递性
  • 对称性
  • 自反性
  • 同余式相加
  • 同余式相乘
  • 同余式约化
  • 多同余式通过最小公倍数合并

2.2 同余类集

• 集合划分-代表元

  $$\overline{x} = a+mZ = \lbrace a+mk|k\subseteq{Z}\rbrace $$

  可加法可乘法

• 环

  R为集合，其中元素之间有加法乘法，且满足以下条件

  对加法

  • 加法封闭
  • 加法结合律
  • 存在单位元
  • 存在加法逆元
  • 加法交换律

  对乘法

  • 乘法封闭性
  • 乘法结合律
  • 乘法单位元

  则称该集合为环

2.3 同余类环的单位

• 欧拉函数

  $\phi(m)$表示小于m且与m互素的代表元集合，欧拉函数值为集合的个数

  其元素取出来代表元得到的集合，成为m的一个既约剩余系

• 欧拉函数常用等式

  P45

• $\sum_{d|m} \phi(d)=m$

• 考虑同余式

  $$ax\equiv{b}(mod m)$$

  (1)如果(a, m)=1, 则有唯一解.

  (2)如果(a, m)=d>1, 则当且仅当$$d|b$时有解, 且有d个不同解(模m意义下)

2.4 Fermat-Euler定理

• 费马小定理

  设p为不整除a的素数, 则

  $$a^{p-1}\equiv{1}(mod p)$$

  $$亦可写为 a^p\equiv{a}(mod p)$$

• 欧拉定理

  设整数a与m互素, 则

  $$a^{\phi(m)}\equiv{1}(mod m)$$

• Wilson定理

  p是素数当且仅当$(p-1)! \equiv {-1} mod (p)$

2.5 孙子定理

重点 看书

第三章 原根与同余方程

3.1 群及元素的阶

• 群的定义

  一个群就是一个集合G, 其中的元素之间都满足一个二元运算, 具有一下4条公理

  • GR1:(封闭性) $ab\in{G}$
  • GR2:(结合律) $(ab)c = a(bc)$
  • GR3:(存在单位元) 存在元素$e\in{G}$ 使得 $ea=ae=a$, 其中$e$被称为单位元
  • GR4:(元素皆可逆) 对任意$a\in{G}$, 存在$a’\in{G}$ 使得$aa’=a’a=e$, 其中$a’$被称为逆元

  若群中元素还满足:

  • COMM: 交换律即$ab=ba$, 则称群为交换群或者Abel(阿贝尔)群

• 群的引理(P60)

  (1)单位元是唯一的

  (2)逆元是唯一的

• 群阶

  群G的元素个数被称为群G的阶(order),记为$#G$ 或 $|G|$.

  有限阶的群成为有限群, 设H是G的子集和, 以G的运算和单位元构成群, 则称H是G的子群, 记为$H<G$

• 元素阶

  对$a\in{G}$,考虑$a^k$

  • 当$a^k\not = 1\quad(k\not = 0)$, 则称元素a的阶无穷, 记为$ord(a) = \infty$
  • 当$a^k = 1\quad(k\not = 0)$, 则存在$a^n=1$的最小正整数n; 此时称n为元素a的阶, 记为$ord(a) = n$

• 阶引理

  对$a\in{G}, ord(a)=n$则

  $$a^k=1 \Leftrightarrow ord(a)|k$$

• 循环群

  设a为G中元素, 则集合$<a>=\lbrace \ldots, a^{-1}, 1 , a, a^2,\cdots \rbrace$

  是G的一个Abel子群, 则称$<a>$为a生成的循环子群,a为此群的生成元.

  若$G=<a>$, 则称G为循环群

  (1)当$ord(n)=\infty$时, $<a>$是无限群, 当$i\not=j, a^i\not=a^j$.

  (2)$ord(n)=n$, 对任意k=nq+r, 有$a^k = a^{nq}a^r=a^r$

• 阶计算引理

  对任意乘法群G, $a\in{G}$, 阶$ord(a)=n$

  (1)若$a^r=1, a^s=1$, 则 $a^{(r,s)} = 1$

  (2)若k|n即k|ord(a),则

  $$ord(a^k)= \frac {n} {k}$$

  而对任意k有

  $$ord(a^k)= \frac {n} {(k,n)}$$

  (3)若a, b的阶分别为m, n且(m, n)=1, ab=ba, 则ab的阶为mn

• 定理1

  Abel群的元素的阶 是 群的阶的因子

  详言之, 设G为n阶有限群, 则G中任意元素a的阶$ord(a) | n$

  从而$a^n = 1, \forall{a}\in{G}$

• 定理2 拉格朗日

  子群的阶是母群阶的因子

• 映射定义

  设G, G’是两个群, 映射$\sigma: G\Rightarrow{G’}$保运算, 即

  $$\sigma(ab)=\sigma(a)\sigma(b)$$

  则称$\sigma$是群的同态映射. 如果$\sigma$是同态映射的, 并且是双射(一一对应), 则称$\sigma$是同构映射, 且称群G和G’是同构的, 记为$G\cong{G’}$

• 循环群引理P65

  n阶循环群G中， n阶元（即生成元）的个数为$\phi(n)$个

3.2 模$P^s$原根

• 原根概念

  模m的整数同余类环中Z/mZ中,可逆元集合记为

  $$U_m=(Z/mZ)^*=\lbrace{\overline{a}|(a, m)=1, 1\le a \le m}\rbrace$$

  其中含有$\phi(m)$个元素, 如果存在$g\in{Z}$使得

  $$U_m=<g>=\lbrace{1, \overline{g},\overline{g}^2,\ldots,\overline{g}^{\phi(m)-1}}\rbrace$$

  则称g为模m的一个原根(primitive root), 也称g(mod m)或$\overline{g}$为原根

  除了1,-1, 只有$m=p^s或2p^s$时, 原根存在(p为奇素数).

• 定理1

  (1)域的有限乘法子群必是循环群 P69证明 重要

  (2)任一有限域F的非零元集合$F^*$是一个循环群

  (3)设p为素数, 则模p的域为循环群, 且当d|(p-1)时, 集合中d阶元个数为$\phi(d)$, 模p原根的个数为$\phi(p-1)$

  (4)设G为n阶循环群, 则对任意d|n, G恰好有一个d阶子群且为循环群, d阶元的个数为$\phi(d)$. 特别, G的生成元(即n阶元)个数为$\phi(n)$

• 引理1

  (1)p为任意素数, $k\ge 1, a\equiv b(mod\ p^k)$, 则

  $$a^p\equiv b^p(mod\ p^{k+1})$$

  (2)若$p\not =2, k\ge 2$, 则$(1+cp)^{p^{k-2}}\equiv 1+cp^{k-1}(mod\ p^k)$

  (3)若素数$p\not = 2, p \not | c$, 则$1+cp(mod\ p^k)$的阶为$p^{k-1}$

• 定理2

  p为奇素数, 则模$p^s和2p^s$有原根, 即他们分别构成的模类为循环群

• 系1 设g为模p(奇素数)的原根

  (1)模$p^k$的原根可取为g或g+p, 依据$g^{p-1} \not \equiv 1(mod\ p^2)或否$

  (2)模$2p^k$的原根可取为$g或g+p^k$, 依据g奇或偶

  模$2p^k$的原根也可取为$g+(g-1)p^k$

3.3 模$2^s$分解

• 定理1

  当$s\ge 3$时, 模$2^s$没有原根, 内直积

• 系1 设m>1, $\phi (m)$的所有素因子为$ p_i$, (g, m)=1. 则g为模m原根的充要条件为

  $$g^{\phi(m)/{p_i}}\not \equiv 1 (mod\ m)$$

3.4 指标与n次剩余

• 定义1 指标

  设g为模m的原根, 整数a与m互素, 若整数i($0\le i \le \phi(m)-1$)使

  $$\overline a=\overline g^i, 即a\equiv g^i(mod\ m)$$

  则称i为a(模m)的指标(index), 或指数, 或对数, 常记

  $$i=ind_ga(mod\ \phi(m)) 或 ind\ a$$

  注意$\overline{g} $的阶为$\phi(m) $, 故$\overline a = \overline g^j = \overline g^{i+k\phi(m)}$

  ind与对数相仿

  (1)$ind_g(ab)=ind_ga+ind_gb$

  (2)$indg(a^r)=rind_ga$

• 定义2 设(a, m) = 1, 若同余式

  $$x^n\equiv a(mod\ m)$$

  有整数解x, 则称a为模m的n次剩余, 否则称为n次非剩余

  简言之, n次剩余就是n次幂

• 定理1 (P79)模m有原根g, (a, m)=1, 考虑$$x^n\equiv a(mod\ m)$$

  (1)a是模m的n次剩余

  $\Leftrightarrow (n, \phi(m)) | ind a$

  $\Leftrightarrow a^{\frac{\phi(m) }{(n, \phi(m))}}\ \equiv 1 \ mod(m)$

  (2)n次剩余a的个数为$\phi(m)/d$, 特别的, m>2时

  $$x^2\equiv a\ (modm)有解(a为2次剩余)$$

  $\Leftrightarrow 2 | ind a$

  $\Leftrightarrow a^{\frac{\phi(m) }{2}}\ \equiv 1 \ mod(m)$

  此时$x^2\equiv a\ (modm)$解数为2. 二次剩余a的个数为$\frac{\phi(m) }{2}$

3.5 高次同余式

第四章 二次互反律

4.1 二次剩余

• 设整数a与m互素，若$x^2\equiv a(mod\ m)$有解, 则称a是模m的二次剩余, 否则称为非剩余.

• 引理1

  (1)设a为奇数, $s\ge 3$, 则a为模$2^s$的二次剩余当且仅当$$a\equiv 1(mod\ 8)$$

  即$$x^2\equiv a(mod\ 2^s)$$有解的充要条件为a模8余1

  (2)a为模$p^s$的二次剩余, 其中$s\ge 1$当且仅当$$a^{(p-1)/2}\equiv 1(mod\ p)$$

• 定理1

  设$m=2^s p_1^{s_1}\cdots p_t^{s_t}$为素因子分解, (a, m)=1, 则$x^2 \equiv a(mod\ m)$有解当且仅当如下条件成立:

  (1)若$s\ge 3$, 则$a\equiv 1(mod\ 8)$. 若s=2, 则$a\equiv 1(mod 4)$

  (2)$a^{(p_i-1)/2}\equiv 1(mod\ p_i)$, i=1,…,t.

• 定义1 设p为奇素数, Legendre(勒让德)符号定义如下:
  $$
  (\frac a p)= {\begin{cases} 1, \quad 若a是二次剩余(mod\ p)\\-1,\ 若a是二次非剩余(mod\ p)\\0, \quad 若a\equiv 0(mod\ p)\end{cases}}
  $$

• 引理2

  (1)(Euler判则)$(\frac a p)\equiv a^{(p-1)/2}(mod\ p)$

  (2)$$(\frac {-1} p) \equiv (-1)^{(p-1)/2}=\begin{cases} 1,\quad 若p\equiv1(mod\ 4)\\-1,\ 若p\equiv 3(mod\ 4) \end{cases}$$

  而且当$p\equiv 1(mod\ 4)$时, $((\frac {p-1} 2)!)^2\equiv -1(mod\ p)$

• 系1

  (1)$(\frac {ab} p) = (\frac a p)(\frac b p)$

  (2)若a模p等于b, 则$(\frac a p)=(\frac b p)$

  (3)模p的二次剩余和非剩余个数相等, 均为$(p-1)/2$, 故模p的二次剩余恰为

  $$1^2, 2^2,\cdots, (\frac {p-1} 2)^2$$

  (4)剩余与非剩余之间的乘法关系如1和-1一样, 剩余为1, 非剩余为-1

• 引理3(Gauss引理) P96

  设奇素数$p\not |a,v $是$\lbrace a, 2a, \cdots, a(p-1)/2\rbrace$的模p绝对最小剩余中负数的个数, 则 $$(\frac a p)=(-1)^v$$

• 引理4

  $$(\frac 2 p)=(-1)^{(p^2-1)/8}=\begin{cases} 1,\quad 若p\equiv \pm 1(mod\ 8)\\-1,\ 若p\equiv \pm 3(mod\ 8) \end{cases}$$

4.2 二次互反律

• 定理1 (二次互反律) 设p,q为奇素数, 则

  $$(\frac q p) = (\frac p q)(-1)^{\frac {p-1} 2 \frac {q-1} 2}$$(即p,q之一为4k+1型时, 取正号),

  $$(\frac {-1} p) = (-1)^{\frac {p-1} 2 }$$(即p为4k+1型时, 取正好),

  $$(\frac {2} p) = (-1)^{\frac {p^2-1} 8 }$$(即$p=8k\pm 1$时, 取正号)

  二次互反律的威力在于, 可定出a为模p二次剩余的所有p

• 定义1

  设$b=p_1p_2\cdots p_t$为正的奇数, $p_i$(i=1,…,t)为奇素数(不必互异), 对任意整数a, Jacobi(雅可比)符号可定为

  $$(\frac a b)=(\frac a {p_1p_2\cdots p_t})=(\frac a {p_1})(\frac a {p_2})\cdots (\frac a {p_t})$$.

  注意$(\frac a b)=1$并不意味着a为模b的二次剩余,

  但若a为模b的二次剩余, 则必定$(\frac a b)=1$

  Jacobi符号性质

  (1)$(\frac {a_1a_2} b)=(\frac {a_1} b)(\frac {a_2} b)$

  (2)$(\frac b {a_1a_2})=(\frac b {a_1})(\frac b {a_2})$

  (3)若$a_1 \equiv a_2(mod\ b)$, 则$(\frac {a_1} b)=(\frac {a_2} b)$

• 对Jacobi符号互反律也成立

• 引理2

  (1)$\frac {s_1\cdots s_r-1} 2 = \frac{s_1-1}2+\cdots+\frac{s_r-1}2$

  (2)$\frac {s_1^2\cdots s_r^2-1} 8 = \frac{s_1^2-1}8+\cdots+\frac{s_r^2-1}8$

• 定理4

  若a不是完全平方数， 则存在无限多个素数p使得$(a/p)=-1$.

  即若a时任意素数的二次剩余, 则a为平方数.

Maple命令

fermat

求第n个费马数:

$$2^{2^n} + 1$$

使用方法

• fermat(n)

• fermat(n, w)

legendre

The legendre(a, p) function computes the Legendre symbol “L(a/p)” of a and p, which is defined to be “1”. If a is a quadratic residue “mod p”

求勒让德符号

使用方法

• legendre(a, p)

mlog

The function mlog computes the discrete logarithm (also called the index) of x to the base a (mod n). It finds an integer y such that

$$a^y = x \ mod n$$
if possible, otherwise it returns FAIL.

使用方法

• mlog(x, a, n)

order

求元素的阶

$n^i = 1 \ mod m$

使用方法

• order(n, m)

phi

求欧拉函数$\phi(n)$

使用方法

• phi(n)

primroot

求n 大于g最小的原根

使用方法

• primroot(g,n)
• primroot(n)

quadres

判断二次剩余(a/b) jacobi符号?

效果应该同勒让德符号 不过勒让德需要p

使用方法

• quadres(a, b)

  isolve

  方程整数求解

  使用方法

  • isolve(方程组，常量)

    例如isolve(3x - 4y = 7, a)

    得{x = 5 + 4a, y = 2 + 3a}

  msolve

  在整数模m的空间下求解方程组

  使用方法

  • msolve(eqns, vars, m)

    例如msolve({7x+y=2,3x=4y=1},19)

    得{x = 15, y = 11}

  chrem

  If u is a list of integers, chrem(u, m) computes the unique positive integer a such that
  “a mod m1 = u1, a mod m2 = u2, () .. (), a mod mn = un” and “0 <= a and a < M”

  使用方法

  • chrem(u, m)

后记

2021/12/17

再次使用通宵学战术 考完再睡

记录真费时间 这种事应该边学边做

期末才开始记录还是太不明智了 看书做题更香