一、整除的概念,欧几里得除法

1、整除的概念

定义1.1:

设a,b是任意两个整数,其中b ≠ 0.如果存在一个整数q使得等式 a = q · b 成立,就称 b 整除 a 或者 a 被 b 整除,记作 b | a,并把b叫做a的因数,把a叫做b的倍数。人们常把q写成 a / b。否则,就称b不能整除a,或者a不能被b整除。

此外,再不会混淆的情况下,乘法a·b简记为ab。

(1)当b遍历整数a的所有因数时,-b也遍历整数a的所有因数。

(2)当b遍历整数a的所有因数时,a/b也遍历整数a的所有因数。

根据定义有:

  • 0是任何非零整数的倍数。
  • 1是任何整数的倍数。
  • 任何非零整数a是其本身的倍数,也是其自身的因数。

定理1.1:

设a,b ≠ 0,c ≠ 0是三个整数。若 b | a,c | b,则c | a。

定理1.2:

设a,b,c ≠ 0是三个整数。若c | a,c | b,则c | a ± b。

定理1.3:

设a,b,c ≠ 0是三个整数。若c | a,c | b,则对任意整数s,t,有c |(s·a+t·b)。

定理1.4:

设整数c ≠ 0。若整数a1,···,an都是整数c的倍数,则对任意n个整数s1,···,sn,整数s1a+ ··· + snan是c的倍数。

定理1.5:

设a,b都是非零整数。若a | b,b | a,则a = ±b。

定义1.2:

设整数n ≠ 0,±1.如果除了显然因数±1和±n外,n没有其他因数,那么n就叫做素数(或质数不可约数),否则,n叫做合数。

定理1.6:

设n是一个正合数,p是n的一个大于1的最小正因数,则p一定是素数,且p≤n1/2

 

2、Eratoshenes筛法

定理1.7:

设n是正整数。若果对所有的素数p ≤ n1/2,都有p不被n整除,则n一定是素数。

应用该定理,可得到一个寻找素数的确定性方法,通常叫做平凡除法或厄拉托塞师筛法。

 

3、欧几里得除法 —— 最小非负余数

定理1.9(欧几里得除法):

设a,b是两个整数,其中b>0,则存在唯一的整数q,r使得a = q·b + r ,0 ≤ r ≤ b 。

定义1.3:

a = q·b + r ,0 ≤ r ≤ b中,q叫做a被b除所得的不完全商,r叫做a被b除所得的余数

定义1.4:

设x是实数,称x的整数部分为小于或等于x的最大整数,记成[x]。

这时,有[x] ≤ x< [x]+1。

 

4、素数的平凡判别

素数的平凡判别:对于给定正整数N,设不大于N1/2的所有素数为p1,p2,,···,ps

如果N被所有pi除的余数都不为零,则N是素数。

 

5、欧几里得除法 —— 一般余数

定理1.10(欧几里得除法):

设a,b是两个整数,其中b>0.则对任意的整数c,存在唯一的整数q,r使得

a = q·b+r,c ≤ r<b+c

 

二、整数的表示

1、b进制

定理2.1:

设b是大于1的正整数,则每个正整数n可唯一地表示成

n = ak-1bk-1 + ak-2bk-2 + ··· + a1b + a0

其中ai是整数,0 ≤ ai ≤ b-1,i = 1,···,k-1,且首项系数ak-1 ≠ 0.

2、计算复杂性

大O符合和小o符号

大O符号:

设f(n)和g(n)都是正整数n的正值函数,如果存在一个正常数C,使得对任意的正整数n都有f(n) ≤ Cg(n),

就称g(n)是f(n)的界,记作f(n) = O(g(n)),简记为f = O(g)。

小o符号:

设f(n)和g(n)都是正整数n的正值函数,如果对任意小的正数€,存在一个正整数N0,使得对任意的正整数n > N0都有f(n) < €g(n),

就称g(n)是比f(n)高阶的无穷量,记作f(n) = o(g(n)),简记为f = o(g)。

 

三、最大公因数与广义欧几里得除法

1、最大公因数

定义3.1:

设a1,···,an是n(n≥2)个整数。若整数d是它们中每一个数的因数,则d就叫做a1,···,an的一个公因数。

d是a1,···,an的一个公因数的数学表达式为:d | a1,···,d | an

如果整数a1,···,an不全为零,那么a1,···,an的所有公因数中最大的一个公因数叫做最大公因数,记作(a1,···,an)。

特别地,当(a1,···,an) = 1 时,称a1,···,an互质互素

注①:d > 0是a1,···,an的最大公因数的数学表达式可表述为

  1. d | a1,···,d | an
  2. 若 e | a1,···,e | an,则e | d。

注②:a,b的最大公因数 d = (a,b)是集合

  { s · a + t · b | s, t ∈ Z}

注③:a1,···,an的最大公因数 d 是集合

  { s1 · a1 + ··· + sn · an | s1,···,sn ∈ Z}

定理3.1:

设a1,···,an是n个不全为零的整数,则

  1. a1,···,an 与 |a1|,···,|an|的公因数相同
  2. (a1,···,an)=(|a1|,···,|an|)。

定理3.2:

设b是任一正整数,则(0,b)= b。

定理3.3:

设a,b,c是三个不全为零的证书。如果a = q · b + c,其中q是整数,则(a,b)= (b,c)

性质3.1:

定理3.4:

定理3.5:

 

2、最大公因数的进一步性质

定理3.9:

设a,b是任意两个不全为零的整数,d是正整数,则d是整数a,b的最大公因数的充要条件是:

  1. d | a,b | b;
  2. 若 e | a,e | b, 则e | d。

假设1,2成立,那么

  1. 说明d是整数a,b的公因数;
  2. 说明d是整数a,b的公因数中的最大数,因为e | d 时,有 | e | ≤ d。

因此,d是整数a,b的最大公因数。

定理3.10:

 

 

定理3.11:

定理3.12:

定理3.13:

 

3、多个整数的最大公因数及运算

定理3.14:

定理3.15:

 

4、形为2α-1的整数及其最大公因数

 

四、整除的进一步性质及最小公倍数

1、整数的进一步性质

定理4.1:

设a,b,c是三个整数,且c ≠ 0,如果c | ab,(a,c)= 1,则c | b。

定理4.2:

设p是素数。若p | ab,则p | a 或 p | b。

定理4.3:

设a1,···,an是n个整数,p是素数。若p | a1,···,an,则p一定整除某一ak,1 ≤ k ≤ n。

2、最小公倍数

定义4.1:

 

定理4.4:

 

3、最小公倍数与最大公因数

定理4.5:

 

4、多个整数的最小公二倍数

定理4.6:

定理4.7:

 

五、整数分解

定理5.1:

 

六、素数的算数基本定理

1、算数的基本定理

定理6.1:

定理6.2:

 

2、算数基本定理的应用

定理6.3:

定理6.4:

定理6.5:

定理6.6:

 

七、素数定理

定理7.1:

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/3cH0-Nu1L/p/14255252.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!