第一章 初等数论

概述

数论被誉为数学的皇后，它的研究对象是我们经常接触的整数及其一些性质，例如求两个整数的最大公约数和最小公倍数，求一个正整数的素因子分解，求一个方程的整数解等等。

起源

毕达哥拉斯和他的学派在数学上有很多创造，尤其对整数的变化规律感兴趣。例如，把全部因数之和（除其本身之外）等于本身的数称为完全数；将其因数之和大于本身的数称为盈数；将其因数之和小于本身的数称为亏数。上帝6天创造世界，而6就是一个完全数，因为6=1+2+3；而8则是个亏数，因为1+2+4<8。直到19xx年，人类才知道12个完全数，他们都是偶数，其中前三个是6,28,496.

一般认为，毕达哥拉斯及其后继者，连同这个团体的哲学，是数轮发展的先驱，是后来把数论发展成神秘主义的基础。如魔术、法术、占星学、占卜上。

整除

设a,b都是非0整数，如果存在一个整数q，使得b=aXq,那么就说b可被a整除，记作a|b，且称b是a的倍数，a是b的约数（因子）。例如，3|12，21|63。下面是有关整除的几个性质。

1． 如果a|b且b|c，那么a|c。

2． a|b且a|c等价于对任意的整数x,y,有a|(b×x+c×y)。

3． 设m≠0,那么a|b等价于（m×a）|(m×b)。

4． 设整数x,y满足下式：a×x+b×y=1,且a|n、b|n，那么（a×b）|n.

证明：因为a|n且b|n,由性质3可得(a×b)|(b×n)且(a×b)|(a×n)

再由性质2得（a×b）|a×n×x+b×n×y)

而a×n×x+b×n×y=n×(a×x+b×y)=n×1=n

所以(a×b)|n

5. 若b=q×d+c,那么d|b的充要条件是d|c。

另外还有一些有用的例子，比如：若2能整除a的最末位（约定0可以被任何数整除），则2|a,若4能整除a的最后两位，则4|a,若8能整除a的最后三位，则8|a,…；若3能整除a的各位数字之和，则3|a；若9能整除a的各位数字之和，则9|a；若11能整除a的偶数位数字之和与奇数位数字之和的差，则11|a。同时，能被7,11,13整除的数的特征是：这个数的末三位数与末三位以前的数字所组成的数之差能被7、11、13整除。

勾股数

对于正整数X,Y,Z,如果满足下列不定方程：X2+Y2=Z2，则称这组正整数（X,Y,Z）为勾股数，他们有着不同的几何含义，如作为一个三角形的三个边。一般限定X和Y互质，且X为偶数。认为(4,3,5)和(6,8,10)为本质相同的勾股数，(X,Y,Z),(X,Z,Y),(Y,X,Z),(Y,Z,X),(Z,X,Y),(Z,Y,X)是一组相同的勾股数。

勾股数有如下几个性质：

1. X,Y,Z一定两两互质。

2. X,Y一定一奇一偶。

3. X+Z一定是一个完全平方数。

4. (Y+Z)/2也是一个完全平方数。

5. X×Y×Z一定能被60整除。

例：勾股数

问题描述：键盘输入整数R,输出小于等于R的满足X2+Y2=Z2的所有正整数X,Y,Z。

问题分析

从数学上考虑，它的一切解都可以表示成如下公式（M,N为正整数，且M>N）:

X=2×M×N

Y=M2-N2

Z=M2+N2

如：M=2,N=1，有：（4,3,5）

M=3,N=2，有：（12,5,13）

M=3,N=1，有：（6,8,10）

M=4,N=3，有：（24,7,25）

M=4,N=2，有：（16,12,10）

M=4,N=1，有：（8,15,17）

所以，算法实现上只要穷举N、M即可。

参考程序

Var r,m,n,x,y,z,count:longint;

Begin

Readln(r);

Count:=0;

For n:=1 to trunc(sqrt(r div 2)) do

For m:=n+1 to trunc(sqrt(r-n*n)) do Begin

X:=2*m*n;

Y:=m*m-n*n;

Z:=m*m+n*n;

Count:=count+1;

Writeln(‘NO.’,count,x:10,y:10,z:10); End;

Writeln(count);

End.

最大公约数与最小公倍数

公约数中最大的一个称为最大公约数，记为GCD，显然它是存在的，至少为1。当GCD=1时，称这n个数是互质的。公约数一定是最大公约数的约数。

