TOC

广义欧几里得除法

a = q * b + c, 0 <= c < b; 则(a, b) = (b, c),可以用来计算最大公因数

def gcd(a, b):  # a <= b  
  if a * b == 0:  
      return 0  
  r = b // a  
  c = b % a  
  while c != 0:  
      # print("%d = %d * %d + %d"%(b, r, a, c))  
      b = a  
      a = c  
      r = b // a  
      c = b % a  
  return a  

算数基本定理

任意整数n > 1都可以表示成素数的乘积, 且在不考虑乘积顺序的情况下,该表达式唯一。

欧拉函数

设m是一个正整数,则m个整数1,2,3…m中,与m互素的整数个数,计做$\varphi$,通常叫做欧拉函数。

欧拉函数性质:
假设m, n是互素的两个正整数,则
$\varphi(m*n) = \varphi(m) * \varphi(n)$

欧拉定理

(Euler) 设m是大于1的整数,如果a是满足$(a, m) = 1$的整数,则
$a^{\varphi(m)} \equiv 1(mod;m)$
但是使得$a^e \equiv 1(mod;m)$成立的最小整数e不一定是$\varphi(m)$, 只有$e \leq \varphi(m)$,如果取等号则a称为m的原根。

费马小定理

(Fermat) 设p是一个素数,则对任意整数a,有:
$a^p\equiv a(mod;p)$

Wilson定理

(Wilson) 设p是一个素数,则
$(p-1)! \equiv -1 (mod;p)$

同余式

设m是一个正整数,m不是a的因子,则一次同余式$ax \equiv 1(mod;m)$有解的充分必要条件是 $(a, m) =1$

中国剩余定理

设$m_1, m_2, m_3,…,m_k$是k个两两互素的正整数,则对任意的整数$b_1, b_2, …, b_n$同余式组
$x \equiv b_1(mod;m_1)$

$x \equiv b_k(mod;m_k)$
一定有解,且解唯一。

# sage  
def CRT(mi, ai):  
  assert(isinstance(mi, list) and isinstance(ai, list))  
  assert(reduce(gcd, mi) == 1) # mi之间互素  
  M = reduce(lambda x, y: x * y, mi)  
  ai_ti_Mi = [a * (M // m) * inverse_mod(M // m, m) for (m, a) in zip(mi, ai)]  
  return reduce(lambda x, y: x + y, ai_ti_Mi) % M  
# sage中也有crt函数  
# sage: x = crt(2, 1, 3, 5); x  
# 11  

平方剩余

设m是正整数,若同余式
$x^2 \equiv a (mod;m),:(a, m) = 1$
有解,则a叫做m的平方剩余(或二次剩余);否则,a叫做模m的平方非剩余。

欧拉判别条件

设p是奇素数,(a, p) = 1, 则
(i) a是模p的平方剩余的充分必要条件是
$a^{\frac{p-1} 2} \equiv 1(mod;p)$
(ii) a是模p的平方非剩余的充分必要条件是
$a^{\frac{p-1} 2} \equiv -1(mod;p)$
由这个判别推出勒让得符号和雅克比符号

设G是一个具有结合法的非空集合,G叫做一个群,如果G中的结合法满足以下三个条件,
(i) 结合律:即对任意的$a, b, c \in G$,都有
$(ab)c=a(bc)$
(ii) 单位元:即存在一个元素$e \in G$,使得对任意$a \in G$,都有
$ae=ea=a$
(iii) 可逆性:即对任意的$a \in G$,都存在$a' \in G$,使得
$aa' = a’a = e$
特别的,当G的结合法写作乘法时,G叫做乘群,当G的结合法写作加法时,G叫做加群。群G中元素的个数叫做群G的阶。

同态和同构

设G, G’都是群,f是G到G’的一个映射,如果对任意的$a, b \in G$, 都有
$f(a, b) = f(a) f(b)$
则f叫做G到G’的一个同态,如果f是一一对应的,则称f为同构。

设R是具有两种结合法(通常表示为加法和乘法)的非空集合,如果以下条件成立:
(i) R对于加法构成一个交换群
(ii) (结合律) 对任意的$a,b,c \in R$,有$(ab)c=a(bc)$
(iii) (分配律) 对任意的$a, b, c \in R$,有
$(a + b)c = ac + bc$和$a(b + c) = ab + ac$
则R称为环。(即加法构成交换群,乘法满足结合率,加法乘法满足分配律)
(iv) 对任意的$a,b,c \in R$,有$ab = ba$,则R叫做交换环
(v) 对任意的$a \in R$,有$a 1_R=1_Ra=a$,则R叫做有单位元环。

称交换环K为一个域,如果K中有单位元,且每个非零元都是可逆元,即K对于加法构成一个交换群,$K* = K \ {0}$对于乘法构成一个交换群。域$F_p$

多项式环

设R为整环,x为变量,则R上形为
$a_nx^n + … + a_1x + a_0,::a_i \in R$
的元素称为R上的多项式。
设$f(x) = a_nx^n + … + a_1x + a_0,::a_i \neq R$是整环R上的多项式,如果再定义加法和乘法则可以生成整环R[x]
注意定义多项式环需要声明是定义在哪个环或者域上的。
$Z[x]$:定义在整数环上的多项式环
$F_2[x]$:定义在域$F_2$上的多项式环
GF(2)到GF(2^8)的扩张: https://blog.openacid.com/storage/ec-2/