同余問題

　　求143⁸⁹除以7的余數。

　　解： 同余的性質能使"大數化小"，凡求大數的余數問題首先考慮用同余的性質化大為小.這道題先把底數在同余意義下變小，然后從低次冪入手，重復平方，找找有什么規律。

　　解法1：∵143≡3（mod7）

　　∴143⁸⁹≡3⁸⁹（mod 7）

　　∵89＝64+16+8+1

　　而3²≡2（mod 7），

　　3⁴≡4（mod7），

　　3⁸≡16≡2（mod 7），

　　3¹⁶≡4（mod 7），

　　3³²≡16≡2（mod 7），

　　3⁶⁴≡4（mod 7）。

　　∵3⁸⁹≡3⁶⁴·3¹⁶·3⁸·3≡4×4×2×3≡5（mod 7），

　　∴143⁸⁹≡5（mod 7）。

　　答：143⁸⁹除以7的余數是5。

　　解法2：證得143⁸⁹≡3⁸⁹（mod 7）后，

　　3⁶≡3²×3⁴≡2×4≡1（mod 7），

　　∴3⁸⁴≡（3⁶）14≡1（mod 7）。

　　∴3⁸⁹≡3⁸⁴·3⁴·3≡1×4×3≡5（mod 7）。

　　∴143⁸⁹≡5（mod 7）。