网站设计师和网页设计师,网站收录下降的原因,绵阳网站维护托管,网站类网站开发源代码主要内容#xff1a; 整除的基本概念#xff08;掌握#xff09; 素数#xff08;掌握#xff09; 同余的概念#xff08;掌握#xff09;
1.1整除
定义#xff1a;设a#xff0c;b是任意两个整数#xff0c;其中b≠0#xff0c;如果存在一个整数q#xff0c;使 …主要内容 整除的基本概念掌握 素数掌握 同余的概念掌握
1.1整除
定义设ab是任意两个整数其中b≠0如果存在一个整数q使 a qb则我们称b整除a或a被b整除记为b|a此时称 b是a的因子a是b的倍数。 例a10, b2则有2|10若a100, b10有10|100 例设a是整数a≠0, 则a|0。 整除的基本性质 1. 如果b|a且a|b则b a或b -a。 2. 如果a|b且b|c则a|c。 3. 如果c|a且c|b则c|uavb其中uv是整数。
整除的基本性质补充 (1) a|b-a|ba|-b-a|-b|a| | |b| (2) b≠0且a|b |a|≤|b|
带余除法当两个整数不能整除时我们有带余除法 定义对于ab两个整数其中b≠0则存在唯一qr使得abqr0 ≤ r|b|。r称为a被b除得到的余数, 当r 0时b|a。 例 1a –37 b 5则–37 (-8)×53q8r3 2a 67b 7则67(9)×(7)4q9 r4 最大公因子 定义 1) 设ab是两个整数如果整数c|a且c|b则c称为ab的公因子。 2) 设c0是两个不全为零的整数ab的公因子如果ab的任何公因子都整除c则c称为ab的最大公因子记为c(a,b)。
最大公因子性质 1.(a,b)(-a,b)(a,-b)(-a,-b)(|a|,|b|) 2.(0,a)a
最大公因子求解 例(-38241837) 最大公因子定理 定理设ab是两个不全为零的整数则存在两个整数u, v使得(a, b)uavb。 例将a 888b 312的最大公因子表示为(a,b) uavb。 1.2互素
定义设ab是两个不全为0的整数如果(a, b)1则称ab互素。
推论a, b互素的充分必要条件是存在uv使uavb1。
互素性质 1) 如果c|ab且(c, a) 1则c|b 。 2) 如果a|cb|c且(a, b) 1则ab|c 。 3) 如果(a,c) 1(b,c) 1则(ab,c) 1 。
最小公倍数 定义 1) 设a, b是两个不等于零的整数如果a|db|d则称d是a和b的公倍数。 2) a和b的正公倍数中最小的称为a和b的最小公倍数记为[a,b] 。
最小公倍数性质 [ab] [–ab] [a–b] [–a–b] [|a||b|] 例a 2b 3它们的公倍数集合为{0±6±12±18…}.而[23] 6 。 最小公倍数与最大公因子关系 定理 1) 设d是ab的任意公倍数则[a, b] | d 。 2)特别地如果(a, b) 1, [a, b] |ab|。
1.3素数
定义如果一个大于1的整数p除±1和±p外无其他因子则p称为一个素数否则称为合数。
定理设p是一个素数则 1) 对任意整数a如果p不整除a则(pa) 1。 2) 如果p|ab则p|a或p|b。
算术基本定理 定理每个大于1的整数a都可以分解为有限个素数的乘积ap1p2…pr。该分解除素数因子的排列外是唯一的。
标准因子分解式 由于p1p2…pr中可能存在重复所以a的分解式可表示为有限个素数的幂的乘积这称为a的标准因子分解式。 例2100的标准因子分解式 素数无穷个 定理素数有无穷多个。
Eratosthenes筛法 定理设a是任意大于1的整数则a的除1外最小正因子q是一素数并且当a是一合数时。
对于一般NEratosthenes筛法可表述如下 第1步 找出的全部素数p1p2…pm。 第2步 在1~N中分别划去p1p2…pm全部倍数。 第2步完成后剩下的数除1外就是不超过N的全部素数。
筛法原理如下对于一个数a≤N如果p1p2…pm都不整除a则a是素数。这是因为如果a是合数则由定理它必有一素因子在p1p2…pm中。 例求不超过100的全部素数。 同理可以将因子57的倍数划去 (3) 划去5的全部倍数 (4) 划去7的全部倍数。 最终经过上述步骤后剩下的数除1外就是不超过100的全部素 数 (25个) 2357111317192329313741434753596167717379838997 1.4 同余
定义给定一个称为模的正整数m。如果m除整数ab得相同的余数即aq1mrbq2mr0≤ r小于等于m 则称a和b关于模m同余记为 a≡b (mod m) 例25≡1(mod 8)16≡-5(mod 7)。 定理整数ab对模m同余的充分必要条件是m|(a-b)即a bmtt是整数。
同余性质及推论
推论如果a1≡b1 (mod m)a2≡b2 (mod m)则
快速指数算法 例1-16求解 2^64 (mod 641)
