สมการไดโอแฟนไทน์เชิงเส้น (Linear Diophantine Equations)

1. สมการไดโอแฟนไทน์เชิงเส้น (Linear Diophantine Equations)

          นิยาม สมการไดโอแฟนไทน์ (Diophantine equations) คือ สมการพหุนาม ที่มีสัมประสิทธิ์เป็นจำนวนเต็ม และมีผลเฉลยเป็นจำนวนเต็ม

โดยมากสมการไดโอแฟนไทน์จะอยู่มีตัวแปรตั้งแต่ 2 ตัวแปรขึ้นไป ตัวอย่างเช่น

1) 3x + 4y = 5
2) x²-2y¹= 1
3) 2x + 2y + 2z = 1
4) x² + y² = z²

          นิยาม สมการไดโอแฟนไทน์เชิงเส้น (linear Diophantine equations) คือ

สมการที่อยู่ในรูป  a₁ x₁+a₂ x₂+a₃ x₃+a₄ x₄+a₅ x₅+⋯+a_n x_n=k

เมื่อ  a₁,a₂,a₃,…,a_n,k เป็นจำนวนเต็มที่ไม่เป็นศูนย์ และ  เป็นตัวแปรซึ่งมีผลเฉลยเป็นจำนวนเต็ม

จะเห็นได้ว่าสมการไดโอแฟนไทน์เชิงเส้น เป็นสมการดีกรีหนึ่ง เนื่องจากทุกตัวแปรมีเลขชี้กำลังเป็นหนึ่ง สมการไดโอแฟนไทน์ มีที่มาจาก ไดโอแฟนทัส (Diophantus) นักคณิตศาสตร์ชาวกรีก ซึ่งศึกษาปัญหาที่เกี่ยวข้องกับสมการในลักษณะนี้ และเป็นหนึ่งในนักคณิตศาสตร์กลุ่มแรกที่เริ่มต้นใช้สัญลักษณ์ในวิชาพีชคณิต ไดโอแฟนทัสได้ชื่อว่าเป็น บิดาของพีชคณิต ปัจจุบันมีวิชาที่ศึกษาปัญหาที่เกี่ยวข้องกับสมการไดโอแฟนไทน์ เรียกว่า การวิเคราะห์ไดโอแฟนไทน์ (Diophantine analysis) ซึ่งมีความสำคัญในการศึกษาการเข้ารหัสคีย์สาธารณะ (public-key cryptography) เป็นต้น

ในการศึกษาสมการไดโอแฟนไทน์เชิงเส้นนั้น เราจะเริ่มพิจารณาจากปัญหาที่ง่ายก่อน ดังตัวอย่างต่อไปนี้

           ตัวอย่าง ต้องการนำเหรียญ 10 บาท และธนบัตรใบละ 20 บาท มารวมกัน ให้ได้เงิน 200 บาท จะทำได้ทั้งหมดกี่วิธี ให้  เป็นจำนวนเหรียญ 10 บาท และ  เป็นจำนวนธนบัตรใบละ 20 บาท จะได้ว่า

จัดรูป จะได้

10x+20y=200
x+2y=20

นั่นคือ  2y=20 – x  จะเห็นได้ว่า  เนื่องจากเราต้องการให้ทั้ง x  และ  y เป็นจำนวนเต็ม ดังนั้น  20 – x ต้องหารด้วย 2 ลงตัว นั่นคือ  x ต้องหารด้วย 2 ลงตัวนั่นเอง ทำให้ได้ว่า ผลเฉลยที่เป็นไปได้ทั้งหมดของ  x มีค่าตั้งแต่ 0 แต่ไม่เกิน 20  ดังนั้น ผลเฉลยทั้งหมด ได้แก่

(0,10),(2,9),(4,8),(6,7),(8,6),(10,5),(12,4),(14,3),(16,2),(18,1),(20,0)

แต่ในความเป็นจริง ผลเฉลยของสมการไดโอแฟนไทน์เชิงเส้นอาจมีความซับซ้อนมากกว่านั้น

             ตัวอย่าง สกายมีเงินอยู่ 68 บาท ต้องการซื้อน้ำกระป๋องละ 8 บาท และน้ำขวดละ 12 บาท จะมีกี่วิธีที่สกายจะซื้อน้ำกระป๋อง ให้ x เป็นน้ำกระป๋อง และ y เป็นจำนวนน้ำขวด ถ้าต้องการใช้เงินให้หมด จะได้ว่า 8x + 12y = 68 ตัดทอนด้วย 4 จนเหลือ 3x +2y =17

จะเห็นได้ว่า ทั้ง 2 และ 3 ต่างก็หาร 17 ไม่ลงตัว ทำให้เราได้ว่า จะไม่สามารถซื้อเฉพาะน้ำขวดหรือน้ำกระป๋องอย่างใดอย่างหนึ่งได้ เพราะในกรณีนั้นจะต้องมี x หรือ y ตัวใดตัวหนึ่งเป็น 0 ทำให้อีกตัวแปรที่เหลือจำเป็นต้องหาร 17 ลงตัว

ต่อไป เริ่มพิจารณาจากค่าน้อยสุดที่เป็นไปได้ โดยเริ่มพิจารณาจาก y = 1 ทำให้ได้ว่า x = 5 จากนั้น เพิ่มเป็น y = 2 จะพบว่าไม่มี x ที่เป็นจำนวนเต็มที่เป็นผลเฉลยได้ เช่นเดียวกับ y = 3

แต่ y = 4 ทำให้ได้ x = 3 จะสังเกตว่า ค่าของ x  ลดลงมา 2 แต่ค่าของ y เพิ่มขึ้น 3 จึงอาจคาดได้ว่า คำตอบที่เหลือคือ x= 1 และ y = 7

ดังนั้น สกายมีทั้งหมด 3 วิธีที่จะใช้เงินทั้งหมด นั่นคือ (1,7),(3,4),(5,2)

ขอบคุณแหล่งข้อมูล https://www.scimath.org