เครื่องคิดเลขทฤษฎีเศษเหลือจีน

ยินดีต้อนรับสู่ เครื่องคิดเลขทฤษฎีเศษเหลือจีน เครื่องมือทฤษฎีจำนวนที่ทรงพลังสำหรับแก้ระบบสมการสมภาคพร้อมกันโดยใช้ทฤษฎีเศษเหลือจีน (CRT) ไม่ว่าคุณจะกำลังศึกษาเลขคณิตมอดุลาร์ เตรียมตัวสำหรับการแข่งขันคณิตศาสตร์ ทำงานเกี่ยวกับปัญหาการเข้ารหัส หรือสำรวจทฤษฎีจำนวน เครื่องคิดเลขนี้จะแสดงวิธีทำอย่างละเอียดทีละขั้นตอน พร้อมการแสดงภาพประกอบที่แสดงให้เห็นว่าคลาสสมภาคสอดคล้องกันที่คำตอบที่เฉพาะเจาะจงอย่างไร

ทฤษฎีเศษเหลือจีนคืออะไร?

ทฤษฎีเศษเหลือจีน (Chinese Remainder Theorem - CRT) เป็นผลลัพธ์พื้นฐานในทฤษฎีจำนวนที่รับประกันการมีอยู่และความเป็นหนึ่งเดียวของคำตอบสำหรับระบบสมการสมภาคพร้อมกัน โดยมีเงื่อนไขว่าตัวหาร (Moduli) ต้องเป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่ ทฤษฎีนี้ถูกอธิบายครั้งแรกโดยนักคณิตศาสตร์ชาวจีนชื่อ Sunzi (孫子) ในผลงานของเขาที่ชื่อว่า Sunzi Suanjing (孫子算經) ประมาณคริสต์ศตวรรษที่ 3

อย่างเป็นทางการ เมื่อกำหนดระบบสมการ:

ถ้าตัวหารทั้งหมด \(m_1, m_2, \ldots, m_k\) เป็น จำนวนเฉพาะสัมพัทธ์เป็นคู่ (นั่นคือ \(\gcd(m_i, m_j) = 1\) สำหรับทุก \(i \neq j\)) แล้วจะมี คำตอบที่เฉพาะเจาะจง \(x\) มอดูโล \(M = m_1 \times m_2 \times \cdots \times m_k\)

อัลกอริทึม CRT ทำงานอย่างไร

การพิสูจน์เชิงสร้างสรรค์ให้ขั้นตอนวิธีที่ใช้โดยเครื่องคิดเลขนี้ดังนี้:

ขั้นตอนที่ 1: คำนวณ M

คำนวณผลคูณของตัวหารทั้งหมด:

ขั้นตอนที่ 2: คำนวณ Mᵢ แต่ละตัว

สำหรับแต่ละสมภาค \(i\) ให้คำนวณ \(M_i = M / m_i\) นี่คือผลคูณของตัวหารทั้งหมด ยกเว้น \(m_i\)

ขั้นตอนที่ 3: หาตัวผกผันโมดูลา

สำหรับแต่ละ \(i\) ให้หา \(y_i\) ที่ทำให้ \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) โดยใช้ Extended Euclidean Algorithm เนื่องจาก \(M_i\) และ \(m_i\) เป็นจำนวนเฉพาะสัมพัทธ์กัน (ตัวหารทั้งหมดเป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่) ตัวผกผันนี้จึงมีอยู่เสมอ

ขั้นตอนที่ 4: สร้างคำตอบ

คำตอบทั่วไป คือ \(x + k \cdot M\) สำหรับจำนวนเต็ม \(k\) ใดๆ ซึ่งหมายความว่าคำตอบจะซ้ำกันทุกๆ \(M\) จำนวนเต็ม

วิธีใช้งานเครื่องคิดเลขนี้

