วิธีการนี้ Gauss ก็เคยเอามาใช้หาคำตอบของสมภาคในรูป
$ax\equiv 1\pmod{n}$
นั่นคือการหา inverse ของ $a$ modulo $n$ ครับ
ตัวอย่าง $5x\equiv 1\pmod{11}$
วิธีที่ Gauss ใช้คือทำแบบนี้
$x=\dfrac{1}{5}=\dfrac{1+11}{5}=\dfrac{1+22}{5}=\dfrac{1+33}{5}=\dfrac{1+44}{5}=9$
ซึ่งจะคล้ายๆกัน แต่ที่ผมชอบอยู่อย่างหนึ่งในวิธีของน้อง Real Matrik คือ
การหาค่า $k$ ที่ทำให้ทุกอย่างลงตัวพอดีแทนที่จะสุ่มไปเรื่อยๆแบบข้างบน ตรงนี้ไม่ใช่กระบวนการสุ่มแต่เป็นการแก้สมภาคอีกรอบ
โดยที่ตัว modulo จะมีค่าน้อยลง ซึ่งผมคิดว่าน่าจะเอาไปใช้งานได้อย่างจริงจังและถ้ามี algorithm ด้วยก็จะดีมากครับ
ที่ผมสงสัยและอยากให้ไปคิดต่อมีดังนี้
1. algorithm ที่ได้จะเร็วกว่า Euclidean algorithm ซึ่งเป็นวิธีการทั่วไปในการแก้สมภาคแบบนี้หรือไม่
2. วิธีการนี้คือ Euclidean algorithm ที่แปลงร่างมาหรือไม่
ขอบคุณสำหรับบทความดีๆครับ