1. สมการไดโอแฟนไทน์เชิงเส้น (Linear Diophantine Equations)
นิยาม สมการไดโอแฟนไทน์ (Diophantine equations) คือ สมการพหุนาม ที่มีสัมประสิทธิ์เป็นจำนวนเต็ม และมีผลเฉลยเป็นจำนวนเต็ม
โดยมากสมการไดโอแฟนไทน์จะอยู่มีตัวแปรตั้งแต่ 2 ตัวแปรขึ้นไป ตัวอย่างเช่น
1) 3x + 4y = 5
2) x2-2y1= 1
3) 2x + 2y + 2z = 1
4) x2 + y2 = z2
นิยาม สมการไดโอแฟนไทน์เชิงเส้น (linear Diophantine equations) คือ
สมการที่อยู่ในรูป a1 x1+a2 x2+a3 x3+a4 x4+a5 x5+⋯+an xn=k
เมื่อ a1,a2,a3,…,an,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