离散数学笔记（三）

数论笔记：

• • 一、整除理论：
  • • • • 整除：
        • 带余除法：
        • 同余：
        • 模m加/乘：
        • 裴蜀定理：
  • 二、素数理论：
  • • • • 素数：
        • 算术基本定理：
        • 伯特兰-切比雪夫定理：
  • 三、同余方程：
  • • • • 线性同余方程：
        • 中国剩余定理：
        • 费马小定理：
        • 欧拉函数：
        • 欧拉定理：

一、整除理论：

• 整除：

  定义：若对任意的整数a和b，a≠0， 若存在整数c使得 b = ac，则称a整除b，记作$a|b$
  性质：
  * 若 a | b, 则 a | bc
  * 若 a | b, 且 b | c, 则 a | c
  * 若 a | b, 且 a | c, 则 a | xb+yc (x,y均为整数)

  ---

• 带余除法：

  令a为整数，d为正整数，则存在唯一的整数q和r，且$0\le r<d$, 满足：a = dq + r, 则称d为除数，a为被除数，q为商，r为余数， 记作 q = a div d, r = a mod d

• 同余：

  设a和b为整数，m为正整数，若 m | (b-a) 则称a与b模m同余，记作$a\equiv b$(mod m)

• 模m加/乘：

  1）模m加： a ± n b = ( a ± b ) m o d n = ( ( a m o d n ) ± ( b m o d n ) ) m o d n a \pm_n b = (a\pm b)\mod{n} = ((a\mod{n})\pm(b\mod{n}))\mod{n} a±n​b=(a±b)modn=((amodn)±(bmodn))modn
  2）模m乘： a ∗ n b = ( a ∗ b ) m o d n = ( ( a m o d n ) ∗ ( b m o d n ) ) m o d n = ( ( a m o d n ) ∗ b ) m o d n a *_n b = (a * b)\mod{n}=((a\mod{n})*(b\mod{n}))\mod{n}=((a\mod{n})*b)\mod{n} a∗n​b=(a∗b)modn=((amodn)∗(bmodn))modn=((amodn)∗b)modn

• 裴蜀定理：

  整数a和b的公约数都可表示为a和b的某种线性组合，特殊地，一定存在$s,t\in Z$, 使得gcd(a,b) = sa + tb；

二、素数理论：

• 素数：

  大于1的正整数p称为素数，当且仅当p不能被除了1和p之外的任何正整数整除；否则，称大于1又不是素数的正整数为合数；

• 算术基本定理：

  每个大于1的正整数都可以唯一地写成一个素数或者若干个素数的乘积，其中素数因子以非递减序出现，即形如： n = p 1 α 1 p 2 α 2 . . . p k α k n = p_1^{\alpha_1} p_2^{\alpha_2}... p_k^{\alpha_k} n=p1α1​​p2α2​​...pkαk​​

• 伯特兰-切比雪夫定理：

  1）若整数n>3, 则至少存在一个质数p，符合 n < p < 2n-2；
  2）若整数n>1, 则至少存在一个质数p，符合 n < p < 2n；

三、同余方程：

• 线性同余方程：

  方程形如：$ax\equiv b$(mod m) 称为线性同余方程，其中a和b为整数，m为正整数；

• 中国剩余定理：

• 费马小定理：

  设正整数a不是素数p的倍数，则：
  1） a p ≡ a a^p \equiv a ap≡a(mod p)；
  2） a p − 1 ≡ 1 a^{p-1} \equiv 1 ap−1≡1(mod p);

• 欧拉函数：

  定义：若n为正整数，则称欧拉函数$\varphi (n)$为比n小且与n互素的正整数个数；
  性质：
  1）$\varphi (p)=p-1,p是素数$
  2）$\varphi (mn)=\varphi (m)\varphi (n)$
  3） ϕ ( n ) = n ∗ Π p ∣ n ( 1 − 1 p ) \phi(n) = n * \Pi_{p | n}(1 - \frac{1}{p}) ϕ(n)=n∗Πp∣n​(1−p1​)

• 欧拉定理：

  若正整数a与n互素，则： a ϕ ( n ) ≡ 1 a^{\phi(n)} \equiv 1 aϕ(n)≡1(mod n)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！