公倍数中最小的一个称为最小公倍数，记为LCM，显然它也是存在的。公倍数一定是最小公倍数的倍数。

数学上，求两个数的最大公约数常用辗转相除法；而求两个数的最小公倍数的方法可以用穷举法或者逐步倍增法，如求3和8的最小公倍数，可以让n从1开始逐步加1，不断检查8*n是不是3的倍数。

定理：a,b两个数的最大公约数乘以它们的最小公倍数等于a和b本身的乘积。

比如，要求3和8的最小公倍数，则LCM(3,8)=3*8 div GCD(3,8)=24.

例：求n个数的最大公约数与最小公倍数

问题描述：编程求n个(n<=100)正整数Ai（Ai<=30000,1<=i<=n）的最大公约数和最小公倍数。假设解一定在长整数范围内。

输入： 3

3 4 5

输出： 1

60

分析：先求出两个数的最大公约数，再和其他数求最大公约数，只需调用函数n-1次。

参考程序：

Var I,j,k,n,gcd,lcm:longint;

A:array[1..100] of longint;

Function gcdnum(p,q:longint):longint;

Begin

If p mod q=0 then gcdnum:=q

Else gcdnum:=gcdnum(q,p mod q); End;

Begin

Readln(n);

For i:=1 to n do read(a[i]);

Gcd:=a[1];lcm:=a[1];

For i:=2 to n do

Begin

Gcd:=gcdnum(gcd,a[i]);

Lcm:=lcm*a[i] div gcdnum(lcm,a[i]); End;

Writeln(‘Gcd=’,gcd);

Writeln(‘Lcm=’,lcm);

End.

尼科梅彻斯定理

问题描述

任何一个自然数的立方都可以写成一串连续奇数之和。

1^3=1

2^3=3+5=8

3^3=7+9+11=27

4^3=13+15+17+19=64

……

编程输入N，输出N^3是由哪些连续奇数之和得到的。

问题分析

枚举法和归纳法是科学研究的基本方法之一，也是我们用计算机编程解题的重要手段。一般先从枚举一些简单数据入手寻找是否有规律，归纳法是通过分析问题，从具体事例和数据中发现一般规律，找到问题的最本质的规律，拟出猜想命题，最好再用数学方法（一般用数学归纳法）证明命题的真假。

本题的归纳方法如下：因为n^3是n个奇数之和。

第m个奇数的值（通项公式）为2m-1：1，3，5，7，9，…

所以：

组成1^3的1个奇数是奇数序列中的第1个奇数。

组成2^3的2个奇数是奇数序列中的第1+2=3个奇数及其前n-1=2-1=1个。

组成3^3的3个奇数是奇数序列中的第1+2+3=6个奇数及其前n-1=3-1=2个。

组成4^3的4个奇数是奇数序列中的第1+2+3+4=10个奇数及其前n-1=4-1=3个。 …

归纳得到，

组成n^3的n个奇数中的最大奇数是奇数序列中的第k个，k=1+2+3+…+n=n×(n+1)/2， 组成n^3的n个奇数中的最小奇数是奇数序列中的第p个，p=1+2+…+(n-1)+1=(n×n-n+2)/2 最大奇数和最小奇数分别是2k-1=n(n+1)-1和2p-1=n×n-n+1。

参考程序

Var n,t,count,sum:longint;

Begin

Readln(n);

If n<1 then writeln(‘ERROR!’)

Else begin

Sum:=n*(n+1)-1;

t:=sum-2*(n-1);

write(t:3);

count:=n-1;

if n>1 then

repeat

count:count-1; sum:=sum+t; write(‘+’,t:3); until count=0; writeln(‘=’,n:3,’^3=’,sum:8) end

end.

组合数学

抽屉原理（鸽巢原理）

把n+1件东西放入n个抽屉，则至少有一个抽屉里放了两件或两件以上的东西。从另一个角度说，把n-1件东西放入n个抽屉，则至少有一个抽屉是空的。

例：假设一年365天，那么366个人中总有两个人生日相同。

加法原理

加法原理可以描述为：如果时间A有p种产生方式，事件B有q种产生方式，则事件“A或B”有p+q种产生方式。

例如，两个班级的同学报名参加篮球比赛，A班有15人报名，B班有10人报名，则两个班报名参加篮球比赛的人数总共为15+10=25人。

