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)

              จาก 2 ตัวอย่างที่ผ่านมา จะสังเกตว่า ผลเฉลยที่ได้จะมีรูปแบบที่เหมือนกัน นั่นคือ ค่าของตัวแปรหนึ่งจะเพิ่มขึ้นตามสัมประสิทธิ์ของอีกตัวแปรหนึ่ง ในทำนองเดียวกัน ค่าของอีกตัวแปรหนึ่งก็จะลดลงตามสัมประสิทธิ์ของอีกตัวแปรหนึ่งเช่นกัน แต่ไม่ใช่ว่าปัญหาไดโอแฟนไทน์จะมีผลเฉลยเสมอไป ตัวอย่างเช่น

              ตัวอย่าง จงหาผลเฉลยที่เป็นจำนวนเต็มทั้งหมดของสมการ    12x+21y=80

              สังเกตว่า เราไม่สามารถตัดทอนโดยนำค่าคงที่หารตลอดทั้งสมการได้ แต่เราสามารถจัดรูปได้ว่า 3(4x+7y)=80

              เนื่องจากเราต้องการผลเฉลยที่เป็นจำนวนเต็ม ทำให้ได้ว่า 4x+7y  ต้องเป็นจำนวนเต็มด้วย

              แต่ 4x+7y=80/3  ซึ่งไม่เป็นจำนวนเต็ม จึงเกิดข้อขัดแย้ง

             ดังนั้น สมการนี้ไม่มีผลเฉลยที่เป็นจำนวนเต็ม