1、 厦门一中 梁黄炫 在 NOIP竞赛中，会涉及到不少比较数学化的知识，这里会选取一些比较经典的进行教学说明，以期让大家对联赛的数论知识有个大概的了解，题目以复赛题目类型为主。 如果有整数 a、 b,且 a1的正整数 p， p仅有的正因子是 1、 p，则称 p是素数，而称 1又不是素数的数为合数， 1既不是素数也不是合数。 如果 p是合数，则必然有一个 p，这不合法，所以上述结论成立。 因此我们就得到了一个判断 n是否是合数的算法，枚举 2sqrt(n)，考虑是否有数整除 n即可。可以注意到在枚举的过程中，我们已经把 n的所有可能约数都算出来了，即找到一个1的正整数 n， n必然可以唯一的表示成
2、若干个素数的乘积，即n=a1b1*a2b2*a3b3 ，其中 a1a2a3.且ai为素数，这样的分解方案是唯一的。 当然这是一个需要证明的定理，有兴趣的同学可以自己尝试，这里不再赘述。 mod运算：令 a为整数， d为正整数，那么有唯一的整数 q和 r，其中 0=rd，使得 a=dq+r。此时称 d为除数 ,a为被除数 ,q为商 ,r为余数，特别的，我们定义 r为 a mod d。 但是要注意，计算机中若 a0，则 a mod b依然是负数，与数学上的定义并不同。余数运算有这些性质 :(a+b) mod c=(a mod c+b mod c) mod c(a-b) mod c=(a mod c
3、-b mod c) mod c(a*b) mod c=(a mod c*b mod c) mod c。 最大公约数和最小公倍数：令 a和 b是不全为0的两个整数，能使 d|a和 d|b的最大整数称为 a和 b的最大公约数，用 gcd(a,b)表示（有时候简记为 (a,b)。令 a和 b是不全为 0的两个整数，能使 a|d和 b|d的最小正整数称为 a和 b的最小公倍数，用 lcm(a,b)表示（简记为 a,b）下面介绍相关的一些性质： 令 a和 b为正整数，则 a*b=gcd(a,b)*lcm(a,b) 为了证明这个定理，可以考虑 a和 b的素因子分解式： a=p1a1*p2a2*.*pnan b=p1b1*p2b2*.*pnbn 由于要使得 a、 b的素因子形式相同，这里允许 ai、 bi为 0（但不同时为 0）
