专题3 同余与常见数论定理（4大题型）-2025年新高考数学19题新定义培优教程

专题3 同余与常见数论定理 【题型归纳目录】 题型一：同余问题 题型二：费马小定理与欧拉定理 题型三：中国剩余定理 题型四：阶与原根 【知识点梳理】 1、同余 定义：设是正整数，是整数．若，则；如果，则．和模同余的充分必要条件是，与被除得的余数相同． 性质： （1）． 若，则． 若，则 （2）若，则 若，则 若是整数且，则 （3）若，而，则 （4）若，则 （5）若，则． 2、阶与原根 设是一个固定的整数，是与互素的整数，存在整数，使得．我们将具有这一性质的最小正整数（仍记为），称为模的阶． （1）设是模的阶，是任意整数，则的充分必要条件是．特别地，的充分必要条件是． （2）设模的阶为，则数列，模是周期的，且最小正周期是．而个数模互不同余． （3）设，则模的阶整除欧拉函数．特别地，若是素数，则模的阶整除． 3、欧拉定理 设，则． 4、费马小定理 设是素数，，则．或表述为，是素数，则对任意整数有，． 5、威尔逊定理 是素数则． 6、中国剩余定理 （1）设，则一次同余方程有解的充分必要条件是 （2）中国剩余定理 设是两两互素的正整数，则对于任意整数，一次同余方程组 必有解，且全部解是模的一个同余类： ，其中 【典型例题】 题型一：同余问题 【例1】（2025·山东烟台·一模）设是一个项数为的数列，其中每一项均为集合中的元素.定义数列如下：若，则，其中，当时，，当时，，且. (1)若数列，求数列； (2)若存在，对任意，均有数列与为同一数列，则称为数列组的一个周期. （i）若，求数列组的最小正周期； （ii）若数列组存在周期，求的所有可能取值. 【变式1-1】（23-24高三下·北京·强基计划）求 模 7 的余数. 【变式1-2】（24-25高三上·全国·阶段练习）如果和除以所得余数相同，则称对模同余，记作， 若集合，集合，现从集合中的个数中可以抽出个数， （）且，使这个数平均分为组，若存在一组数对 (三者不相等）且满足恰好能被整除，对模同余，则为“灵魂莲华集合”，为“灵魂莲华数对” (1)判断为“灵魂莲华集合” (2)若，判断有多少组数对为灵魂莲华数对 (3)现从素数集合中任取三个不同的数，若构成公差为8的等差数列，求证：无论且为任何集合，最多有一对满足条件的为灵魂莲华数对． 题型二：费马小定理与欧拉定理 【例2】（23-24高三下·河北·开学考试）设a，b为非负整数，m为正整数，若a和b被m除得的余数相同，则称a和b对模m同余，记为． (1)求证：； (2)若p是素数，n为不能被p整除的正整数，则，这个定理称之为费马小定理．应用费马小定理解决下列问题： ①证明：对于任意整数x都有； ②求方程的正整数解的个数． 【变式2-1】（2024高三下·上海·竞赛）数列满足：是大于1的正整数，试证明：在数列中存在相邻的两项，它们除以余数相同. 【变式2-2】（2023高三·全国·专题练习）已知素数证明：为整数，其中． 题型三：中国剩余定理 【例3】（23-24高一上·云南昆明·开学考试）“物不知数”是中国古代著名算题，原载于《孙子算经》卷下第二十六题：“今有物不知其数，三三数之剩二：五五数之剩三；七七数之剩二．问物几何？”问题的意思是，一个数被3除余2，被5除余3，被7除余2，那么这个数是多少？若一个数被除余，我们可以写作．它的系统解法是秦九韶在《数书九章》大衍求一术中给出的．大衍求一术（也称作“中国剩余定理”）是中国古算中最有独创性的成就之一，现将满足上述条件的正整数从小到大依次排序．中国剩余定理：假设整数，，…，两两互质，则对任意的整数：，，…，方程组一定有解，并且通解为，其中为任意整数，，，为整数，且满足． (1)求出满足条件的最小正整数，并写出第个满足条件的正整数； (2)在不超过4200的正整数中，求所有满足条件的数的和．（提示：可以用首尾进行相加）． 【变式3-1】（2023高三·全国·专题练习）证明：对任意正整数，存在个连续正整数，它们中每一个数都不是素数的幂． 【变式3-2】（2023高三·全国·专题练习）解同余方程组． 题型四：阶与原根 【例4】（2021高三·全国·竞赛）设为一个质数，且也是一个质数，证明：的小数表示形式中包含0至9的所有数码． 【变式4-1】（2019高三·全国·竞赛）设是的十进制写法中最后一个非零数字．证明：0·…是无理数． 【强化训练】 1．（2023高三·全国·专题练习）求证：为任意整数． 2．（2023高三·全国·专题练习）设是正整数， (1)证明： (2)证明： (3)证明： 3．（2023高三·全国·专题练习）若证明： 4．（2023高三·全国·专题练习）若跑遍模的完系， 跑遍模的完系．证明：跑遍模的完系． 5．（2023高三·全国·专题练习）已知数列满足. (1)证明：是正整数数列； (2)是否存在，使得？并说明理由. 6．（2023高三·全国·专题练习）已知数列满足. (1)证明：是正整数数列； (2)是否存在，使得？并说明理由. 7．（2024高三·全国·专题练习）已知函数，，，，求证：． 8．（2024高三·全国·专题练习）设，证明： ． 9．（2023高三·全国·专题练习）设证明：存在使得同余方程在模的意义下至少有个根． 10．（2024高三上·全国·专题练习）已知，， (1)若在处取得极值，试求的值和的单调增区间； (2)如图所示，若函数的图象在连续光滑，试猜想拉格朗日中值定理：即一定存在，使得，利用这条性质证明：函数图象上任意两点的连线斜率不小于． 11．（2023高三·全国·专题练习）求所有的正整数，使得为完全平方数． 12．（2023高三·全国·专题练习）（1）求证：是正奇数时，能被整除． （2）是自然数，它不能被整除，求证：与中有且只有一个数被整除． 2 学科网（北京）股份有限公司 $$ 专题3 同余与常见数论定理 【题型归纳目录】 题型一：同余问题 题型二：费马小定理与欧拉定理 题型三：中国剩余定理 题型四：阶与原根 【知识点梳理】 1、同余 定义：设是正整数，是整数．若，则；如果，则．和模同余的充分必要条件是，与被除得的余数相同． 性质： （1）． 若，则． 若，则 （2）若，则 若，则 若是整数且，则 （3）若，而，则 （4）若，则 （5）若，则． 2、阶与原根 设是一个固定的整数，是与互素的整数，存在整数，使得．我们将具有这一性质的最小正整数（仍记为），称为模的阶． （1）设是模的阶，是任意整数，则的充分必要条件是．特别地，的充分必要条件是． （2）设模的阶为，则数列，模是周期的，且最小正周期是．而个数模互不同余． （3）设，则模的阶整除欧拉函数．特别地，若是素数，则模的阶整除． 3、欧拉定理 设，则． 4、费马小定理 设是素数，，则．或表述为，是素数，则对任意整数有，． 5、威尔逊定理 是素数则． 6、中国剩余定理 （1）设，则一次同余方程有解的充分必要条件是 （2）中国剩余定理 设是两两互素的正整数，则对于任意整数，一次同余方程组 必有解，且全部解是模的一个同余类： ，其中 【典型例题】 题型一：同余问题 【例1】（2025·山东烟台·一模）设是一个项数为的数列，其中每一项均为集合中的元素.定义数列如下：若，则，其中，当时，，当时，，且. (1)若数列，求数列； (2)若存在，对任意，均有数列与为同一数列，则称为数列组的一个周期. （i）若，求数列组的最小正周期； （ii）若数列组存在周期，求的所有可能取值. 【解析】（1）由，对于，则， 同理，， 所以，对于，则， 同理，， 所以，依上的过程，易知； （2）（i）若，，则，记， 若，，则，记， 若，，则，记， 令，各不相同， 则， 若，则，，，显然，即是周期； 若，则，，，显然，即是周期； 若，则，即是周期；（注意为正整数）， 综上，对任意，为数列组周期，最小正周期是3； （ii）当为偶数，不妨设，则，为正整数， 此时不存在正整数，使得数列与为同一数列，即数列组不存在周期； 当为奇数，由的每一项均为中元素，所以至多有个， 对于给定的，总存在，，使得， 下证：若时，， 事实上，设表示除以的余数， 由数列到的变换结果，知，， 不妨设，， 由，则，， 所以， 即， 结合为奇数，，，可得，则， 同理可证：对任意，均有，所以， 以此类推，有，，， 所以，对于任意均存在整数，使得， 在变化时，所有的最小公倍数，即为数列组的一个周期， 综上，数列组均存在周期时，的所有可能取值为且. 【点睛】关键点点睛：第二问，一小问，注意，各不相同，有，二小问，讨论的奇偶性，其中为奇数的情况下证明时，为关键. 【变式1-1】（23-24高三下·北京·强基计划）求 模 7 的余数. 【解析】因为，所以 ， 上述中用到，，所以. 【变式1-2】（24-25高三上·全国·阶段练习）如果和除以所得余数相同，则称对模同余，记作， 若集合，集合，现从集合中的个数中可以抽出个数， （）且，使这个数平均分为组，若存在一组数对 (三者不相等）且满足恰好能被整除，对模同余，则为“灵魂莲华集合”，为“灵魂莲华数对” (1)判断为“灵魂莲华集合” (2)若，判断有多少组数对为灵魂莲华数对 (3)现从素数集合中任取三个不同的数，若构成公差为8的等差数列，求证：无论且为任何集合，最多有一对满足条件的为灵魂莲华数对． 【解析】（1）是灵魂莲华集合，证明：从取，而 ，因此是灵魂莲华集合； （2）不妨设这组数为，且， 第一种情况：若 ，则只能是偶数， 由于样本数量并不大，不妨直接枚举寻找规律，单独分析和， 而我们知道模5只能余，若余0，则 ， 有以上六种情况，而的偶数有9个，由乘法原理可知此时一共有 组，减去或的情况，共有组， 若余1，除以5余1的有四个，也就是四个数相互组合，共有种， 有种， 若余2，除以5余2的有四个，减去12种，种， 若余3，除以5余3的有，同上有96组， 若余4，除以5余4的有三个，因此有组，种， 所以时，有. 第二种情况：只能是，而模2只能余0或1， 模2余0的有9个数，因此，此时共有组数， 减去有10的情况，从共有16组组合，组， 模2余1的有9个数，同上有216组 减去有5或15的情况，有30组，因此组，因此第二种情况有386组， 综上所述，共有组数； （3），由于等价，设为偶数，且为素数，则只能为2， 因此不是素数，因此不满足题意，此时不存在， 若为奇数，，则只能为3，下面来证明： 不妨设这三个数分别为， 令，因此可遍布所有整数， 第一种情况，，则，若为素数，则， 这三个数分别为满足题意， 第二种情况，，因此不是素数， 第三种情况，，则，因此不是素数， 综上，必须满足条件中，必须为1或3，而 才为灵魂莲华数对， 若均，则均无法整除，此时不存在， 若或3，但11和19对模不同余，此时也不是灵魂莲华数对， 故综上所述，是灵魂莲华数对. 【点睛】方法点睛：这是一道新运算类的题目，其特点一般是“新”而不“难”，处理的方法一般为：根据新运算的定义，将已知中的数据代入进行运算，易得最终结果． 题型二：费马小定理与欧拉定理 【例2】（23-24高三下·河北·开学考试）设a，b为非负整数，m为正整数，若a和b被m除得的余数相同，则称a和b对模m同余，记为． (1)求证：； (2)若p是素数，n为不能被p整除的正整数，则，这个定理称之为费马小定理．应用费马小定理解决下列问题： ①证明：对于任意整数x都有； ②求方程的正整数解的个数． 【解析】（1）因为， 所以被7除所得的余数为1， 所以被7除所得的余数为2， 又65被7除所得的余数为2， 所以. （2）①当能被13整除时，可以被13整除即； 当不能被13整除时，由费马小定理得即； 所以； 又， 所以， 同理：，， 因为都为素数，， 所以 ②因为， 由整除的性质及费马小定理知，对于任意正整数都有， 即， 由整除的性质及费马小定理知，对于任意正整数都有， 即， 因为5和7互为质数，所以对于任意的正整数都有 所以方程的正整数解的个数为无数个. 【点睛】关键点睛：本题的关键是充分理解新定义，然后结合带余除法以及费马小定理等初等数论知识即可顺利求解. 【变式2-1】（2024高三下·上海·竞赛）数列满足：是大于1的正整数，试证明：在数列中存在相邻的两项，它们除以余数相同. 【解析】设除以为余数为.构造有序数对的序列:       注意到,则序列中至多有个不同的项, 根据抽屉原理,在序列的前项中必有相同的两项,不妨设为 由于, 于.继续上述过程,可以得到. 又,,显然,所以且. 综上,在数列中存在相邻的两项,它们除以的余数相同. 【点睛】根据抽屉原理反复迭代构造. 【变式2-2】（2023高三·全国·专题练习）已知素数证明：为整数，其中． 【解析】证明：由Fermat小定理知，则所以． 又所以．即，于是，从而．即 于是． 下面只需要证明即可． 引理：设是正整数，则 回到原题， 注意到且均为素数，所以 于是．即为整数． 题型三：中国剩余定理 【例3】（23-24高一上·云南昆明·开学考试）“物不知数”是中国古代著名算题，原载于《孙子算经》卷下第二十六题：“今有物不知其数，三三数之剩二：五五数之剩三；七七数之剩二．问物几何？”问题的意思是，一个数被3除余2，被5除余3，被7除余2，那么这个数是多少？若一个数被除余，我们可以写作．它的系统解法是秦九韶在《数书九章》大衍求一术中给出的．大衍求一术（也称作“中国剩余定理”）是中国古算中最有独创性的成就之一，现将满足上述条件的正整数从小到大依次排序．中国剩余定理：假设整数，，…，两两互质，则对任意的整数：，，…，方程组一定有解，并且通解为，其中为任意整数，，，为整数，且满足． (1)求出满足条件的最小正整数，并写出第个满足条件的正整数； (2)在不超过4200的正整数中，求所有满足条件的数的和．（提示：可以用首尾进行相加）． 【解析】（1）由题目中给出的中国剩余定理可知， 又因为，解得， 所以， 当时，取得最小值，． 所以第个满足条件的正整数为． （2）不超过4200的正整数中，，解得， 所以共有40个满足条件的正整数，将这40个正整数首尾进行相加有 ， 故所有满足条件的数的和为82820． 【点睛】关键点点睛：本题第一问的关键是充分理解剩余定理，从而得到方程组，解出相关值，再计算出即可. 【变式3-1】（2023高三·全国·专题练习）证明：对任意正整数，存在个连续正整数，它们中每一个数都不是素数的幂． 【解析】证明：若能找到个连续正整数，它们中的每一个数都有两个不同的素因子，则命题得证． 为此取个不同的素数 考虑同余方程组 因为显然两两互素，故由中国剩余定理知上述同余方程组有正整数解 于是连续个数中每一个数都有两个不同的素因子．命题得证． 【变式3-2】（2023高三·全国·专题练习）解同余方程组． 【解析】两两互素，则由中国剩余定理知道有唯一解． 取 取 取 所以 题型四：阶与原根 【例4】（2021高三·全国·竞赛）设为一个质数，且也是一个质数，证明：的小数表示形式中包含0至9的所有数码． 【解析】令为质数，由费马小定理可知， 设10模q的阶为d，则，从而， 注意到，故． 由于且为长度不超过d位的整数， 故是循环节长度为d位的纯循环小数，且循环节为（若长度不够则补为d位）在十进制下表示的数码节． 设模q的余数为，记，由于10模q的阶为d， 于是我们得到互不相同， 注意到相当于将的小数点向右移动了k位，故的小数点后的第一位必定出现在的循环节中， 也即的小数点后的第一位必定出现在的循环节中． 设g为模q的原根，则构成模q的缩系，故存在x，使得． 若10模q的阶为p，则，由原根及阶的最小性可知，也即， 设，则显然（否则若则可知）， 于是模两两不同余且均为4的倍数， 故， 于是由可知S是由模q的所有四次剩余构成的集合； 类似的若，则S是由模q的所有二次剩余构成的集合； 若，则S是由模q的缩系． 从而无论哪种情况，集合S均包含模q的所有四次剩余． 下面考虑所有不超过q的四次方程：，显然这些数均在集合S中． 我们证明：对任意，存在正整数k使得，也即的小数点的首位数字为， 从而表明存在，使得的小数点后的首位数字为t， 进而说明t出现在的循环节中． 事实上，显然，， 注意到，故每次变化的步长： ， 故必定经过的每一个区间， 也即对任意，均存在正整数k使得，结论成立． 综上，结论成立． 【变式4-1】（2019高三·全国·竞赛）设是的十进制写法中最后一个非零数字．证明：0·…是无理数． 【解析】设是有理数．则存在、，使得对每个，均有． 首先证明：存在，，且的最后一个非零数字为1． 事实上，设，其中，、，不被2与5整除． 则的最后一个非零数字为奇数，且不等于5． 若其等于1，则取；若其等于3，则取； 若其等于7，则取；若其等于9，则取． 在以上情形下，的最后一位非零数字分别与1、21、21、81的相同． 这样就求出了当时使得的数． 其次证明：对任意的，． 事实上，记表示不超过实数的最大整数． 则在的素因子分解式中，2的幂指数为， 5的幂指数为． 因为当时，，所以，，且， 其中，，不被2与5整除．从而，其最后一位非零数字与的相同． 于是，不等于5，即最后取充分大的，使得． 记．则． 故． 因此，． 因为，所以，． 从而，． 故 ， 即与的最后一位数字相同． 另一方面，，但是，因为，所以，的最后一位数字不等于． 从而，，矛盾． 【强化训练】 1．（2023高三·全国·专题练习）求证：为任意整数． 【解析】证明：令，则， 都是的因式．于是由费尔马小定理可知，， 又两两互素，且，所以． 2．（2023高三·全国·专题练习）设是正整数， (1)证明： (2)证明： (3)证明： 【解析】证明：（1）当时结论成立． 当时，设的素因数分解式 结论成立． （2） 显然所以得证． （3）当时，显然成立． 当素数，所以结论成立． 当，为不含平方因数的整数，若则 则，，结论成立． 所以 3．（2023高三·全国·专题练习）若证明： 【解析】证明：因为跑遍模的简系， 跑遍模的简系．则跑遍模的简系． 所以模的简系个数等于跑过的个数，跑过的个数为模的简系个数，跑过的个数为模的简系个数．于是跑过的个数为 即 4．（2023高三·全国·专题练习）若跑遍模的完系， 跑遍模的完系．证明：跑遍模的完系． 【解析】证明：我们知道跑遍模的完系，则跑过个数，跑遍模的完系，则跑过个数， 于是跑过个数． 假设，其中是模的完系中的数，是模的完系中的数．于是， 因为所以所以 这表明跑遍模的完系． 若则由得 于是 所以 反之，若则 于是所以 这就证明了所要的结论． 5．（2023高三·全国·专题练习）已知数列满足. (1)证明：是正整数数列； (2)是否存在，使得？并说明理由. 【解析】（1）数列满足，则，，且， 有，两式相减得，因此数列为常数数列， 于是，则，又，，因此， 所以是正整数数列. （2）因为，假设有，则必有， 又，则，由费马小定理得，矛盾， 所以不存在，使得. 6．（2023高三·全国·专题练习）已知数列满足. (1)证明：是正整数数列； (2)是否存在，使得？并说明理由. 【解析】（1）由得， 得，则， 故①，②， 由①②可知，为方程的两根， 所以，即， 因为，所以为正整数， 所以是正整数数列. （2）不存在，使得，理由如下： 假设存在，使得，则. 一方面，，所以，即， 所以. 由费马小定理知，所以， 另一方面，. 事实上，假设，则，即，所以，而，这样得到.矛盾. 所以由费马小定理得. 这样得到，矛盾， 所以不存在，使得. 7．（2024高三·全国·专题练习）已知函数，，，，求证：． 【解析】证明：根据题意，不妨设，由拉格朗日中值定理知，, ，使得, 因此要证明，只要证明在区间内恒成立即可， 因为，所以． 令，则． 当时，，即在上单调递增； 当时，，即在上单调递减． 所以，所以， 所以． 8．（2024高三·全国·专题练习）设，证明： ． 【解析】证明： 设，，显然在满足拉格朗日中值定理的条件， 则，使得， 而，所以． 由知在上单调递增， 从而有 即有. 9．（2023高三·全国·专题练习）设证明：存在使得同余方程在模的意义下至少有个根． 【解析】证明：对于任意的素数，同余方程可化为．所以恰好有两个不同的解． 现在任取个不同的奇素数，这里的满足令． 考虑个不同的数组，其中． 由中国剩余定理方程组有唯一解（在模的意义下）． 此解满足，也就是满足 若两个不同的数组，则必存在使得不妨设 于是与不同解． 于是． 从而． 这就证明了至少有个解． 所以存在存在使得同余方程在模的意义下至少有个根． 10．（2024高三上·全国·专题练习）已知，， (1)若在处取得极值，试求的值和的单调增区间； (2)如图所示，若函数的图象在连续光滑，试猜想拉格朗日中值定理：即一定存在，使得，利用这条性质证明：函数图象上任意两点的连线斜率不小于． 【解析】（1）因为，则， 依题意，有，即． 所以，， 令，得或， 令，得， 所以在和上单调递增，在上单调递减， 所以满足题意，同时，的单调增区间为和； （2）猜想如下： 因为表示的两端点连线的斜率， 而由题可知，上必然存在点，使得其切线的斜率为，即， 所以一定定存在，使得； 证明如下： 因为， 则． 由猜想可知，对于函数图象上任意两点， 在之间一定存在一点，使得， 又，故有. 11．（2023高三·全国·专题练习）求所有的正整数，使得为完全平方数． 【解析】， 所以为偶数，可设， ， （注意到不能太大，否则，不为完全平方数） 即要求，， 用数学归纳法证明当时，不成立，所以， 逐一验证即可， 当时，不是完全平方数； 当时，，此时； 当时，不是完全平方数，此时； 当时，， 此时模4并不能否定它是完全平方数，所以我们再多加考虑几个模，考虑3，5，7，9其中3没有意义，如果都考虑到后任然排除不了，我们只能把它算出来了．（这里没有考虑6，8，10这是因为本身就是能被4整除的，所以模6和模3效果是一样的）， ，，， 排除不掉，但是不可能， 当时，， ，不可能， 当时，，，不可能， 因此唯一符合题意的． 12．（2023高三·全国·专题练习）（1）求证：是正奇数时，能被整除． （2）是自然数，它不能被整除，求证：与中有且只有一个数被整除． 【解析】（1）证明：当是自然数时，， 当是正奇数时，， 由于，所以， 类似，所以 ，所以， 因为，两两互素，故 （2）证明：由是素数，不能被整除，则．   由费尔马小定理，得，即， 则，故或 但是，不能被整除， 所以与中有且只有一个数被整除． 2 学科网（北京）股份有限公司 $$