使用加法原理要注意时间A和B 产生的方式不能重叠，相互独立。

加法原理可以推广到n个事件。

乘法原理

乘法原理可以描述为：如果事件A有p种产生方式，事件B有q种产生方式，则事件“A与B”有p×q中产生方式。

例如，从A地到B地有5种走法，从B地到C地有3种走法，则从A地经过B地再到C地的走法一共有5×3=15种。

使用乘法原理的条件是：事件A与B要相互独立，即他们的产生方式要彼此无关。 乘法原理可以推广到n个事件。

举例

1.一个班级中有20人学习英语，有10人学习德语，有3人同时学习英语和德语，问班级里共有几人学习外语？

2.求有多少个没有重复数字且能够被5整除的四位奇数？

解：被5整除的奇数：个位必须为5，只有这一种方案。千位不能是5和0，所以有8种方案。十位和百位只要不是5和千位上的数字就行，即8×7=56种方案。所以，根据乘法原理，共有1×8×56=448个符合条件的数。

3.有8位同学排成一行，要求A、B两位同学互不相邻，问有多少种排法？

解：先不考虑限制条件，共有8！种排法。再考虑7位同学的排法，即先不让B排，则有7！种排法。最后将B排在A的左边或右边，所以，这两个人相邻的情况有：2×7！种排法。因此，整个问题的解为：8！－2×7！=30240种排法。

4.有8位同学排成一列，其中4位女生，要求同性别的人不相邻，问有多少种排法？

解：假设第一位同学是男生，则4个男生的排列数为4！=24种。再把每个女生插入在每个男生后面，而四个女生的排列数也为4！=24种，即分别把每种男生的排列与每种女生的排列进行合成，则根据乘法原理，共有24×24=576种排法，同理，如果第一位同学是女生，则也有576种排法。所以，根据加法原理，本题共有576+576=1152种排法。

排列

组合数学的研究对象，根据有无顺序，一般分为排列问题和组合问题。排列于组合的根本区别在于前者与元素的顺序有关，后者与元素的顺序无关。

在排列与组合的问题中，经常会出现计数问题，解决计数问题的思路一般有以下三种：

1. 只取要的。即把各种符合条件的情形枚举出来，再利用加法原理累加。

2. 先全部取，再减去不要的。即把所有可能的情形构造出来，再减去不符合条件者。

3. 先取后排。即先把各步中符合条件的排列或组合计算出来，在根据乘法原理求积。

例：

1.有8位同学排成一列，其中4位女生，要求同性别的人不相邻，问有多少种排法？

解：

2.有8位同学排成一行，要求A、B两位同学互不相邻，问有多少种排法？

解：

3.求有多少个没有重复数字且能够被5整除的四位奇数？

解：

组合

从n个元素的集合S中，无序选取出r个元素，叫做S的一个r组合。如果两个组合中，至少有一个元素不同，他们就被认为是不同的组合。

在一个问题中，所有不同组合的个数，叫做组合书，记作C(n,r)。研究组合的目的之一就是要找出根据已知条件所能构成的组合数。

C(n,r)=P(n,r)/r!=n!/(r! ×(n-r)!) (r<=n)

约定：C(n,0)=1

证明：每一种组合，可以扩展到r!种排列，而总排列为P(n,r)，所以组合数为P(n,r)/r!

例：

1. 一班有10名同学，二班有8名同学。要在每个班级选出2 名学生参加一个座谈会，问

有多少种选法？

解：

2. 某班有10名同学，其中有4名女同学。要在班级选出3名学生参加座谈会，其中至少

有1名女同学，问有多少种选法？

解 运用组合及加法原理，共有：C(4,1) ×C(6,2)+C(4,2) ×C(6,1)+ C(4,3) ×C(6,0)=100种。也可以运用“减法原理”，先确定1名女同学都不选的方案数为C(6,3) ×C(4,0)=20种，而从10个人中选3个（不分性别）的方案数为C(10,3)=120种，所以，符合题目的方案数为120-20=100种。

3. 仅含有数字1和0的10位正整数中，能被11整除的数有多少个？

解 一个正整数能被11整除的充要条件是其奇数位上数字之和与偶数位上数字之和的差是11的倍数。

设仅含有1和0的10位十进制正整数是n=1abcdefghi（最高位必须是1）。

根据上述的充要条件得：a+c+e+g+i=P （1）

1+b+d+f+h=Q （2）

