第11講同余基本理論（原卷版）

第11講同余基本理論【考點(diǎn)預(yù)測(cè)】同余理論是初等數(shù)論的重要組成部分，是研究整數(shù)問題的重要工具之一，利用同余來(lái)論證某些整除性的問題是很簡(jiǎn)便的．【定義1】設(shè)是大于1的正整數(shù)，是整數(shù)，如果，則稱與關(guān)于模同余，記作，讀作同余模．顯然，有如下事實(shí)：（1）若，則；（2）分別用去除與，余數(shù)相同．【定理1】設(shè)都是整數(shù)，則有（1）反身性；（2）若，則對(duì)稱性；（3）若，，則傳遞性．【定理2】設(shè)，，則（1）；（2）．【推論1】若，則（1）；（2）．【推論2】若，則．【定理3】若，且，則．【推論3】若，且，則．注意這一條件，當(dāng)時(shí)，此性質(zhì)不成立，如，但．【定理4】若，且，則．【定義2】設(shè)．把全體整數(shù)按其對(duì)模的余數(shù)歸于一類，記為．每一類均稱為模的剩余類(又叫同余類)．由定義知，即，．它是一個(gè)公差為的(雙邊無(wú)窮的等差數(shù)列．根據(jù)定義，剩余類具有如下性質(zhì)：（1），且；（2）對(duì)任一數(shù)，有唯一的使；（3）對(duì)任意的．【定義3】設(shè)是模的全部剩余類，從每個(gè)中任取一個(gè)數(shù)，這個(gè)數(shù)，組成的一個(gè)數(shù)組稱為模的一個(gè)完全剩余系，簡(jiǎn)稱完系．顯然，模的完系有無(wú)窮多個(gè)，但最常用的有（1）非負(fù)最小完系．（2）絕對(duì)值最小完系：當(dāng)為奇數(shù)時(shí)，有；當(dāng)為偶數(shù)時(shí)，有．由定義不難得到如下判別完系的方法：【定理5】個(gè)整數(shù)是模的一個(gè)完系的充要條件是．【定義6】若是模的完系，則也是模的完系．【定理7】若是模的完系，，則也是模的完系．【定義4】如果一個(gè)模的剩余類中任一數(shù)與互質(zhì)，則稱是與?；ベ|(zhì)的剩余類；在與?；ベ|(zhì)的每個(gè)剩余類中任取一個(gè)數(shù)共個(gè))所組成的數(shù)組，稱為模的一個(gè)簡(jiǎn)化剩余系，簡(jiǎn)稱簡(jiǎn)系．由此定義不難得到：【定理8】是模的簡(jiǎn)系的充要條件是且，．【定理9】在模的一個(gè)完系中，取出所有與互質(zhì)的數(shù)組成的數(shù)組就是一個(gè)模的簡(jiǎn)系．質(zhì)數(shù)模的最小非負(fù)簡(jiǎn)系為．【定理10】若，且是模的簡(jiǎn)系，則也是模的簡(jiǎn)系．剩余類與完系、簡(jiǎn)系在解題中的應(yīng)用是十分廣泛的．歐拉定理設(shè)，則．費(fèi)馬小定理設(shè)為質(zhì)數(shù)，，則．威爾遜(Wilson)定理設(shè)是素?cái)?shù)，則．中國(guó)剩余定理設(shè)，而是個(gè)兩兩互質(zhì)的正整數(shù)，令，則下列同余式組：的正整數(shù)解是．其中，滿足．【定理11】設(shè)為質(zhì)數(shù)，為兩個(gè)正整數(shù)，且在進(jìn)制下，分別為，．求證：．【定理12】在中，有個(gè)數(shù)是的倍數(shù)，有個(gè)為的倍數(shù)，為的倍數(shù)．所以在中的指數(shù)為．【典例例題】例1．（2019·全國(guó)·高三競(jìng)賽）對(duì)給定的正整數(shù)，定義表示的各個(gè)數(shù)位上的數(shù)字之和的平方，當(dāng)且時(shí)，表示的各個(gè)數(shù)位上的數(shù)字之和的次方，其中，當(dāng)為奇數(shù)時(shí)，；當(dāng)為偶數(shù)時(shí)，，試求的值．例2．（2019·全國(guó)·高三競(jìng)賽）設(shè)整數(shù)滿足，證明：.例3．（2019·全國(guó)·高三競(jìng)賽）四位數(shù)和互為反序的正整數(shù)，且，、分別有16個(gè)、12個(gè)正因數(shù)（包括1和本身），的質(zhì)因數(shù)也是的質(zhì)因數(shù)，但的質(zhì)因數(shù)比的質(zhì)因數(shù)少1個(gè)，求的所有可能值.例4．（2021·全國(guó)·高三競(jìng)賽）對(duì)每個(gè)正整數(shù)n，定義為從1到n中所有與n不互質(zhì)的正整數(shù)的和.求證：若且，則是合數(shù).例5．（2021·全國(guó)·高三競(jìng)賽）正整數(shù)，且的素因子個(gè)數(shù)不超過2，對(duì)于任意整數(shù)，若，則有成立，求證：是質(zhì)數(shù).例6．（2019·吉林·高三校聯(lián)考競(jìng)賽）求所有的正整數(shù)n，使得方程有正整數(shù)解.例7．（2019·上海·高三校聯(lián)考競(jìng)賽）求證：不存在無(wú)窮多項(xiàng)的素?cái)?shù)數(shù)列，使得.例8．（2023·全國(guó)·高三專題練習(xí)）試證明對(duì)函數(shù)應(yīng)用拉格朗日中值定理時(shí)所求得的點(diǎn)總是位于區(qū)間的正中間．例9．（2023·全國(guó)·高三專題練習(xí)）已知函數(shù)在區(qū)間上滿足拉格朗日中值定理的條件，試求滿足定理的．例10．（2021·全國(guó)·高三競(jìng)賽）對(duì)于正整數(shù)n，記與的最大公因子為，若，則稱n是奇異的．證明：若n是奇異的，則也是奇異的．例11．（2019·江蘇·高三校聯(lián)考競(jìng)賽）設(shè)k、l、c均為正整數(shù)，證明：存在正整數(shù)a、b滿足，且，其中(a，b)表示a、b的最大公因數(shù)，表示正整數(shù)m的所有不同正因子的個(gè)數(shù).例12．（2018·全國(guó)·高三競(jìng)賽）已知個(gè)兩兩互質(zhì)的正整數(shù)滿足：可以適當(dāng)添加“+”或“-”使得其代數(shù)式的和為0.問：是否存在一組正整數(shù)（允許有相同的），使得對(duì)任意正整數(shù)，都有兩兩互質(zhì).例13．（2018·全國(guó)·高三競(jìng)賽）設(shè).證明：存在,使得同余方程至少有個(gè)根.【過關(guān)測(cè)試】1．（2022·上海·高三?？紡?qiáng)基計(jì)劃）定義，其中為奇素?cái)?shù).(1)給出同余方程的滿足的一組解；(2)（代數(shù)基本定理）設(shè)，且，求證在內(nèi)至多有個(gè)解；(3)（小定理）求證：；(4)（原根存在定理）若正整數(shù)滿足：，且，則記，則稱為在意義下的階，求證：必定存在，有；(5)求證，存在，都存在中必有一者成立；(6)說明當(dāng)時(shí)，必有一組非零解.2．（2020·北京·高三強(qiáng)基計(jì)劃）求證：對(duì)任意正整數(shù)k，均存在n為k的倍數(shù)，且n的十進(jìn)制表示以2020開頭．3．（2021·江蘇·高三強(qiáng)基計(jì)劃）求能使表示為兩整數(shù)平方之和的所有n的值（）．4．（2021·全國(guó)·高三競(jìng)賽）設(shè)為n個(gè)正整數(shù)，并且滿足，令，并記.求證：對(duì)于任意，必存在正整數(shù)u、v，使得，等于A或.5．（2021·全國(guó)·高三競(jìng)賽）已知是兩個(gè)整數(shù)集合，且對(duì)于任意整數(shù)，存在唯一的使得.記.證明：對(duì)任意的，存在，使得.6．（2021·浙江·高三競(jìng)賽）已知素?cái)?shù)，滿足.證明：存在正整數(shù)使得的十進(jìn)制表示的各位數(shù)字之和是2或3.7．（2021·浙江·高三競(jìng)賽）給定素?cái)?shù).稱1，2，…，的排列為“好排列”，如果對(duì)，2，…，均有，并且是的倍數(shù).求“好排列”的個(gè)數(shù)除以的余數(shù).8．（2021·全國(guó)·高三競(jìng)賽）一個(gè)大于1的整數(shù)m，如果對(duì)所有的正整數(shù)n，都存在正整數(shù)x、y、z，使得，則稱m為上數(shù)，否則稱為下數(shù)．試問：是否存在無(wú)數(shù)多的上數(shù)？是否存在無(wú)數(shù)多的下數(shù)？9．（2020·全國(guó)·高三競(jìng)賽）設(shè)a，b為不超過12的正整數(shù)，滿足：存在常數(shù)C，使得對(duì)任意正整數(shù)n成立．求所有滿足條件的有序數(shù)對(duì)．10．（2018·全國(guó)·高三競(jìng)賽）對(duì)于素?cái)?shù)p，定義集合.及.試求所有的素?cái)?shù)p，使得.11．（2018·全國(guó)·高三競(jìng)賽）設(shè)，定義：，.證明：當(dāng)時(shí)，為整數(shù)，且為奇數(shù)當(dāng)且僅當(dāng)或2.12．（2018·全國(guó)·高三競(jìng)賽）設(shè)是一個(gè)大于1的正整數(shù)，是素?cái)?shù)，.(1)證明：或；(2)若是不同于的素?cái)?shù)，則恰有個(gè)不同的解（即模互不同余）.13．（2018·全國(guó)·高三競(jìng)賽）已知正整數(shù)滿足，.令，，.對(duì)任意的，記，其中，表示不超過實(shí)數(shù)的最大整數(shù)，表示集合中元素的個(gè)數(shù).證明：（1）；（2）.14．（2018·全國(guó)·高三競(jìng)賽）求所有正整數(shù)、使得多項(xiàng)式在某三個(gè)相繼整數(shù)處均取整數(shù)值．15．（2018·全國(guó)·高三競(jìng)賽）已知、、、、、為整數(shù)，方程①有正整數(shù)解．證明：存在無(wú)窮多個(gè)正整數(shù)使得．16．（2018·全國(guó)·高三競(jìng)賽）設(shè)，問：是否存在正整數(shù)，使如果存在，試求出最小的正整數(shù)；如果不存在，請(qǐng)說明理由．17．（2019·全國(guó)·高三競(jìng)賽）試求所有的正整數(shù)，滿足存在一個(gè)整數(shù)，使得是的一個(gè)因數(shù)．18．（2019·全國(guó)·高三競(jìng)賽）已知數(shù)列滿足，．給定奇質(zhì)數(shù)和正整數(shù)滿足，證明：的充分必要條件為．19．（2019·全國(guó)·高三競(jìng)賽）從左到右依次寫出1到10000的全部正整數(shù)，然后去掉那些能被5或7整除的數(shù)，將