同余式及其应用

孙浩

【摘要】若两个整数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.