การแก้สมการและระบบสมการคอนกรูเอนซ์

[Real Matrik]

เป็นแนวคิดใหม่(??) ในการแก้สมการและระบบสมการคอนกรูเอนซ์เชิงเส้นตัวแปรเดียวครับ Click !!

รบกวนคอมเม้นท์ด้วยก็ดีครับ

[nooonuii]

วิธีการนี้ 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 ที่แปลงร่างมาหรือไม่

ขอบคุณสำหรับบทความดีๆครับ

[Real Matrik]

ขอบคุณครับพี่ nooonuii แต่ก่อนผมใช้วิธีการหาค่า $k$ ที่เหมาะสมมาบวกเข้าครับ
แต่เดี๋ยวนี้ใช้วิธีเล่นกับสัมประสิทธิ์ของ $x$ อย่างเดียวเลย เร็วดีแถมไม่ต้องเขียนภาษามนุษย์ด้วยครับ

$$5x\equiv1\pmod{11}$$
$$10x\equiv2\pmod{11}$$
$$11x-10x\equiv0-2\pmod{11}$$
$$x\equiv9\pmod{11}$$