设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。3d
注:blog
(1)当b遍历整数a的全部因数时,-b也遍历整数a的全部因数。数学
(2)当b遍历整数a的全部因数时,a/b也遍历整数a的全部因数。遍历
根据定义有:方法
设a,b ≠ 0,c ≠ 0是三个整数。若 b | a,c | b,则c | a。im
设a,b,c ≠ 0是三个整数。若c | a,c | b,则c | a ± b。d3
设a,b,c ≠ 0是三个整数。若c | a,c | b,则对任意整数s,t,有c |(s·a+t·b)。db
设整数c ≠ 0。若整数a1,···,an都是整数c的倍数,则对任意n个整数s1,···,sn,整数s1a1 + ··· + snan是c的倍数。img
设a,b都是非零整数。若a | b,b | a,则a = ±b。
设整数n ≠ 0,±1.若是除了显然因数±1和±n外,n没有其余因数,那么n就叫作素数(或质数或不可约数),不然,n叫作合数。
设n是一个正合数,p是n的一个大于1的最小正因数,则p必定是素数,且p≤n1/2。
设n是正整数。若果对全部的素数p ≤ n1/2,都有p不被n整除,则n必定是素数。
应用该定理,可获得一个寻找素数的肯定性方法,一般叫作平凡除法或厄拉托塞师筛法。
设a,b是两个整数,其中b>0,则存在惟一的整数q,r使得a = q·b + r ,0 ≤ r ≤ b 。
a = q·b + r ,0 ≤ r ≤ b中,q叫作a被b除所得的不彻底商,r叫作a被b除所得的余数。
设x是实数,称x的整数部分为小于或等于x的最大整数,记成[x]。
这时,有[x] ≤ x< [x]+1。
素数的平凡判别:对于给定正整数N,设不大于N1/2的全部素数为p1,p2,,···,ps。
若是N被全部pi除的余数都不为零,则N是素数。
设a,b是两个整数,其中b>0.则对任意的整数c,存在惟一的整数q,r使得
a = q·b+r,c ≤ r<b+c
设b是大于1的正整数,则每一个正整数n可惟一地表示成
n = ak-1bk-1 + ak-2bk-2 + ··· + a1b + a0,
其中ai是整数,0 ≤ ai ≤ b-1,i = 1,···,k-1,且首项系数ak-1 ≠ 0.
大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)。
设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的最大公因数的数学表达式可表述为
注②:a,b的最大公因数 d = (a,b)是集合
{ s · a + t · b | s, t ∈ Z}
注③:a1,···,an的最大公因数 d 是集合
{ s1 · a1 + ··· + sn · an | s1,···,sn ∈ Z}
设a1,···,an是n个不全为零的整数,则
设b是任一正整数,则(0,b)= b。
设a,b,c是三个不全为零的证书。若是a = q · b + c,其中q是整数,则(a,b)= (b,c)
设a,b是任意两个不全为零的整数,d是正整数,则d是整数a,b的最大公因数的充要条件是:
假设1,2成立,那么
所以,d是整数a,b的最大公因数。
设a,b,c是三个整数,且c ≠ 0,若是c | ab,(a,c)= 1,则c | b。
设p是素数。若p | ab,则p | a 或 p | b。
设a1,···,an是n个整数,p是素数。若p | a1,···,an,则p必定整除某一ak,1 ≤ k ≤ n。