1. ป้อนสมการสมภาคของคุณ: สำหรับแต่ละสมการ \(x \equiv a \pmod{m}\) ให้ป้อนเศษ \(a\) และตัวหาร \(m\) เริ่มต้นด้วย 2 สมการ และคลิก "เพิ่มสมการสมภาค" เพื่อเพิ่มมากขึ้น (สูงสุด 10 สมการ)
2. ตรวจสอบตัวหารของคุณ: ตัวหารทั้งหมดต้องเป็นจำนวนเต็มบวก ≥ 2 และเป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่ เครื่องคิดเลขจะตรวจสอบสิ่งนี้โดยอัตโนมัติ
3. คลิก "แก้ระบบสมการ": เครื่องคิดเลขจะใช้อัลกอริทึม CRT และแสดงคำตอบที่เฉพาะเจาะจงพร้อมวิธีทำทีละขั้นตอน
4. ตรวจสอบการแสดงภาพ: เส้นจำนวนจะแสดงให้เห็นว่าคลาสสมภาคจากแต่ละสมการมาตัดกันที่คำตอบอย่างไร
5. ตรวจสอบคำตอบ: ส่วนการตรวจสอบจะยืนยันว่าคำตอบสอดคล้องกับสมการสมภาคดั้งเดิมทุกข้อ

การทำความเข้าใจผลลัพธ์

• คำตอบที่เป็นบวกที่น้อยที่สุด (x₀): คำตอบที่เฉพาะเจาะจงในช่วง [0, M−1]
• คำตอบทั่วไป: จำนวนเต็มทั้งหมดในรูปแบบ x₀ + kM เมื่อ k เป็นจำนวนเต็มใดๆ
• ตารางตรวจสอบคำตอบ: ยืนยันว่า x₀ mod mᵢ = aᵢ สำหรับแต่ละสมการ
• การแยกย่อยทีละขั้นตอน: แสดง Mᵢ, ตัวผกผันโมดูลา yᵢ และผลบวกย่อย aᵢ·Mᵢ·yᵢ สำหรับแต่ละสมการ
• เส้นจำนวน: การแสดงภาพแทนการจัดตำแหน่งของคลาสส่วนเหลือที่คำตอบ

การประยุกต์ใช้ทฤษฎีเศษเหลือจีน

ปัญหาคลาสสิกของ Sunzi

ปัญหาดั้งเดิมจาก Sunzi Suanjing ถามว่า: "มีสิ่งของจำนวนหนึ่งที่ไม่ทราบจำนวน หากเรานับทีละสาม จะเหลือเศษสอง; นับทีละห้า จะเหลือเศษสาม; และนับทีละเจ็ด จะเหลือเศษสอง มีของอยู่กี่ชิ้น?"

ซึ่งแปลได้ว่า: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\) เมื่อใช้ CRT คำตอบคือ x = 23 (และโดยทั่วไปคือ 23 + 105k สำหรับจำนวนเต็มไม่เป็นลบ k ใดๆ)

เมื่อใดที่ CRT ไม่สามารถใช้ได้?

• ตัวหารที่ไม่เป็นจำนวนเฉพาะสัมพัทธ์: หากคู่ใดคู่หนึ่งของตัวหารมีตัวประกอบร่วมกันมากกว่า 1 CRT แบบมาตรฐานจะไม่รับประกันว่าจะมีคำตอบ คำตอบอาจยังมีอยู่หากเศษมีความสอดคล้องกัน แต่เครื่องคิดเลขนี้ต้องการตัวหารที่เป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่สำหรับอัลกอริทึมมาตรฐาน
• สมการสมภาคเดียว: CRT ต้องการสมการสมภาคอย่างน้อย 2 สมการ สมการสมภาคเดียว \(x \equiv a \pmod{m}\) มีคำตอบที่ชัดเจนอยู่แล้วคือ x = a

Extended Euclidean Algorithm

Extended Euclidean Algorithm เป็นสิ่งจำเป็นสำหรับ CRT เพราะใช้สำหรับหาตัวผกผันโมดูลา เมื่อกำหนดจำนวนเต็ม \(a\) และ \(b\) อัลกอริทึมนี้จะหาจำนวนเต็ม \(x\) และ \(y\) ที่ทำให้:

