แก้สมการ congruence

[Pattern&Math]

เราจะแก้สมการ Congruence แบบนี้ยังไงครับ

[กระบี่ทะลวงด่าน]

$f(x)=x+1$. เดี๋ยวมาเเสดงวิธีคิดให้ครับ

[nooonuii]

หารยาวธรรมดานิ แค่เปลี่ยนรูปไปเป็นอย่างอื่น

$x^3+x^2+1=(x+1)(x^2+1)-x$

[PP_nine]

ใช้แนวคิดคล้ายๆกับ #3 ครับ แต่จัดรูปนิดหน่อย

$(x^2+1)(x+1)=(x^3+x^2+1)+x$

$x(x^2+x)=(x^3+x^2+1)-1$

เราเลยคูณ $x+1$ และ $x^2+x$ ลงไปในสมการ กลายเป็นอะไรต่อลองทำดูครับ

[nooonuii]

คำตอบไม่ได้มีแค่ $x+1$ นะครับ แต่ตัวนี้เป็นคำตอบที่มี degree ต่ำสุด

$f(x)=(x+1)+g(x)(x^3+x^2+1)$ คือคำตอบทั่วไป

[Pattern&Math]

ข้อความเดิมเขียนโดยคุณ nooonuii

คำตอบไม่ได้มีแค่ $x+1$ นะครับ แต่ตัวนี้เป็นคำตอบที่มี degree ต่ำสุด

$f(x)=(x+1)+g(x)(x^3+x^2+1)$ คือคำตอบทั่วไป

เรามีวิธีในการแสดงการหาคำตอบในรูปทั่วไปได้อย่างไรอ่ะครับ

[nooonuii]

เหมือน congruence ของจำนวนเต็มนั่นแหละครับ

เอาพหุคูณของ $x^3+x^2+1$ บวกเพิ่มเข้าไป

[Anarist]

มาเพิ่มเติมว่า เหมือนแก้ $a x = b \text{ mod } c$ จริงๆ
ซึ่งก็คือต้องหา $d$ ที่ $a p = 1 \text{ mod } c$ แล้วก็จะได้ $x = b d \text{ mod } c$

วิธีทั่วไปก็คือหา $d,e$ ที่ $ad + ce = 1$ ซึ่งก็คือการหา หรม. ของ $a$ กับ $c$ นั่นเอง
อย่างข้อนี้ $a = x^2 + 1$ , $c = x^3 + x^2 + 1$ แล้วก็เปลี่ยนเป็นหา หรม. ของพหุนามแทน

[Pattern&Math]

ข้อความเดิมเขียนโดยคุณ Anarist

มาเพิ่มเติมว่า เหมือนแก้ $a x = b \text{ mod } c$ จริงๆ
ซึ่งก็คือต้องหา $d$ ที่ $a p = 1 \text{ mod } c$ แล้วก็จะได้ $x = b d \text{ mod } c$

วิธีทั่วไปก็คือหา $d,e$ ที่ $ad + ce = 1$ ซึ่งก็คือการหา หรม. ของ $a$ กับ $c$ นั่นเอง
อย่างข้อนี้ $a = x^2 + 1$ , $c = x^3 + x^2 + 1$ แล้วก็เปลี่ยนเป็นหา หรม. ของพหุนามแทน

คือผมยัง งงๆ ตรง การหา หรม ของ $a$ $c$ อ่ะครับ แล้วก็ตรง หา $d$ ที่ $a p = 1 \text{ mod } c$ แล้วก็จะได้ $x = b d \text{ mod } c$ สองสมการนี้มันสัมพันธ์กันยังไงอ่ะครับ คือมันยังติดๆคืออ่านแล้วยังไม่ get จริงๆครับ ขอคำอธิบายเพิ่มเติมได้ไหมครับ

[Pattern&Math]

ข้อความเดิมเขียนโดยคุณ PP_nine

ใช้แนวคิดคล้ายๆกับ #3 ครับ แต่จัดรูปนิดหน่อย

$(x^2+1)(x+1)=(x^3+x^2+1)+x$

$x(x^2+x)=(x^3+x^2+1)-1$

เราเลยคูณ $x+1$ และ $x^2+x$ ลงไปในสมการ กลายเป็นอะไรต่อลองทำดูครับ

คือว่าผม ไม่เข้าใจอ่ะครับ ตรงประโยคนี้ เราเลยคูณ $x+1$ และ $x^2+x$ ลงไปในสมการ กลายเป็นอะไรต่อลองทำดูครับ [/quote] คือ ผลมันออกมามันจะได้อะไรอ่ะครับ คือสองสมการด้านบน มันก็ได้ค่าเท่ากันแล้วไม่ใช่เหรอครับ แล้ว คูณทำไมอ่ะครับ ผม งง จริงๆครับ

[PP_nine]

#10

เป็นแนวคิดเกี่ยวกับการหา inverse การคูณ คือคูณเพื่อทำให้พหุนามหายไป

เช่น แก้สมการ $4x \equiv 3 \pmod{9}$

คูณสองเข้าไปเป็น $8x \equiv 6 \pmod{9}$

$-x \equiv -3 \pmod{9}$

คูณ $-1$ เข้าไปเป็น $x \equiv 3 \pmod{9}$


โจทย์นี้ก็ทำนองเดียวกันเลยครับ

$(x^2+1)f(x) \equiv x \pmod{x^3+x^2+1}$

คูณ $x+1$ เข้าไปเป็น $[(x^3+x^2+1)+x]f(x) \equiv (x+1)(x) \pmod{x^3+x^2+1}$

$(x)f(x) \equiv x^2+x \pmod{x^3+x^2+1}$

คูณ $x^2+x$ เข้าไปเป็น $[(x^3+x^2+1)-1]f(x) \equiv (x^2+x)(x^2+x) \pmod{x^3+x^2+1}$

$-f(x) \equiv x^4+2x^3+x^2 \pmod{x^3+x^2+1}$

$-f(x) \equiv -x-1 \pmod{x^3+x^2+1}$

$f(x) \equiv x+1 \pmod{x^3+x^2+1}$


คำตอบในรูปทั่วไปก็คือ $f(x)=(x+1)+(x^3+x^2+1)g(x)$ ตามข้างต้นเลยครับ

[Pattern&Math]

ข้อความเดิมเขียนโดยคุณ PP_nine

#10


$-f(x) \equiv x^4+2x^3+x^2 \pmod{x^3+x^2+1}$

$-f(x) \equiv -x-1 \pmod{x^3+x^2+1}$

อยากทราบว่าบรรทัดข้างบน มาบรรทัดข้างล่างได้ยังไงอ่าครับ

[PP_nine]

หารยาวธรรมดาครับ

$x^4+2x^3+x^2=(x+1)(x^3+x^2+1)+(-x-1)$

[Pattern&Math]

อ้อ ขอบคุณมากครับผม