初等数论与小学数学.ppt

初等数论与小学数学1.辗转相除法与最大公因数解：4935
4042定理1若是任一正整数,则与的公因数就是的因数,反之,的因数也就是与的公因数..

定理2设是任意三个不全为的整数,且其中是非零整数,则与有相同的公因数,因而
定理3若是任意两个整数,,且有下面的系列等式:

则就是最后一个不等于零的余数,即

2.算术基本定理与高斯函数问题2.3：问的末尾0的个数？定义1一个大于1的整数,如果它的正因数只有1及它本身,就叫作质数(或素数);否则就叫作合数.
定理1(算术基本定理)任一大于1的整数能表成质数的乘积,即任一大于1的整数
,,
其中是质数,并且若
,,
其中是质数,则,,定义2函数是对于一切实数都有定义的函数,函数的值等于不大于的最大整数;函数称为的高斯函数，我们也把叫做的整数部分.
定理2若是任意两个正整数,则不大于而为的倍数的正整数的个数是.
定理3在的标准分解式中质因数的指数问题3.1:测算某同学的年龄?
问题3.2（“物不知数”或“韩信点兵”）：“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”
设是所求物数,则依题意《孙子算经》里面所用的方法可以列表如下:定义1给定一个正整数,把它叫做模.如果用去除任意两个整数a与b所得的余数相同,我们就说a,b对模m同余,记作.如果余数不同,我们就说a,b对模m不同余,记作.
定义2设是大于1的整数，且不能整除a，则
称为模的一次同余方程；若整数c满足上述方程，则称是一次同余方程
的一个解.定理1（大衍求一术）设是大于1的整数，若，则一次同余方程有唯一解

（这里为辗转相除所得到的n个不完全商）.定理2(孙子定理)设是k个两两互质的正整数,
,,则一次同余方程组

的解是4.欧拉函数与欧拉定理问题4.3：求的末两位数？
对问题4.3，末两位数是40个一循环，这里
（前面），所以的末两位数与的末两位数相同，为29.
为的欧拉函数，即1至100这100个数中与100互质的整数的个数，又因为
，所以问题4.3：求的末两位数？
解：，.
又，由欧拉定理得

的末两位数末两位数相为29.
定义欧拉函数是定义在正整数上的函数,它在正整数上的值等于序列
中与互质的整数的个数.
定理1设,则

定理2（欧拉定理）设是大于1的整数，
，则
5.不定方程（组）问题5.1（“百鸡问题”）：“鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一.百钱买百鸡.问鸡翁母雏各几何?”
解：设鸡翁、鸡母、鸡雏分别有、、只，则有

（1）
消去z，得
解得
（为整数）
不定方程组（1）的整数解为解不等式组

得，又，
方程组（1）的非负整数解为：（0、25、75）、（4、18、78）、（8、11、81）、（12、4、84）。
有四种买法：（1）鸡翁0只、鸡母25只、鸡雏75只，（2）鸡翁4只、鸡母18只、鸡雏78只，（3）鸡翁8只、鸡母11只、鸡雏81只，（4）鸡翁12只、鸡母4只、鸡雏84只.定义方程(其中是整数,且都不是0)（1）称为二元一次不定方程.
定理1二元一次不定方程（1）有整数解的充分与必要条件是.若，则二元一次不定方程（1）的一个整数解为

（这里为辗转相除所得到的个不完全商）.定理2设二元一次不定方程（1）有一整数解；又设,,则二元一次不定方程的一切解可以表成
（）