TL;DR
สมการ Diophantine ความจริงแล้วเป็นสมการเพื่อหา x,y จากสมการ polynomial ธรรมดาๆ หนิแหละ แต่สิ่งที่นักคณิตศาสตร์สนใจมากกว่าคำตอบทั่วๆไป คือ คำตอบที่เป็นจำนวนเต็ม เฉพาะแค่จำนวนเต็มเท่านั้นที่เราสนใจ และดึงดูดให้นักคณิตศาสตร์พยายามศึกษาแล้วแก้ไขโจทย์พวกนี้มาหลายศตวรรษ
สารภาพว่า วันนี้ /me โดดเรียนภาษาอังกฤษ เลยมาเขียนบทความเนิร์ดๆไถ่โทษ เรื่องหนึ่งที่ /me สนใจมาตั้งแต่มัธยม การแก้ปัญหาทางคณิตศาสตร์ ซึ่งทำให้ /me ได้เล่น Project Euler ซึ่งมีปัญหาทางคณิตศาสตร์เจ๋งๆให้แก้ โดยใช้ทั้งทักษะทางคณิตศาสตร์ และ ทักษะการเขียนโปรแกรมเพื่อแก้ปัญหา โดยปัญหากลุ่มหนึ่งที่ /me มักจะเจอก็ คือ ปัญหาการแก้สมการ “Diophantine Equation” ซึ่งเป็นปัญหา classic ตั้งแต่สมัยศตวรรษที่ 16
What is Diophantine Equation?
สมการ Diophantine ความจริงแล้วเป็นสมการเพื่อหา x,y จากสมการ polynomial ธรรมดาๆ หนิแหละ แต่สิ่งที่นักคณิตศาสตร์สนใจมากกว่าคำตอบทั่วๆไป คือ คำตอบที่เป็นจำนวนเต็ม เฉพาะแค่จำนวนเต็มเท่านั้นที่เราสนใจ และดึงดูดให้นักคณิตศาสตร์พยายามศึกษาแล้วแก้ไขโจทย์พวกนี้มาหลายศตวรรษ
หนึ่งในสมการ Diophantine ที่โด่งดังไป ก็คือ The Fermat’s Last Theorem ซึ่งเป็นปัญหาที่ไม่สามารถแก้ได้มานับ 100 ปี แต่พึ่งโดยพิชิตโดย Andrew Wiles ในปี 1995
\[a^{n}+b^{n} = c^{n} : n>2\]ในปี 1900 Diophantine Equation กลายเป็นหนึ่งในปัญหา Hilbert’s problem ซึ่งท้าทายนักคณิตศาสตร์ด้วยโจทย์ที่ถามว่า จะมี general algorithm ที่สามารถแก้ทุกๆสมการ Diophantine ได้จริงๆหรือไม่? แต่ข่าวร้ายก็คือ ในปี 1970, Yuri Matiyasevich พิสูจน์ว่า general algorithm ที่เราฝันนั้น มันไม่มีอยู่จริง. RIP
แต่อย่างไรก็ตาม สมการ classic หลายๆสมการก็สามารถแก้ได้จริงๆ หนึ่งในนั้น ก็คือ สมการ 2 ตัวแปรที่มีดีกรีไม่เกิน 2 ที่เราเรียนกันมาตั้งแต่สมัยมัธยมปลาย
\[Ax^{2}+Bxy+Cx^{2}+Dx+Ey+F = 0\]และเราก็จะมาศึกษาวิธีการแก้มันในบทความนี้ //คิดว่าคงต้องมีอย่างน้อย 2-3 ตอน เพราะมันเยอะ และยาวมากกกกก~
Get started
ก่อนที่จะเริ่มกันอย่างจริงจัง จากที่เรียนใน ม.ปลาย เราสามารถแบ่งรูปแบบของสมการได้เป็น 5 รูปแบบคือ
- Linear case: A = B = C = 0
- Simple hyperbolic case: A = C = 0; B ≠ 0
- Elliptical case: B2 - 4AC < 0
- Parabolic case: B2 - 4AC = 0
- Hyperbolic case: B2 - 4AC > 0
Linear case
กรณีนี้เป็นรูปแบบที่เรียบง่ายที่สุด โดย เมื่อ A = B = C = 0 จะทำให้ส่วนที่เป็นดีกรี 2 ของสมการหายไป เหลือเพียง Linear Equation ซึ่งเมื่อวาดกราฟออกมา ก็จะได้รูปเส้นตรง 1 เส้น \(Dx+Ey+F = 0\)
เมื่อพิจารณาแล้ว จะพบว่า
เมื่อ \(D = E = 0\)
สมการจะเป็นจริง ก็ต่อเมื่อ F=0 และจะได้คำตอบ (x,y) สำหรับทุกๆ x,y ที่เป็นจำนวนเต็มใดๆ
เมื่อ \(D = 0, E \neq 0\)
สมการจะเป็นจริง ก็ต่อเมื่อ E หาร F ลงตัว และจะได้คำตอบ (x, \(\frac{-F}{E}\)) สำหรับทุกๆ x ที่เป็นจำนวนเต็มใดๆ
เมื่อ \(D \neq 0, E = 0\)
สมการจะเป็นจริง ก็ต่อเมื่อ D หาร F ลงตัว และจะได้คำตอบ (\(\frac{-F}{D}\), y) สำหรับทุกๆ y ที่เป็นจำนวนเต็มใดๆ
เมื่อ \(D \neq 0, E \neq 0\)
//มาถึงสมการที่ต้องแก้กันอย่างจริงจังแล้ว
พิจารณา g = gcd(D, E) โดย gcd(x, y) คือ ตัวเลขที่มากที่สุดที่หารทั้ง x, y ลงตัว หรือ ห.ร.ม. นั้นเอง
จะได้ว่า D = gd และ E = ge เมื่อแทนค่าลงในสมการจะได้
\[Dx+Ey = -F\\\\ gdx+gey = -F\\\\ g(dx+ey) = -F\\\\\]ดังนั้นเงื่อนไขแรกสำหรับการหาคำตอบที่เป็นจำนวนเต็ม ก็คือ g จะต้องหาร F ลงตัว เราจะแทน F = gf ปรับเป็นสมการใหม่ คือ
\[dx+ey = -f : gcd(d,e) = 1\]จากนั้นใช้ Extended Euclid’s Algorithm ที่ต่อยอดจาก Euclid’s Algorithm ที่ใช้ในการหา หรม. ซึ่งพิสูจน์ว่า สำหรับทุกๆจำนวนเต็ม a,b ใดๆ สามารถจัดให้อยู่ในรูปแบบ \(ax + by = gcd(a,b)\) ได้เสมอ //ไม่อธิบายวิธการละกัน แต่สามารถดูจากตัวอย่างนะ #เชื่อเถอะว่าไม่ยาก
Example of Extended Euclid’s Algorithm
กำหนด a = 1180, b = 482
Phase I : Euclid’s Algorithm
$$
1180 = 482(2) + 216\\\\
482 = 216(2) + 50\\\\
216 = 50(4) + 16\\\\
50 = 16(3) + 2\\\\
16 = 2(8) + 0\\\\
gcd(1180, 482) = 2 \sharp\\\\
$$
Phase II : Extended Euclid’s Algorithm
$$
2 = 50 - 16(3)\\\\
2 = 50 -(216 - 50(4))(3) = 216(-3) + 50(13)\\\\
2 = 216(-3) + (482 - 216(2))(13) = 216(-29) + 482(13)\\\\
2 = 482(13) + (1180 - 482(2))(-29) = 1180(-29)+482(71)\\\\
2 = 1180(-29)+482(71) \sharp\\\\
$$
หลังจากผ่าน Extended Euclid’s Algorithm เราจะได้ \(du+ev = 1\) โดยที่ u, v เป็นจำนวนเต็ม และคูณอยู่กับ d, f ที่เราศึกษาจากโจทย์
\[du+ev = 1 \\\\ du(-f)+ev(-f) = -f \\\\ du(-f)+ev(-f) + (det - det) = -f \\\\ d(et-uf)+e(dt-vf) = -f \\\\\]ดังนั้น คำตอบทั่วไปของสมการ ตามเงื่อนไขนี้ ก็คือ
\[x = et-uf\\\\ y = dt-vf \\\\\]สำหรับทุกๆ t ที่เป็นจำนวนเต็มใดๆ Q.E.D.
Simple hyperbolic case
\[Cxy+Dx+Ey+F = 0\]สิ่งที่เพิ่มเติมในกรณีนี้ก็คือ พจน์ Cxy ทำให้เกิดคุณสมบัติที่สำคัญคือ มันสามารถจัดรูปเป็น 2 พจน์ที่คูณกันได้
\[Bxy + Dx + Ey + F = 0 \\\\ Bxy + Dx + Ey = -F \\\\ B^{2}xy + BDx + BEy = -BF \\\\ B^{2}xy + BDx + BEy + DE = DE - BF \\\\ (Bx + E) (By + D) = DE - BF\]สำหรับกรณี \(DE - BF = 0\)
\[(Bx + E) (By + D) = 0\]นั้นคือสมการจะเป็นจริง ก็ต่อเมื่อ \((Bx + E) = 0\) หรือ \((By + D) = 0\) เท่านั้น ดังนั้น คำตอบที่เป็นจำนวนเต็มของสมการนี้ ก็คือ \((\frac{-E}{B}, y)\) สำหรับ ทุกๆ y ที่เป็นจำนวนเต็มใดๆ และ B ต้องเป็นตัวประกอบของ E และ
\((x, \frac{-D}{B})\) สำหรับ ทุกๆ x ที่เป็นจำนวนเต็มใดๆ และ B ต้องเป็นตัวประกอบของ D
สำหรับกรณี \(DE - BF \neq 0\)
พิจารณาทุกๆตัวประกอบของ DE - BF ซึ่งมีจำนวนจำกัด และสามารถทดสอบทั้งหมดได้ แทนด้วย \(d_{1}, d_{2}, d_{3}, ...\)
เพราะ DE - BF เกิดจากคู่ตัวประกอบ 2 ตัวคูณกัน ดังนั้น กำหนด
\[(Bx + E) = d_{i} \\\\ (By + D) = \frac{DE - BF}{d_{i}} \\\\\]ดังนั้น คำตอบของสมการ ตามเงื่อนไขนี้ ก็คือ
\[x = \frac{d_{i}-E}{B}\\\\ y = \frac{DE - BF - D(d_{i})}{B(d_{i})} \\\\\]โดยนับเฉพาะ x, y ที่เป็นจำนวนเต็ม Q.E.D.
ผ่านไปแล้ว สำหรับ 2 กรณีแรก ที่ยังไม่ค่อบซับซ้อน แต่ก็เป็นอาหารเรียกน้ำย่อยได้ดีเลยทีเดียว สำหรับตอนต่อไป /me จะไปลุยกับ กรณีอื่นๆแล้วมาค้นกันว่า มันจะมีวิธีประหลายๆยังไงเพื่อหาคำตอบที่เป็นจำนวนเต็มของสมการนี้ :)