算法灵魂源自数学--数论数学笔记
2022/5/30 1:21:05
本文主要是介绍算法灵魂源自数学--数论数学笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数论数学笔记
- 第一章:整数的可除性
- 整除的概念及欧几里得除法
- 整除定义
- 素数与合数的定义
- 不完全商和余数定义
- 最大公因数与广义欧几里得除法
- 最大公因数
- 最大公因数性质
- 整除的进一步性质及最小公倍数
- 最小公倍数
- 素数分解
- 素数定理
- 整除的概念及欧几里得除法
- 同余式
- 同余的概论和及基本性质
- 同余定义
- 剩余类和完全剩余系
- 剩余系与剩余
- 欧拉函数
- 简化剩余系
- 欧拉定理性质
- \(Euler\)
- \(Fermat\)
- \(Wilson\)
- 同余的概论和及基本性质
- 同余式
- 基本概念及一次同余式
- 同余式的基本概念
- 逆元
- 中国剩余定理
- 高次同余式的解数及解法
- 高次同余式的解数
- 高次同余式的提升
- 基本概念及一次同余式
- 二次同余式与平方剩余
- 一般二次同余式
- 平方剩余
- 模为奇素数的平方剩余与平方非剩余
- 欧拉判别条件
- 勒让得符号
- 二次互反律
- 雅可比符号
- 模平方根
- 一般二次同余式
- 原根与指标
- 指数
- 指数的基本性质
- 大指数构造
- 原根
- 指数
- 素数检验
- 伪素数
- 伪素数 \(Fermat\) 素性检验
- \(Carmicheal\) 数
- \(Euler\) 伪素数
- Solovay-Stassen 素性检验
- 强伪素数
- 伪素数
- 连分数
- 简单连分数
第一章:整数的可除性
整除的概念及欧几里得除法
整除定义
设 \(a,b\) 是任意两个整数,其中 \(b \not ={0}.\) 如果存在一个整数 \(q\) 使得等式
\(\qquad a=q \cdot b\)
成立,就称 \(b\) 整除 \(a\),记作 \(b \mid a\),
- 把 \(b\) 叫做 \(a\) 的因数,
- 把 \(a\) 称为 \(b\) 的倍数
否则,就称 \(b\) 不能整除 \(a\),记作 \(b \nmid a\)
定理
-
整除具有传递性
\(设a,b,c \not ={0} 是三个整数,有 \quad{{b \mid a, c \mid b}\Rightarrow{c \mid a}}\)
-
在加法、减法运算,整除的性质是保持的
\(设a,b,c \not ={0} 是三个整数,有 \quad{{c \mid a, c \mid b}\Rightarrow{c \mid a \pm b}}\)
-
在线性组合中,整除的性质是保持的
\(设a,b,c \not ={0} 是三个整数. 若 c \mid a, c \mid b,则对任意整数 s,t, \\ 有c \mid (s \cdot a + t \cdot b).\)
推广:
\(设整数 c \not ={0}. 若整数 a_1,...,a_n 都是整数 c 的倍数,则对任意 n 个整数 s_1,...,s_n,整数 \\ \qquad\qquad\qquad\qquad\qquad s_1a_1+...+s_na_n \\ 是c的倍数.\)
\(设a,b都是非零整数. 若a \mid b, b \mid a, 则 a = \pm b.\)
素数与合数的定义
\(设整数n \not ={0, \pm 1}.如果除了显然因数 \pm 1 和 \pm n 外,n没有其他因数,那么称 n 为素数【质数】,否则叫做合数\)
如果没有特殊声明,素数一般是指正整数,通常写作 \(p\)
定理
-
每个合数必定有素因子
\(设n是一个正和数,p是n的一个大于1的最小正因数,则p一定是素数,且p一定是素数,且 p \leqslant \sqrt{n}\)
-
厄拉托塞师 【 \(Eratoshenes\) 】 筛法依据
\(设 n 是正整数. 如果对所有的素数 p \sqrt{n},都有 p \nmid n,则 n 一定是素数.\)
-
素数有无穷多个.
-
欧几里得除法
\(设 a,b 是两个整数,其中 b > 0,则存在唯一的整数 q,r 使得\)
\(\qquad a=q \cdot b + r, \quad 0 \leqslant r < b\)
不完全商和余数定义
在 欧几里得除法 的公式中 \(q\) 叫做 \(a\) 被 \(b\) 除所得的 不完全商,\(r\) 叫做 \(a\) 被 \(b\) 除所得的余数
推理:在欧几里得除法的条件下,\(b \mid a\) 的充要条件是 \(a\) 被 \(b\) 除所得的余数 \(r=0.\)
引入一个数学符号
\(设 x 是实数. 称 x 的整数部分为小于或等于x的最大整数,记成 [x],此时,有\)
\(\qquad [x] \leqslant x < [x] + 1\)
则在欧几里得除法中的不完全商 \(q\) 可以写作 \(q=[\dfrac{a}{b}]\),余数 \(r\) 可以写为 \(r=a-[\dfrac{a}{b}].\)
素数的平凡判别:
对于给定正整数 \(N\),设不大于 \(\sqrt{N}\) 的所有素数为 \(p_1,p_2,\cdots,p_s\). 如果 \(N\) 被所有 \(p_i\) 除的余数都不为零,即 \(p_i \nmid n,\; 1 \leqslant i \leqslant s\),则 \(N\) 是素数
定理:
-
运用欧几里得除法时,余数取其它形式
\(设a,b是两个整数,其中 b > 0. 则对任意的整数 c,存在唯一的整数 q,r 使\)
\(\qquad a = a \cdot b + r,\quad c \leqslant r < b+c\)
最大公因数与广义欧几里得除法
最大公因数
\(设 a_1,...,a_n 是 n(n \geqslant 2) 个整数. \\ 若整数 d 是它们中每一个数的因数,则 d 就是a_1,...,a_n的一个公因数.\)
\(\quad d 是 a_1,...,a_n 的一个公因数的数学表达式为\)
\(\qquad\quad d \mid a_1,...,d\mid a_n\)
\(如果整数a_1,...,a_n不全为零,那么整数a_1,...,a_n 的所有公因数中最大的一个公因数称作\) 最大公因数 $ ,记住 (a_1,...,a_n)\(   \)当(a_1,...,a_n)=1,称 a_1,...,a_n $ 互素或互质
定理
- \(设a,b是两个整数,则有 (0,b)=b\)
广义欧几里得除法
\(设a,b是任意两个正整数,记r_{-2}=a,r_{-b}=b,反复运用欧几里得除法,必然存在 n 使得 r_{n+1}=0\)
- \(设a,b是任意两个正整数,则(a,b)=r_n,并且 a>b 时,计算(a,b)的时间为 \;O(\log a \log^2 b).\)
\(B \hat{e} zout\) 等式
\(\qquad 设a,b是任意两个正整数,则存在s,t使得\)
\(\qquad\qquad s \cdot a + t \cdot b = (a,b)\)
-
\(整数 a,b 互素的充分必要条件是存在整数 s,t使得\)
\(\qquad\qquad s a + t b = 1\)
最大公因数性质
\(设a,b是任意两个不全为零的整数,d是正整数,则d是整数a,b的最大公因数的充要条件是\)
- \(d \mid a, d \mid b\)
- \(若 e \mid a, e \mid b, 则 e \mid d\)
互素整数构造 \(\Big(\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}\Big) = 1\)
\(设 a,b 和 u,v 都是不全为零的整数,如果\)
\(\qquad\qquad a=q \cdot u + r \cdot v, \; b = s \cdot u + t \cdot v\)
\(其中q,r,s,t是整数,且q \cdot t - r \cdot v = 1,则 (a,b)=(u,v)\)
整除的进一步性质及最小公倍数
最小公倍数
设 \(a_1,...,a_n\) 是 \(n\) 个整数. 若 \(D\) 是这 \(n\) 个数的倍数,则 \(D\) 叫做这 \(n\) 个数的公倍数.
在 \(a_1,...,a_n\) 的公倍数中最小正整数叫做最小公倍数,记作 \([a_1,...,a_n]\)
定理
-
\(设a,b是两个整数,且 (a,b) = 1. 则\)
- \(若 a \mid D, b \mid D, 则a \cdot b \mid D\)
- \([a,b]=a \mid b\)
最小公倍数 与 最大公因数
\(\qquad 设 a,b 是两个正整数,则\)
\(\qquad\quad 若 a\mid D,b\mid D,则 [a,b] \mid D.\)
\(\qquad\quad [a,b]=\dfrac{a\cdot b}{(a,b)}\)
素数分解
\(给定正合数 n > 1. 如果存在整数 a,b 使得\)
\(\qquad n\mid a^2 - b^2, \quad n\nmid a - b, \quad n\nmid a + b\)
\(\;\; 则 (n,a-b) 和 (n,a+b) 都是 n 的真因数\)
-
标准分解式
\(任意整数 n > 1 可以唯一地表示成\)
\(\qquad n=p^{\alpha_1}_1 \cdots p^{\alpha_s}_s , \quad \alpha_i > 0,\;i=1,...,s\)
\(其中 p_i < p_j (i < j)是素数\)
-
因数个数
\(设正整数 n 有因数分解式\)
\(\qquad n=p^{\alpha_1}_1 \cdots p^{\alpha_s}_s , \quad \alpha_i > 0,\;i=1,...,s\)
\(则n的因数数量\)
\(\qquad d(n)=(1+\alpha_1)\cdots(1+\alpha_s)\)
-
最小公因数与最大公倍数
\(设 a,b 是两个正整数,且都因式分解\)
\(\qquad n=p^{\alpha_1}_1 \cdots p^{\alpha_s}_s , \quad \alpha_i > 0,\;i=1,...,s\)
\(\qquad n=p^{\beta_1}_1 \cdots p^{\beta_s}_s , \quad \beta_i > 0,\;i=1,...,s\)
\(则\)
\((a,b)=p^{\gamma_1}_1 \cdots p^{\gamma_s}_s , \quad \gamma_i =\min(\alpha_i,\;\beta_i),\;i=1,...,s\)
\([a,b]=p^{\delta_1}_1 \cdots p^{\delta_s}_s , \quad \delta_i =\max(\alpha_i,\;\beta_i),\;i=1,...,s\)
素数定理
\(\lim\limits_{x \to \infty}\dfrac{\pi(x)}{\dfrac{x}{\ln x}}=1\)
同余式
同余的概论和及基本性质
同余定义
\(给定一个正整数 m,两个整数 a,b叫做模 m 同余\)
\(如果 a-b 被 m 整除,或 m \mid a - b,就记作 a \equiv (\mod m). 否则,叫做模 m 不同余,记住 a \not \equiv b (\mod m)\)
同余性质
-
\(设m是一个正整数,设d\cdot a\equiv d\cdot b (\mod m). 如果(d,m)=1,则\)
\(\qquad a \equiv b (\mod m)\)
-
\(设 m 是一个正整数,设 a \equiv (\mod m),\;d > 0,则\)
\(\qquad d \cdot a \equiv d \cdot b (\mod d \cdot m)\)
-
\(设 m 是一个正整数,设 a \equiv b (\mod m). 如果整数 d \mid (a,b,m)\)
\(\qquad \dfrac{a}{d} \equiv \dfrac{b}{d} (\mod \dfrac{m}{d})\)
-
\(设 a \equiv b (\mod m), 则\)
\(\qquad(a,m)=(b,m)\)
剩余类和完全剩余系
\(设m是一个正整数,则\)
- \(任意整数必包含在一个 C_r 中,0 \leqslant r \leqslant m -1;\)
- \(C_a = C_b的充分必要条件是 a \equiv b (\mod m)\)
- \(C_a与C_b的交集为空集的充分必要条件是 a \not \equiv b (\mod m)\)
剩余系与剩余
\(C_a 叫做模 m 的 a 的剩余类. 一个剩余系中的任意数叫做该类的\) 剩余 \(或\) 代表元. \(若r_0,r_1,\cdot,C_{m-1}是 m 个整数,并且其中任何两个数都不在一个剩余类里,则 r_0,\cdot,r_{m-1}叫做模m 的\) 完全剩余系
欧拉函数
\(设m是一个正整数,则m 个整数 1,\cdot,m-1,m中与m 互素的整数的个数,记作 \varphi(m),通常叫\) 做欧拉函数
定理
-
\(对于素数幂 m = p^\alpha,有\)
\(\qquad \varphi(m)=p^\alpha - p^{\alpha-1}=m \prod\limits_{p \mid m}(1 - \dfrac{1}{p})\)
简化剩余系
\(一个模m的剩余系叫做\) 简化剩余类, \(如果该类中存在一个与m 互素的剩余. 这时简化剩余类中的剩余叫做\) 简化剩余
\(设m 是一个正整数. 在模m 的所有不同简化剩余类中,从每个类任取一个数组成的整数的集合,叫做模m 的一个\) 简化剩余系
\(元素个数为\; \varphi(m)\)
定理
-
\(设m是一个正整数,a 是满足(a,m)=1的整数,则存在唯一的整数a',1 \leqslant a' < m使得\)
\(\qquad a \cdot a' \equiv 1 (\mod m)\)
欧拉定理性质
\(设正整数 m 的标准因数分解式为\)
\(\qquad m=\prod\limits_{p \mid m}p^\alpha=p^{\alpha_1}_1 \cdots p^{\alpha_s}_k,\)
\(\qquad \varphi(m)=p^\alpha - p^{\alpha-1}=m \prod\limits_{p \mid m}(1 - \dfrac{1}{p})=m(1 - \dfrac{1}{p_1})\cdots(1 - \dfrac{1}{p_k})\)
\(Euler\)
\(设 m 是大于1的整数. 如果 a 是满足 (a,m)=1 的整数, 则\)
\(\qquad a^{\varphi(m)} \equiv 1 (\mod m)\)
\(Fermat\)
\(设p是一个素数,则对任意整数a,有\)
\(\qquad a^p \equiv a (\mod p)\)
\(Wilson\)
\(设p是一个素数,则\)
\(\qquad (p-1)!\equiv -1(\mod p)\)
同余式
基本概念及一次同余式
同余式的基本概念
\(设m是一个正整数,f(x)为多项式\)
\(\qquad f(x)= a_nx^n + \cdots + a_1x + a_0\)
\(其中a_i是整数,则\)
\(\qquad f(x) \equiv 0 (\mod m)\)
\(称之为\) 同余式 \(.若 a_n \not \equiv 0 (\mod m), 则 n 叫做 f(x) 的\) 次数 $,记作 \deg f. 此时称式子为模m 的n $ 次同余式
定理
-
$设 m 是一个正整数,a 是满足 m \nmid{a} 的整数,则一次同余式 $
\(\qquad ax \equiv 1 (\mod m)\)
\(有解的充分必要条件是\)
\(\qquad (a,m)=1. 且当同余式有解,其解唯一\)
逆元
\(设 m 是一个正整数,a是一个整数. 如果存在整数a'使得\)
\(\qquad a \cdot a' \equiv a' \cdot a \equiv 1 (\mod m)\)
\(成立,则a 称为模m的\) 可逆元
\(a'称为a的模m\) 逆元
定理
-
\(设m是一个正整数,则\)
\(\qquad整数a是模m简化剩余 \iff 整数a是模m逆元\)
-
通常的一次同余式求解
\(设m是一个正整数,a 是满足 m \nmid{a} 的整数,则一次同余式\)
\(\qquad ax \equiv 1 (\mod m)\)
\(有解的充要条件是 (a,m) \mid b,解为\)
\(x \equiv \dfrac{b}{(a,m)} \cdot \bigg( \Big( \dfrac{a}{(a,m)} \Big)^{-1} \Big( \mod \dfrac{m}{(a,m)} \Big) \bigg) + t \cdot \dfrac{m}{(a,m)} (\mod m), \qquad t= 0,1,\cdots,(a,m)-1\)
中国剩余定理
\(设 m_1,\cdots,m_k是k个两两互素的正整数,则对任意整数 b_1, \cdots,b_k, 同余式组\)
\( \qquad \begin{cases} x \equiv b_1 (\mod m_1) \\ \qquad\vdots \\ x \equiv b_k (\mod m_k) \end{cases} \)
\(有唯一解\)
\(令\)
\(\qquad m = m_1\cdots m_k, \quad m = m_i \cdots M_i, i = 1,\cdots,k\)
\(则解表示为\)
\(\qquad x \equiv b_1\cdot M'_1 \cdots M_1 + b_2\cdot M'_2 \cdots M_2 + \cdots + b_k\cdot M'_k \cdots M_k (\mod m)\)
高次同余式的解数及解法
高次同余式的解数
\(设 m_1,\cdots,m_k是k个两两互素的正整数, m = m_1\cdots m_k,同余式\)
\(\qquad f(x) \equiv 0 (\mod m)\)
\(与同余式组\)
\( \qquad \begin{cases} f(x) \equiv 0 (\mod m_1) \\ \qquad\vdots \\ f(x) \equiv 0 (\mod m_k) \end{cases} \)
\(等价. 如果用 T_i 表示同余式\)
\(\qquad f(x) \equiv 0 (\mod m_i)\)
\(的解数 i = 1, \cdots, k, T 表示同余式的解数,则\)
\(\qquad T = T_1 \cdots T_k\)
高次同余式的提升
\(设 x \equiv x_1(\mod p) 是同余式\)
\(\qquad f(x) \equiv 0 (\mod p)\)
\(的一个解,且\)
\(\qquad (f'(x),p)=1\)
\(则同余式有解为\)
$\qquad x \equiv x_\alpha(\mod p^\alpha) $
\(其中x_\alpha 由下面的关系式递归得出\)
\(\qquad x_i \equiv x_{i-1} + t_{i-1} \cdot p^{i-1} (\mod p^i), \quad i = 2,\cdots ,\alpha\)
\(\qquad t_{i-1} \equiv \dfrac{-f(x_{i-1})}{p^{i-1}} \cdot (f'(x_1)^{-1} (\mod p)) (\mod p) \quad i = 2,\cdots ,\alpha\)
二次同余式与平方剩余
一般二次同余式
平方剩余
\(设m是正整数. 若同余式\)
\(\qquad x^2 \equiv a (\mod m), \quad (a,m)=1\)
\(有解,则a称为模m的\) 平方剩余【二次剩余】 \(; 否则称为\) 平方非剩余【二次非剩余】
模为奇素数的平方剩余与平方非剩余
欧拉判别条件
\(设 p 是奇素数,(a,m)=1 ,则\)
$\qquad a是模p的平方剩余 \iff a^{\frac{p-1}{2}} \equiv 1 (\mod p) \( \)\qquad a是模p的平方非剩余 \iff a^{\frac{p-1}{2}} \equiv -1 (\mod p) $
\(并且,当a是模p的平方剩余,恰有二解\)
推论
\(设 p 是奇素数,(a_1,m)=1 ,(a_2,m)=1 则\)
- \(如果a_1,a_2是模p的平方剩余 \implies a_1 \cdot a_2是模p的平方剩余\)
- \(如果a_1,a_2是模p的平方非剩余 \implies a_1 \cdot a_2是模p的平方剩余\)
- \(如果a_1是模p的平方剩余,a_2是模p的平方非剩余 \implies a_1 \cdot a_2是模p的平方非剩余\)
勒让得符号
\(设p 是素数,定义 Legendre 符号\)\(\qquad\Big(\dfrac{a}{p}\Big)\begin{cases} 1,\quad 若a是模p的平方剩余;\\ -1,\quad 若a是模p的平方非剩余;\\ 0, \quad 若 p \mid a \end{cases}\)
定理
-
欧拉判别法则
\(设 p 是奇素数,则对任意整数a,\)\(\Big(\dfrac{a}{p}\Big) \equiv a^{\frac{p-1}{2}} (\mod p)\)
-
\(设 p 是奇素数,则\)
\(周期性 \Big(\dfrac{a + p}{p}\Big) = \Big(\dfrac{a}{p}\Big)\)
\(完全可乘性 \Big(\dfrac{a \cdot b}{p}\Big) = \Big(\dfrac{a}{p}\Big)\Big(\dfrac{b}{p}\Big)\)
\(设(a,p)=1,则 \Big(\dfrac{a^2}{p}\Big) = 1\)
高斯引理
\(设 p 是奇素数,整数a,(a,p)=1,如果整数\)
\(\qquad a\cdot1,a\cdot2,\cdots,a\cdot \dfrac{p-1}{2}\)
\(中模p的最小正剩余大于\cfrac{p}{2}的个数是m,则\)
\(\qquad \Big(\dfrac{a}{p}\Big) = (-1)^m\)
二次互反律
\(若 p,q 是互素奇素数,则\)
\(\qquad \Big(\dfrac{q}{p}\Big) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} \Big(\dfrac{p}{q}\Big)\)
雅可比符号
\(设 m = p_1 \cdots p_r 是奇素数 p_i的乘积. 对任意整数 a,定义 Jacobi 符号\)
\(\qquad \Big(\dfrac{a}{m}\Big) = \Big(\dfrac{a}{p_1}\Big)\cdots \Big(\dfrac{q}{p_r}\Big)\)
模平方根
-
模 p 平方根
\(设p 是形为 4k + 3 的素数,如果同余式\)
\(\qquad x^2 \equiv a (\mod p)\)
\(有解,则其解是\)
\(\qquad x \equiv \pm a^{\frac{p+1}{4}} (\mod p)\)
-
模 m 平方根
\(m是合数的二次同余式\)
\(\qquad x^2 \equiv a (\mod m),\quad (a.m)=1\)
\(当 m = 2^\delta p^{\alpha_1}_1 \cdots p^{\alpha_k}_k 时 同余式等价于\)
\(\begin{cases} \quad x^2 \equiv a (\mod 2^\delta) \\ \quad x^2 \equiv a (\mod p^{\alpha_1}_1) \\ \qquad \vdots \\ \quad x^2 \equiv a (\mod p^{\alpha_k}_k) \end{cases}\)
\(设 p 是奇素数,则同余式 \; x^2 \equiv a (\mod p^{\alpha}),\quad (a,p)=1,\;\alpha>0有解 \iff a是模p的平方剩余\)
\(解数为2\)
原根与指标
指数
\(m > 1是整数,a 是与m 互素的正整数,则\)
\(\qquad a^e \equiv 1 (\mod m)\)
\(成立的最小正整数e称为 a 对模m 的\) 指数,$记作 ord_m(a) \( \)如果 a 对模m 的指数是 \varphi(m),则 a 叫做模m 的$ 原根
指数的基本性质
\(m > 1是整数,a 是与m 互素的正整数,则整数d使得\)
\(\qquad a^d \equiv 1 (\mod m) \iff ord_m(a) \mid d\)
-
$若 b \equiv a (\mod m),则 ord_m(a) = ord_m(a) $
-
\(设a^{-1} 使得 ^{-1} \cdot a \equiv 1 (\mod m),则 ord_m(a^{-1}) = ord_m(a)\)
-
\(a^d \equiv a^k (\mod m) \iff d \equiv k (\mod ord_m(a))\)
-
\(ord_m(a^d) = \dfrac{ord_m(a)}{(d,ord_m(a))}\)
大指数构造
\(m > 1是整数,a,b 是与m 互素的正整数,如果(ord_m(a),ord_m(b)) = 1,则\)
\(\qquad ord_m(a \cdot b) = ord_m(a) \cdot ord_m(b)\)
\(设 m,n 都是大于 1 的整数,a 是与m 互素的正整数,则\)
- \(若 n \mid m,则 ord_n(a) \mid ord_m(a)\)
- \(若 (m,n)=1,则\; ord_{mn}(a) = [ord_m(a),ord_n(a)]\)
原根
-
\(设p 是奇素数,则模p的原根存在,且有\varphi(p-1)个原根,其中 \varphi 为欧拉函数\)
-
\(设p 是奇素数,如果整数g是模p原根,则有\)
\(\qquad g^{p-1} \not \equiv 1 (\mod p^2) \quad or \quad (g+p)^{p-1} \not \equiv 1 (\mod p^2)\)
素数检验
伪素数
伪素数 \(Fermat\) 素性检验
\(设 n 是一个奇合数,如果整数 b,(b,n) = 1 使得 同余式\)
\(\qquad b^{n-1} \equiv 1 (\mod n)\)
\(成立,则n 叫做对基 b 的\) 伪素数
\(Fermat\) 素性检验
\(给定奇素数 n \geqslant 3 和安全参数 t\)
- \(随机选取整数b,(b,n) = 1,\quad 2 \leqslant b \leqslant n -2\)
- \(计算 r = b^{n-1} (\mod n)\)
- \(如果 r \not ={1},则 n 是合数\)
- \(上述过程重复 t 次\)
\(Carmicheal\) 数
\(和数 n 称为 Carmicheal 数 ,如果对所有的正整数b,(b,n) = 1,,都有同余式\)
\(\qquad b^{n-1} \equiv 1 (\mod n)\)
\(成立\)
定理
\(设 n 是一个奇合数\)
-
\(如果 n 被一个大于 1 平方数整除,则 n 不是 Carmicheal 数\)
-
\(如果 n = p_1\cdots p_k 是一个无平方数,则\)
\(\qquad n 是 Carmicheal 数 \iff p_i - 1 \mid n -1,\quad 1 \leqslant i \leqslant k\)
\(Euler\) 伪素数
\(设 n 是一个正奇合数,如果整数 b 与 n 互素,满足\)
\(b^{\frac{n-1}{2}} \equiv \Big(\dfrac{b}{n}\Big) (\mod n)\)
\(则 n称为 对于基b的\) \(Euler\) 伪素数
Solovay-Stassen 素性检验
\(给定奇素数 n \geqslant 3 和安全参数 t\)
- \(随机选取整数b,(b,n) = 1,\quad 2 \leqslant b \leqslant n -2\)
- \(计算 r = b^{\frac{n-1}{2}} (\mod n)\)
- \(如果 r \not ={1}以及r \not ={n-1},则 n 是合数\)
- \(计算 Jacobi 符号 s = \Big(\dfrac{b}{n}\Big)\)
- \(如果 r \not ={s},则n 是合数\)
- \(上述过程重复 t 次\)
强伪素数
\(设 n 是一个正奇合数,且有表达式 n-1=2^st,其中t 为奇数. 如果整数 b 与 n 互素,满足\)
\(\qquad b^{t} \equiv 1 (\mod n)\)
\(或者存在一个整数 r ,0 \leqslant r \leqslant s使得\)
\(\qquad b^{2^rt} \equiv -1 (\mod n)\)
\(则 n称为 对于基b的\) 强伪素数
连分数
简单连分数
\(给定一个实数x\)
- \(令 a_0 = [x], x_0 = x - a_0.\qquad 0 \leqslant x_0 < 1\)
- \(如果 x_0 =0则终止,否则令a_1 = \Big[\dfrac{1}{x_0}\Big],x_1 = \dfrac{1}{x_0} - a_1\)
- \(如果 x_1 =0则终止,否则令a_2 = \Big[\dfrac{1}{x_1}\Big],x_2 = \dfrac{1}{x_1} - a_2\)
- \(重复上述步骤,得到 a_k,x_k\)
$ \qquad x =
a_0 + \cfrac{1}{
a_1 + \cfrac{1}{
a_2 + \cfrac{1}{
\ddots + \cfrac{1}{
a_{n-1} + \cfrac{1}{
a_n + \cdots
}
}
}
}
} \
$
\(无限连分数记作[a_0,a_1,a_2, \cdots],有限连分数记作[a_0,a_1,a_2, \cdots, a_{n-1},a_n]\)
\(设k \geqslant 0 (有限简单连分数时,k \leqslant n),将有限连分数\)
\(\qquad [a_0,a_1,a_2, \cdots, a_{n-1},a_n] = \dfrac{P_k}{Q_k}\)
\(叫做简单连分数的第k 个\) 渐近分数,\(将 a_k 叫做它的第 k 个\) 部分商
定理
-
\(设 \alpha 是实数,[a_0,a_1,a_2, \cdots,a_n, \cdots]是其简单连分数,则\)
\(\begin{vmatrix} \alpha - \dfrac{P_k}{Q_k} \end{vmatrix} \leqslant \dfrac{1}{Q^2_k}\)
这篇关于算法灵魂源自数学--数论数学笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-22Java创业学习:初学者的全面指南
- 2024-11-22JAVA创业学习:零基础入门到实战应用教程
- 2024-11-22Java创业学习:从零开始的Java编程入门教程
- 2024-11-22Java对接阿里云智能语音服务学习教程
- 2024-11-22JAVA对接阿里云智能语音服务学习教程
- 2024-11-22Java对接阿里云智能语音服务学习教程
- 2024-11-22Java副业学习:零基础入门到实战项目
- 2024-11-22Java副业学习:零基础入门指南
- 2024-11-22Java微服务学习:入门与实践指南
- 2024-11-22JAVA项目部署学习:从入门到实践