则P-Q能被11整除，且|P-Q|<=5。所以，P只能等于Q，设P=Q=K，则K可取1、2、3、4、5共五种方案。对于给定的K，根据（1）式，a、c、e、g、i中应该为K个1, 5-K个0，共有C（5，K）种方案。而b、d、f、h中应该为K-1个1，5-K个0，共有C(4,K-1)种方案。所以，根据乘法原理、加法原理和排除法，总的方案数S为：

C(5,1) ×C(4,0)+ C(5,2) ×C(4,1)+C(5,3) ×C(4,2)+C(5,4) ×C(4,3)+C(5,5) ×C(4,4)=126

组合问题

组合数学研究的中心问题是如何按照一定的规则来安排一些物体。 1. 存在性问题:判断满足某种条件的情况或状态是否存在

例：三角形中的点

问题描述：在边长为2的等边三角形中放5个点，则至少存在两个点，它们之间的距离小于等于1.

证明：将等边三角形的3条边的中点连接起来，形成4个边长为1的等边三角形。根据抽屉原理，5个点放在4个三角形中，则至少有1个三角形内（包括其边上）有2个点，而一个边长为1的等边三角形内任两个点之间的距离都小于等于1

2． 计数性问题：存在多少种满足某种条件的情况或状态

例：路径问题

问题描述：有一个m×n的棋盘，其中，m=4,n=5，有一个中国象棋的“卒”要从左上角走到右下角，卒每步只能往右或者往下走一格，问卒一共有多少种走法？

问题分析

解法1：递推（加法原理）

解法2

假设0=向右走一步，1=向下走一步，那么从左上角到右下角的一种可能的走法，就唯一对应了一个由4个0和3个1组成的7位二进制字符串。反之，给定一个由4个0和3个1组成的7位二进制字符串，则这个字符串又唯一对应了一种可能的走法。这样便建立了一种一一对应关系，所求的方案数就是有4个0和3个1组成的7位二进制字符串的个数，即C(7,4)=35.

集合

1、集合的运算：并、交、补、差

并：∪

交：∩

补：～或￣ 差：－(定义：一般地，记A，B是两个集合，则所有属于A且不属于B的元素构成的集合，叫做集合A减集合B(或集合A与集合B之差)

1 （NOIP9）设全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，则集合（A ∩B）∪～C 为（ ）。

A） 空集 B） {1} C） {3，5} D）{1，5} E） {1，3，5}

2 （NOIP10）设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，

B = {b, d, e}，C = {e, f, g}，那么集合

A. {a, b, c, d} B. {a, b, d, e}

C. {b, d, e} D. {b, c, d, e} E. {d, f, g}

3 （NOIP11）设全集I = {a, b, c, d, e, f, g, h}，

集合B∪A = {a, b, c, d, e, f}，

C∩ A?= {c, d, e}，A∩~B = {a, d}，那么集合C∩ B∩ A

为（ ）。

A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f} 为（ ）。

2、容斥原理

在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：

先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

容斥原理的第一形式：设A，B是有限集合，则

容斥原理的第二形式：设A、B、C是有限集合，则

1、（NOIP10）75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。

1：

只是玩过其中两种的有55-20=35人

只是玩过其中一种人所花费用 700-20*（5*3）-35*（5*2）=50元

只是其中一种的人数 50÷5=10人

没有玩过其中任何一种的人数 75-20-35-10=10人

2、某学校足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队，那么同时只参加两个队的队员有多少？

足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队,减去这2人，则足球队有球衣28件，篮球队有球衣13件，排球队有球衣16件，三队队员总数为48人，

设学足球的为集合A 篮球为集合B 排球为集合C ∵|A∪B∪C|=48 |A|=28 |B|=13 |C|=16 |A∩B∩C|=0 x=|A∩B|+|B∩C|+|C∩A|

∴28+13+16-x=48

X=9人

3、分母是1001的最简分数一共有多少个？

1001＝7×11×13

在1——1001这些自然数中，1001的约数有：

1、7、11、13、7×11、7×13、11×13、7×11×13共8个，

所以，分母是1001的最简真分数共有：1001－8＋1＝994个。

因数分解

var

n,i:longint;

begin

readln(n);

i:=2;

while n>1 do

begin

while n mod i<>0 do i:=i+1;

while n mod i=0 do begin

write(i);

n:=n div i;

if n<>1 then write('*'); end;

end;

end.