Exercise · ZW-FERMAT-S-LITTLE-THEOREM-010 · ★★★ Advanced
Find the remainder of \(2^{1000}+3^{1000}\) when divided by \(7\).
Choose one option.
Show answer
- A. \(6\)
Explanation
Since \(7\) is prime, \(2^{6}\equiv 3^{6}\equiv 1\pmod 7\). As \(1000=6\cdot 166+4\), \(2^{1000}\equiv 2^{4}=16\equiv 2\) and \(3^{1000}\equiv 3^{4}=81\equiv 4\pmod 7\), so the sum is \(6\pmod 7\). The option \(5\) is a typical error from miscomputing \(3^{4}\bmod 7\).
Review the concept: Fermat's little theorem
Fermat's little theorem states that if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then \(a^{p-1}\equiv 1 \pmod{p}\). It is a basic tool for simplifying modular powers.
\[a^{p-1}\equiv 1 \pmod{p}, \quad p\nmid a\]
More practice problems: fermat's little theorem
- ZW-FERMAT-S-LITTLE-THEOREM-001 By Fermat's little theorem, what is a^p-1 congruent to modulo p when p is prime and pnmid a?
- ZW-FERMAT-S-LITTLE-THEOREM-002 What is the value of 3^6bmod 7?
- ZW-FERMAT-S-LITTLE-THEOREM-003 If p is prime, what condition on a is needed to use a^p-1≡ 1 pmodp?
- ZW-FERMAT-S-LITTLE-THEOREM-004 What is the remainder of 5^12 when divided by 13?
- ZW-FERMAT-S-LITTLE-THEOREM-005 If p=7 and a=2, what value does a^p-1bmod p take?
- ZW-FERMAT-S-LITTLE-THEOREM-006 Compute 2^100bmod 11.
- ZW-FERMAT-S-LITTLE-THEOREM-007 Find the remainder of 3^50 when divided by 7.
- ZW-FERMAT-S-LITTLE-THEOREM-008 What is the value of 4^30bmod 13?