孫浩

【摘要】若兩個(gè)整數(shù)A、B被自然數(shù)m除有相同的余數(shù)，那么稱A、B對于模m同余，用式表示為A≡B（modm）.

【關(guān)鍵詞】余數(shù);模;整除

同余有如下性質(zhì)：

（2）反身性：a≡a（modm）.

（3）傳遞性：a≡b（modm），b≡c（modm）

?a≡c（modm）.

（4）對稱性：a≡b（modm）?b≡a（modm）.

（5）可加性：a≡b（modm），c≡d（modm）

?a+c≡b±d（modm）.

等.

例1一個(gè)三位數(shù)被37除余3，被36除余7，求這個(gè)三位數(shù).

解設(shè)這個(gè)三位數(shù)為n，

由條件可知

n=37a+3=36a+（a+3），

所以n÷36的余數(shù)等于（a+3）÷36的余數(shù).

再令（a+3）÷36的商為b，

則a+3=36b+7，a=36b+4，

代入得n=37×（36b+4）+3=1332b+151，

由n是三位數(shù)，知b=0，n=151.

例2某數(shù)被5除余2，被7除余6，被11除余9，求該數(shù)的最小值.

解這個(gè)數(shù)加8，能同時(shí)被5和7整除，除以11余6，

5，7的最小公倍數(shù)是35，

35÷11=3……2，2×3=6，

即35×3=105除以11余6，

所以數(shù)最小為105-8=97.

另解7和11的公倍數(shù)中被5除余1的最小數(shù)是231;

5和11的公倍數(shù)中被7除余1的最小數(shù)是330;

5和7的公倍數(shù)中被11除余1的最小數(shù)是210.

要求的數(shù)被5，7，11除的余數(shù)分別是2，6，9，

由剩余定理可得

231×2+330×6+210×9

=462+1980+1890=4332，

5，7，11的最小公倍數(shù)是385，

4332÷385=11……97，

故最小的數(shù)是97.

例3被7除余2、被8除余3、被9除余3的數(shù)最小是________.

解由題意知余數(shù)不同，但余數(shù)的補(bǔ)數(shù)相同，

即7-2=8-3=5，

于是a+5是7和8的倍數(shù)，也就是56的倍數(shù)，

所以a+5=56n（n是正整數(shù)），

即a=56n-5，

又a被9除余3，

所以a可表示為a=9k+3（k是正整數(shù)），

即9k+3=56n-5，

即2n-8是9的倍數(shù)，

所以n=4，13，22，…，

所以a=219為最小.

另解7和8的公倍數(shù)中被9除余1的最小數(shù)是280;

7和9的公倍數(shù)中被8除余1的最小數(shù)是441;

8和9的公倍數(shù)中被7除余1的最小數(shù)是288.

要求的數(shù)被7，8，9除的余數(shù)分別是2，3，3，

由剩余定理可得

280×3+441×3+288×2

=840+1323+576=2739，

7，8，9的最小公倍數(shù)是504，

2739÷504=5……219，

故最小的數(shù)是219.

解因?yàn)?019=7×288+3，

所以2019²⁰²²≡3²⁰²²（mod7），

3²⁰²²=（3³）⁶⁷⁴=27⁶⁷⁴，

又27=4×7+（-1），

所以3²⁰²²=27⁶⁷⁴≡（-1）⁶⁷⁴=1（mod7），

例5質(zhì)數(shù)p>5，求336除7p⁴+5得到的余數(shù).

解分解質(zhì)因數(shù)336=2⁴×3×7.

因?yàn)椋╬²+1）（p+1）（p-1）=p⁴-1，

又質(zhì)數(shù)p>5，

所以p必為奇數(shù)，

于是（p²+1），（p+1），（p-1）都是偶數(shù).

設(shè)p=2k-1，其中k為整數(shù)，

則p+1=2k，p-1=2k-2，

（p+1）（p-1）=2²k（k-1），

設(shè)p=3k±1，其中k是整數(shù)，

因?yàn)?p⁴+5=7（p⁴-1）+12，

故336除7p⁴+5，得余數(shù)12.

例6若自然數(shù)x除以3余2，除以4余3，除以5余4，則x除以15所得余數(shù)是________.

分析由3-2=4-3=5-4=1，知x+1能被3×4×5整除.

解法1由x除以3余2，除以4余3，除以5余4，

知x+1能被60整除.

設(shè)x+1=60k（k為整數(shù)），則

x=60k-1=15×（4k）-1=15×（4k-1）+14，

因此，所求的余數(shù)是14.

解法2只須找出一個(gè)除以3余2，除以4余3，除以5余4的數(shù)即可求得解答.

除以3余2的數(shù)的形式是3m+2（m是自然數(shù)），如

5，8，11，14，17，20，23，26，29，32，35，……

以上這些數(shù)中，除以4余3的數(shù)有

11，23，35，47，59，……

這些數(shù)中，除以5余4的第一個(gè)數(shù)是59.

而59除以15得余數(shù)14，即為所求.

例7x是三位自然數(shù)，x÷3，x÷5，x÷7的余數(shù)都是2，求x的個(gè)數(shù).

解因?yàn)閤=3×5×7×n+2=105n+2，

又100≤x≤999，

所以100≤105n+2≤999，

故n=1，2，3，…，9，共9個(gè).

例82016年1月20日發(fā)現(xiàn)了第49個(gè)梅森素?cái)?shù)2^74207281-1（可記為M₄₉或M74207281），它是迄今為止所知道的最大素?cái)?shù)，是一個(gè)22338618位數(shù)，求該素?cái)?shù)的末兩位數(shù).

解先求個(gè)位數(shù)：

因?yàn)?^74207281-1=2×4^37103640-1

=2×16^18551820-1≡2×6-1≡1（modl0），

所以2^74207281-1的個(gè)位數(shù)字是1.

再求十位數(shù)：

=3（16^18551829+16^18551818+…+16+1）

≡3×（6×188551819+1）

≡3×（4+1）

≡5（modl0），

所以2^74207281-1的十位數(shù)字是5.

因此2^74207281-1的末兩位數(shù)是51.