เมื่อ \(\gcd(a, b) = 1\) แล้ว \(x\) จะเป็นตัวผกผันโมดูลาของ \(a\) มอดูโล \(b\) นั่นคือ \(a \cdot x \equiv 1 \pmod{b}\)

คำถามที่พบบ่อย

ทฤษฎีเศษเหลือจีนคืออะไร?

ทฤษฎีเศษเหลือจีน (CRT) ระบุว่าถ้าคุณมีระบบสมการสมภาคพร้อมกัน x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ) โดยที่ตัวหารทั้งหมดเป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่ จะมีคำตอบที่เฉพาะเจาะจงมอดูโล M = m₁ × m₂ × ... × mₖ ทฤษฎีนี้ถูกอธิบายครั้งแรกโดยนักคณิตศาสตร์ชาวจีนชื่อ Sunzi ในศตวรรษที่ 3

จำนวนเฉพาะสัมพัทธ์เป็นคู่หมายถึงอะไร?

จำนวนเฉพาะสัมพัทธ์เป็นคู่หมายความว่าตัวหารทุกคู่ไม่มีตัวประกอบร่วมกันนอกจาก 1 ตัวอย่างเช่น {3, 5, 7} เป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่เพราะ gcd(3,5)=1, gcd(3,7)=1 และ gcd(5,7)=1 อย่างไรก็ตาม {4, 6, 5} ไม่เป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่เพราะ gcd(4,6)=2

วิธีการแก้ระบบสมการสมภาคทีละขั้นตอนทำอย่างไร?

การแก้โดยใช้ CRT: (1) ตรวจสอบว่าตัวหารทั้งหมดเป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่ (2) คำนวณ M = ผลคูณของตัวหารทั้งหมด (3) สำหรับแต่ละสมการ ให้คำนวณ Mᵢ = M/mᵢ (4) หาตัวผกผันโมดูลา yᵢ ของ Mᵢ มอดูโล mᵢ โดยใช้ Extended Euclidean Algorithm (5) คำนวณคำตอบ x = Σ(aᵢ × Mᵢ × yᵢ) mod M คำตอบทั่วไปคือ x + k×M สำหรับจำนวนเต็ม k ใดๆ

การประยุกต์ใช้ทฤษฎีเศษเหลือจีนมีอะไรบ้าง?

CRT มีการประยุกต์ใช้จริงมากมาย: การเข้ารหัส RSA ใช้ CRT เพื่อการถอดรหัสที่มีประสิทธิภาพ วิทยาการคอมพิวเตอร์ใช้สำหรับการคำนวณจำนวนขนาดใหญ่โดยการแบ่งการคำนวณออกเป็นส่วนย่อยๆ การประมวลผลสัญญาณใช้ CRT ในรหัสแก้ไขข้อผิดพลาด ปัญหาการจัดตารางเวลาและปฏิทินที่เหตุการณ์ซ้ำกันในรอบที่ต่างกันก็ใช้ CRT เช่นกัน

จะเกิดอะไรขึ้นถ้าตัวหารไม่เป็นจำนวนเฉพาะสัมพัทธ์?

หากตัวหารไม่เป็นจำนวนเฉพาะสัมพัทธ์เป็นคู่ ทฤษฎีเศษเหลือจีนแบบมาตรฐานจะไม่สามารถใช้ได้โดยตรง ในบางกรณี คำตอบอาจยังคงมีอยู่หากเป็นไปตามเงื่อนไขความเข้ากันได้บางประการ (เศษต้องสอดคล้องกันมอดูโล ห.ร.ม. ของตัวหารที่ไม่เป็นจำนวนเฉพาะสัมพัทธ์) อย่างไรก็ตาม หากไม่มีคำตอบ แสดงว่าระบบสมการสมภาคขัดแย้งกัน

แหล่งข้อมูลเพิ่มเติม

• ทฤษฎีเศษเหลือจีน - Wikipedia
• Extended Euclidean Algorithm - Wikipedia
• เลขคณิตมอดุลาร์ - Wikipedia