Subjects number theory

Modular Multiplication

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Modular Multiplication


1. **State the problem:** We need to show that $$-11100 \times 134 \equiv -1 \pmod{13}$$ without using a calculator. 2. **Reduce each number modulo 13:** Calculate $$-11100 \mod 13$$ and $$134 \mod 13$$. 3. **Calculate $$11100 \mod 13$$:** Divide 11100 by 13: $$11100 \div 13 = 853 \text{ remainder } 11$$ So, $$11100 \equiv 11 \pmod{13}$$ Therefore, $$-11100 \equiv -11 \equiv 13 - 11 = 2 \pmod{13}$$ 4. **Calculate $$134 \mod 13$$:** Divide 134 by 13: $$134 \div 13 = 10 \text{ remainder } 4$$ So, $$134 \equiv 4 \pmod{13}$$ 5. **Multiply the reduced values modulo 13:** $$(-11100) \times 134 \equiv 2 \times 4 = 8 \pmod{13}$$ 6. **Check if 8 is congruent to -1 modulo 13:** Since $$-1 \equiv 12 \pmod{13}$$ and 8 is not equal to 12, this suggests a mistake. 7. **Re-examine step 3:** Since $$-11100 \equiv -11 \pmod{13}$$, and $$-11 \equiv 2$$ is correct. 8. **Re-examine step 5:** $$2 \times 4 = 8$$, so the product modulo 13 is 8, not -1. 9. **Try reducing $$-11100$$ directly:** $$-11100 \equiv -11100 + 13 \times 854 = -11100 + 11102 = 2 \pmod{13}$$ (confirms previous result) 10. **Try reducing $$134$$ directly:** $$134 \equiv 4 \pmod{13}$$ (confirmed) 11. **Try reducing the product $$-11100 \times 134$$ directly modulo 13:** Calculate $$-11100 \times 134 = -1,487,400$$ Divide $$-1,487,400$$ by 13: $$1,487,400 \div 13 = 114,415 \text{ remainder } 5$$ So, $$-1,487,400 \equiv -5 \equiv 8 \pmod{13}$$ 12. **Conclusion:** The product modulo 13 is 8, not -1. Therefore, the original statement $$-11100 \times 134 \equiv -1 \pmod{13}$$ is incorrect. **Final answer:** $$-11100 \times 134 \equiv 8 \pmod{13}$$, not $$-1$$.