Chinese Remainder Theorem
กำหนดให้
$a_1,\ldots,a_n$ และ $m_1,\ldots,m_n$ เป็นจำนวนเต็มบวกโดยคู่ของ $m_i$ กับ $m_j$
ใดๆจะเป็นจำนวนเฉพาะสัมพัทธ์หรือไม่ก็ได้
$b_1,\ldots,b_n$ เป็นจำนวนเต็มบวกหรือศูนย์
แอปพลิเคชันนี้ใช้คำนวณหาคำตอบของระบบ linear congruences \begin{align*} a_1x &\equiv b_1 \pmod{m_1} \\ a_2x &\equiv b_2 \pmod{m_2} \\ &\vdots \\ a_nx &\equiv b_n \pmod{m_n} \end{align*} ในกรณีเฉพาะที่ $a_i=1$ เมื่อ $1\leqslant i\leqslant n$ ปัญหาข้างบนจะถูกลดรูปเป็น Chinese remainder theorem
รูปแบบของข้อมูลอินพุท
ใส่ข้อมูลทีละแถวและแถวละสามจำนวนของ a b m เรียงตามลำดับ โดยคั่นด้วยช่องว่างอย่างน้อยหนึ่งช่อง
ยกตัวอย่างเช่น ข้อมูลของ linear congruences \begin{align*} 3x &\equiv 2 \pmod{5} \\ 4x &\equiv 7 \pmod{9} \end{align*} จะต้องใส่ข้อมูลดังนี้
3 2 5
4 7 9
ถ้าเป็น Chinese remainder theorem ตัวแรกของแต่ละแถวจะต้องเป็น 1
หนังสืออ้างอิง
- Gareth A. Jones and Josephine M. Jones, Elementary Number Theory, Springer Undergraduate Mathematics Series, 8th printing 2005.
- Tom M. Apostol, Introduction to analytic number theory, Undergraduate texts in mathematics, 1976.
- A. Bogomolny, Chinese Remainder Theorem from Interactive Mathematics Miscellany and Puzzles. Accessed 23 January 2016