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