แก้+พิสูจน์สมการนี้หน่อย

[NEWTON]

1.จงพิสูจน์ว่าสมการ ax+by = a+c มีผลเฉลยก็ต่อเมื่อ ax+by = c มีผลเฉลย
2. หาผลเฉลยของสมการไดโอเฟนไทน์ที่เป็นจำนวนเต็มบวกของ 123x+57y= 531
3) หาผลเฉลยทั่วไปของ
3.1 13x+5y = 34
3.2 17x-33y = 14
4. หาผลเฉลยของระบบคอนกรูเอ็นซ์
x = 3(mod 5)
x = 5(mod 7)
x = 7(mod 11)

ช่วยหน่อยนะครับ นึกไม่ออกจริง ๆ

[Numeric Philanthropist]

1.) สมการ ax+by = c จะมีคำตอบเป็นจำนวนเต็ม ก็ต่อเมื่อ (a,b) หาร c ลงตัว ก็ต่อเมื่อ (a,b) หาร a + c ลงตัว ซึ่งก็ต่อเมื่อสมการ ax+by = a+c มีคำตอบเป็นจำนวนเต็ม
2.) มันก็น่าจะมีวิธีดีๆ มีหลักการเหมือนกัน แต่ขี้เกียจคิด ใช้วิธีแทนค่าเอาดีกว่า เค้าให้ x,y เป็น จำนวนเต็มบวก ก็ไล่แทน x ตั้งแต่ 1,2,3,4 ก็ได้ x = 2 y = 5 เป็นคำตอบเดียวที่สอดคล้อง
3.) สำหรับสมการ ax + by = c จะมีสูตรการหาคำตอบ (x,y) ที่เป็นจำนวนเต็มคือ
x = m + (b/d)t
y = n - (a/d)t
เมื่อ d = gcd(a,b) และ t เป็นจำนวนเต็มใดๆ และ (m,n) เป็นคำตอบหนึ่งของสมการ
4.) ใช้ Chinese Remainder Theorem

ขอบคุณครับสำหรับคำตอบที่ตอบมา แต่ว่าผมต้องการคำตอบครับ ก็คือข้อ 3 และข้อ 4
ข้อ 3 นั้นต้องขออภัยอย่างยิ่งครับ ผมลืมบอกวิธีการหา ใช้เทคนิดการหาแบบคอนกรูเอนซ์ครับ ซึ่งข้อนี้ผมก็ใช้วิธีการหาแบบดังกล่าวผลปรากฏว่าผลเฉลยออกมาไม่ใช่จำนวนเต็ม แต่ถ้าใช้วิธีที่เสนอมานี้ผมก็ได้คำตอบเหมือนกัน
ข้อ 4 ผมต้องการคำตอบเลยครับ ไม่ต้องแสดงวิธีทำให้ดูก็ได้
และข้อ 1แนวการพิสูจน์ดูมั่ว ๆ หน่อยนะครับ แล้วผมก็ไม่เข้าใจว่า (a,b) หาร a + c ลงตัวเนี้ย เรารู้ได้อย่างไรว่ามันเป็นจริง

[gon]

ตอบบางข้อนะครับ.
สมการ ax + by = gcd(a,b) มีคำตอบหนึ่งเสมอ
หาคำตอบหนึ่งได้ง่าย ๆ โดยใช้ขั้นตอนวิธีการหารของยุคลิดครับ

เช่น 17x-33y = gcd(17, 33) = 1

33 = 1(17) + 16
17 = 1(16) + 1
16 = 16(1) + 0

ให้ a = 17, b = -33
ดังนั้น
16 = -b - a
1 = a + b + a = 2a + b

นั่นคือ (2, 1) เป็นคำตอบหนึ่งของสมการนี้
แล้วลองคิดต่อเอาเองนะครับว่า คำตอบทั่วไป
ของ 17x - 33y = 34 จะเป็นอะไร

ถ้าได้คำตอบทั่วไปมาแล้ว อยากได้คำตอบที่เป็นบวกอย่างเดียวก็ไม่ยาก

-------------
x = 3(mod 5) ... (1)
x = 5(mod 7) ... (2)
x = 7(mod 11) ... (3)

x = 3 mod 5 -> x = 5a + 3 ....(4)
แทนค่าลงใน (2)
5a + 3 = 5 mod 7
5a = 2 mod 7
-2a = 2 mod 7
-a = 1 mod 7
a = -1 = 6 mod 7
a = 7b + 6
ดังนั้น x = 5(7b + 6 ) + 3 = 35b + 33 .... (5)
แทนค่าลงใน (3)
35b + 33 = 7 mod 11
35b = -26 = 7 mod 11
2b = 7 mod 11
10b = 35 = 2 mod 11
-b = 2 mod 11
b = -2 = 9 mod 11
b = 11c + 9
ดังนั้น x = 35(11c + 9) + 33 = 385c + 348 Ans

ช่วยดูด้วยอาจมีที่ผิดครับ

[warut]

1. ตามความเห็นของผมการพิสูจน์ของคุณ Numeric Philanthropist
ถูกต้องดีแล้วนะครับ เรารู้ว่า (a,b) | c ซ (a,b) | a + c ก็เพราะว่า (a,b) | a
3. ไม่แน่ใจว่าเทคนิดการหาแบบคอนกรูเอนซ์คือแบบนี้ใช่มั้ยครับ
เนื่องจาก 13x + 5y = 34 ดังนั้นเราจึงได้ว่า 13x บ 34 (mod 5)
ทำ reduction modulo 5 ตลอดจะได้ว่า -2x บ -1 (mod 5) หรือ 2x บ 1 (mod 5)
ดังนั้น x บ 3 (mod 5) ถ้า x = 3 จะได้ y = -1 ดังนั้นคำตอบทั่วไปคือ
x = 3 + 5t
y = -1 - 13t
4. คำตอบของคุณ gon: x บ 348 (mod 385) ถูกต้องแล้วครับ
385 = 5*7*11
348 บ 3 (mod 5)
348 บ 5 (mod 7)
348 บ 7 (mod 11)

[StormZNW]

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

35b = -26 = 7 mod 11
2b = 7 mod 11

สงสัยครับ ตรงนี้มาไงครับ? หาทฤษฎีอ่านไม่ได้อ่าครับ

[Amankris]

โห กระทู้ 9 ปี O_o"

ไม่ค่อยเข้าใจ #6 นะ แต่ลองหาอ่าน Chinese remainder theorem ดู

[kongp]

การพิสูจน์แบบหาข้อขัดแย้ง ถ้าอาจารย์เฮียบๆ จะได้คะแนนน้อย เพราะเหมือนกับตีกรอบกว้างๆ ในสังคมที่ประสบในชวิตประจำวัน มีส่ิ่งที่มี 2 แง่ ที่ไม่ใชุ่เรื่องถูกผิด