备考2024新高考新题型高三数学--数论与密码学

这是一份备考2024新高考新题型高三数学--数论与密码学，共10页。试卷主要包含了整除，不能被整除就记做，素数与合数，带余除法，最大公因数与最小公倍数，同余定理是数论中的重要内容等内容，欢迎下载使用。

1.整除.
设如果存在使得那么就说可被整除(或整除),记做且称是的倍数,是的约数(也可称为除数、因数).不能被整除就记做.
整除关系的基本性质：
（1）.
（2）.对任意的有
（3）.设，则.
（4）.若，则.
（5）.设为整数，若，则或者.
性质（5）提供了由整除关系到不等关系的一种基本途径，该性质表明：若整数，且，则不整除.
2.素数与合数.
（1）素数的定义：
（2）定理：素数有无穷多个.
3.带余除法（核心内容）.
带余除法：设、是两个给定的整数且，那么，存在唯一的一对整数和，满足，其中，显然，.
4.最大公因数与最小公倍数：
（1）.定义：设是两个不全为零的整数,如果且那么就称为和的公约数,我们把和的公约数中的最大的称为和的最大公约数,记做若则称和是既约的,或是互素的.
（2）设是两个均不为零的整数,如果且那么就称为和的公倍数,我们把和的公倍数中的最小的称为和的最小公倍数,记做
（3）基本性质：若为素数，则.
（4）若的最大公因数为1，则称互素.
★二.同余及应用
设为正整数,若整数和被除的余数相同,则称和对模同余,记做
1.同余的性质：
自反性：；
（2）对称性：若，则；
（3）传递性：若且，则；
（4）若，，则；
（5）若，，则.特别地，若，则
2.完全剩余系与既约剩余系
（1）设是一个给定的正整数,我们称为模的同余类(或剩余类).显然构成整数集的一个划分.
例如，我们以，全体整数被2整除的模2的同余类为0或者1，前者为偶数，后者为奇数，这就完成了一次整数的分类，依此类推.
在模的同余类中各取一数,这个数称为模的一个完全剩余系(简称完系).最常用的完系称为模的非负最小完全剩余系.
（2）如果一个模的同余类里面的数与互素,就把它叫做一个与模互素的同余类,在与模互素的全部同余类中,各取一数所组成的集叫做模的一个简系.模的一个简系的元素个数记为欧拉函数
欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.
★三.初等数论中的几个重要定理
1.欧拉定理：设证明：欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.也等于模的一个简系的元素个数.
进一步，令,若则于是
若则,所以这就证明了费马小定理.
2.(费马小定理)设一个素数,对任意的整数,证明若则
3.算术基本定理：
设整数,那么其中是素数,在不计次序下唯一.把中相同的素数合并,则得到标准素因数分解式
4.欧拉函数.
1.定义：欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.
2.计算公式：
（1）若为素数，则
（2）若为素数，且，形成了一个等比数列.
证明：即证.由的定义知等于从减去中与不互质的数的个数；亦即等于从减去中与不互质的数的个数.由于是质数，故等于从减去中被整除的数的个数.由于中被整除的数的个数是，故.
（3）已知正整数的素因数分解式其中素数
,证明：
二．典例分析
例1.设都是正整数，则在中恰有个数被整除.
解析：此题是数论中的经典结论，利用高斯取整函数和带余除法基本概念可得：若整数满足（，，是整数且），则
例2.证明：完全平方数模同余或.
解析：根据模的余数，可将任意整数分为四种，那么的形式为：，故模的余数只能为或.
例3．若正整数、只有为公约数，则称、互质.对于正整数，是小于或等于的正整数中与互质的数的个数.函数以其首名研究者欧拉命名，称为欧拉函数，例如：，，，则下列说法正确的是（ ）
A． B．数列是等差数列
C． D．数列的前项和为，则
解析：对于A选项，在不超过的正整数中，与互质的正整数有：、、、，故，A错；
对于B选项，因为，，，显然、、不成等差数列，B错；
或者用上面公式：，显然不是等差数列.
对于C选项，为质数，在不超过的所有正整数中，能被整除的正整数的个数为，
所有与互质的正整数的个数为，所以，，
因此，，C错；或者用上面公式：，因此，，C错；
对于D选项，因为为质数，在不超过的正整数中，所有偶数的个数为，
所以，，所以，，则，
所以，，上述两个不等式作差可得，所以，，D对.
或者：若，形成了一个等比数列.故选D.
例4．我国南北朝时期的著作《孙子算经》中对同余问题有了较深的研究．设，，为正整数，若和被除得的余数相同，则称和对模同余，记为．下列说法正确的是（ ）
A．若，，则
B．
C．若，，，则
D．若，，则
解析：若，则或，故，故A错误；
因为，所以被7除所得的余数为1，65被7除所得的余数为2，故B错误；
由，得，由，得，所以，被除得的余数为6，而被除得的余数为5．故C错误；
若，则，，
，
，所以，故D正确．
故选：D.
例5．中国南北朝时期的著作《孙子算经》中，对同余除法有较深的研究设，，为整数，若和被除得的余数相同，则称和对模同余，记为．若，，则的值可以是（ ）
A．2021 B．2023 C．2025 D．2026
【答案】C
解析：因为，
又，被8除得的余数为1，
所以被8除得的余数也要为1，因为2021除以8余5，2023除以8 余7，2025除以8余1，2026除以8余2，所以的值可以2025，故选：C
例6．若两整数、除以同一个整数，所得余数相同，即，则称、对模同余，用符号表示，若，满足条件的由小到大依次记为，则数列的前项和为__________.
解析：由两数同余的定义，是一个正整数，对两个正整数、，若是的倍数，
则称、模同余，我们易得若，则为6的整数倍，则，
故均满足条件．由等差数列的前项公式，
则．故答案为：976．
例7.（合肥一中24届高三模拟试题）同余定理是数论中的重要内容.同余的定义为:设且.若则称与关于模同余,记作(“|"为整除符号).
（1）解同余方程;
（2）设（1）中方程的所有正根构成数列,其中.
①若,数列的前项和为,求;
②若,求数列的前项和.
解:（1）由题意,所以或,即或.
(2)①由(1)可得为,所以，因为,所以
.
②.
因为,所以
.
例8．欧拉函数(n)(n∈)的函数值等于所有不超过正整数n，且与n互质的正整数的个数，例如：(1)=1，(4)=2．
（1）求，；
（2）令，求数列的前n项和．
解析：（1）不超过9，且与其互质的数即为中排除掉3，6，9剩下的正整数，
则；不超过27，且与其互质的数即为[1,27]中排除掉3，6，9，12，15，18，21，24，27剩下的正整数，则．
（2）表示任意相邻的三个正整数，其中与互质的为与两个，故分别取可得中与互质的正整数个数为，所以，所以．设数列的前项和为．
，∴，
两式相减得：
则．
例9．（24届高三九省联考试卷）离散对数在密码学中有重要的应用．设是素数，集合
，若，记为除以的余数，为除以的余数；设，两两不同，若，则称是以为底的离散对数，记为．
（1）若，求；
（2）对，记为除以的余数（当能被整除时，）．证明：，其中；
（3）已知．对，令．证明：．
解析：（1）若，又注意到，所以.
（2）当时，此时，此时，，
故，此时.
当时，因相异，故，而，故互质.
记，
则，使得，
故，故，设，则，因为除以的余数两两相异，且除以的余数两两相异，故，故，
故，而其中，
故即.
（3）由题设和（2）的法2的证明知：
，
．
故
．
由（2）法2的证明知，所以．