同余式及其應用

孫浩

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

【關鍵詞】余數;模;整除

同余有如下性質：

（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一個三位數被37除余3，被36除余7，求這個三位數.

解設這個三位數為n，

由條件可知

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

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

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

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

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

由n是三位數，知b=0，n=151.

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

解這個數加8，能同時被5和7整除，除以11余6，

5，7的最小公倍數是35，

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

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

所以數最小為105-8=97.

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

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

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

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

由剩余定理可得

231×2+330×6+210×9

=462+1980+1890=4332，

5，7，11的最小公倍數是385，

4332÷385=11……97，

故最小的數是97.

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

解由題意知余數不同，但余數的補數相同，

即7-2=8-3=5，

于是a+5是7和8的倍數，也就是56的倍數，

所以a+5=56n（n是正整數），

即a=56n-5，

又a被9除余3，

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

即9k+3=56n-5，

即2n-8是9的倍數，

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

所以a=219為最小.

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

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

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

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

由剩余定理可得

280×3+441×3+288×2

=840+1323+576=2739，

7，8，9的最小公倍數是504，

2739÷504=5……219，

故最小的數是219.

解因為2019=7×288+3，

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

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

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

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

例5質數p>5，求336除7p⁴+5得到的余數.

解分解質因數336=2⁴×3×7.

因為（p²+1）（p+1）（p-1）=p⁴-1，

又質數p>5，

所以p必為奇數，

于是（p²+1），（p+1），（p-1）都是偶數.

設p=2k-1，其中k為整數，

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

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

設p=3k±1，其中k是整數，

因為7p⁴+5=7（p⁴-1）+12，

故336除7p⁴+5，得余數12.

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

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

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

知x+1能被60整除.

設x+1=60k（k為整數），則

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

因此，所求的余數是14.

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

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

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

以上這些數中，除以4余3的數有

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

這些數中，除以5余4的第一個數是59.

而59除以15得余數14，即為所求.

例7x是三位自然數，x÷3，x÷5，x÷7的余數都是2，求x的個數.

解因為x=3×5×7×n+2=105n+2，

又100≤x≤999，

所以100≤105n+2≤999，

故n=1，2，3，…，9，共9個.

例82016年1月20日發現了第49個梅森素數2^74207281-1（可記為M₄₉或M74207281），它是迄今為止所知道的最大素數，是一個22338618位數，求該素數的末兩位數.

解先求個位數：

因為2^74207281-1=2×4^37103640-1

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

所以2^74207281-1的個位數字是1.

再求十位數：

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

≡3×（6×188551819+1）

≡3×（4+1）

≡5（modl0），

所以2^74207281-1的十位數字是5.

因此2^74207281-1的末兩位數是51.