同余问题

求14389除以7的余数。 解：同余的性质能使\"大数化小\"，凡求大数的余数问题首先考虑用同余的性质化大为小.这道题先把底数在同余意义下变小，然后从低次幂入手，重复平方，找找有什么规律。 解法1：∵143≡3（mod7） ∴14389≡389（mod 7） ∵89＝64+16+8+1 而32≡2（mod 7）， 34≡4（mod7），

8

3≡16≡2（mod 7）， 316≡4（mod 7）， 332≡16≡2（mod 7）， 364≡4（mod 7）。 ∵389≡364·316·38·3≡4×4×2×3≡5（mod 7）， ∴14389≡5（mod 7）。

答：14389除以7的余数是5。 解法2：证得14389≡389（mod 7）后， 36≡32×34≡2×4≡1（mod 7）， ∴384≡（36）14≡1（mod 7）。 ∴389≡384·34·3≡1×4×3≡5（mod 7）。 ∴14389≡5（mod 7） 小学六年级奥数题——同余问题

1.若a为自然数，证明10│（a2005－a1949）．

2.给出12个彼此不同的两位数，证明：由它们中一定可以选出两个数，它们的差是两个相同数字组成的两位数．

3.求被3除余2，被5除余3，被7除余5的最小三位数．

4.设2n＋1是质数，证明：12，22，…，n2被2n＋1除所得的余数各不相同． 5.试证不小于5的质数的平方与1的差必能被24整除． 参考答案：

1.提示：对于任何自然数a，a5与a的个位数字相同． 2.提示：有两个数的差能被11整除 3.173

4.分析这道题肯定不可能通过各数被2n＋1除去求余数．那么我们可以考虑从反面入手，假设存在两个相同的余数的话，就会发生矛盾．而中间的推导是步步有根据的，所以发生矛盾的原因是假设不合理．从而说明假设不成立，因此原来的结论是正确的．

证明：假设有两个数a、b，（a≠b，设b那么，由同余定义得a2－b2≡0（mod（2n＋1））．

即（a＋b）（a－b）≡0（mod（2n＋1）），由于2n＋1是质数． ∴a＋b≡0（mod（2n＋1））或a－b≡0（mod（2n＋1））．

由于a＋b，a－b均小于2n＋1且大于零，可知，a＋b与2n＋1互质，a－b也与2n＋1互质．即a＋b与a－b都不能被2n＋1整除．产生矛盾，∴原题得证．

说明：这里用到一个重要的事实：如果A·B≡0（modp），p是质数，那么A或B中至少有一个模p为零．p是质数这一条件不能少，否则不能成立。例如2·3≡0（mod6），但2、3被6除余数不为0。

5.证明：∵质数中仅有一个偶数2，∴不小于5的质数是奇数．又不小于5的自然数按除以6所得的余数可分为6类：6n，6n＋1，6n＋2，6n＋3，6n＋4，6n＋5，（n是自然数），其中6n，6n＋2，6n＋4都是偶数，又3│6n＋3． ∴不小于5的质数只可能是6n＋1，6n＋5．

又自然数除以6余数是5的这类数换一记法是：6n－1， ∴（不小于5的质数）2－1＝（6n±1）2－1 ＝36n2±12n＝12n（3n±1），

这里n与（3n±1）奇偶性不同，其中定有一个偶数， ∴2│n（3n±1），∴24│12n（3n±1）．∴结论成立． 说明：按同余类造抽屉是解竞赛题的常用方法．