แถมให้อีกข้อ ข้อ 14 วันแรก ถ้าทำแบบ elementray ผมรู้สึกต้องทำยาวเหยียดเลย เขียนไปก็ไม่รู้เรื่องว่ามายังไง (ใครคิดสั้น ๆ เป็นบอก) เลยหามาทั่วไปเลย นี่ก็เหมือนกัน ถ้าโจทย์สนใจเฉพาะคำตอบ อาจจะลองทำกำลังน้อย ๆ แล้วเดาเลยก็อาจถูก แต่ถ้าพิสูจน์ก็อาจจะทำแบบนี้ ขอบอกใครจะทำทัน 3 ชั่วโมง
ถ้า a
ฮ I
+ , a
น 1 และ m, n
ฮ I
+ จะพิสูจน์ว่า (a
m - 1, a
n - 1) = a
(m, n) - 1 ดังนี้
สมมติให้ d = (m, n) จะได้ว่า จะมีจำนวนเต็มบวก s และ t ที่ทำให้ m = ds และ n = dt
\ a
m - 1 = a
ds - 1 = (a
d)
s - 1 ซึ่งหารด้วย a
d - 1 ลงตัว
เพราะ a - b หาร a
n - b
n ลงตัว ทุก n = 1, 2, 3, ...
ทำนองเดียวกัน a
n - 1 = a
dt - 1 = (a
d)
t - 1 ซึ่งหารด้วย a
d - 1 ลงตัว
ในส่วนแรกสรุปได้ว่า ถ้า d = (m, n) แล้ว (a
d - 1) | (a
m - 1) และ (a
d - 1) | (a
n - 1)
ต่อไปจะพิสูจน์ว่า a
d - 1 (หรือ a
(m, n) - 1) เป็นจำนวนเต็มบวกที่มากที่สุดซึ่งหาร a
m - 1 และ a
n - 1 ลงตัว)
d = (m, n) แสดงว่าจะมีจำนวนเต็ม x, y โดยที่ d = mx + ny ซึ่งจะได้ว่า x กับ y ต้องมีเครื่องหมายต่างกัน ทั้งนี้เพราะ ถ้า x, y < 0 ทั้งคู่ จะได้ว่า d < 0 ซึ่งเป็นไปไม่ได้ หรือ ถ้า x, y > 0 ทั้งคู่ (x, y
ณ 1) ก็จะได้ว่า d
ณ m + n ซึ่งเป็นไปไม่ได้ เพราะจาก d = (m, n) แสดงว่า d
ฃ m และ d
ฃ n จึงเหลือเพียงกรณีเดียวคือ เครื่องหมายต่างกัน โดยไม่เสียนัยสำคัญ จะสมมติให้ x > 0 , y
ฃ 0 (ถ้า y = 0 ยังคงมั่นใจได้ว่า d > 0)
สมมติว่ามีจำนวนเต็มบวกตัวอื่นนอกเหนือไปจาก a
d - 1 ซึ่งหารทั้ง a
m - 1 และ a
n - 1 ลงตัว คือ c โดยที่ c | a
m - 1 และ c | a
n - 1 จะแสดงว่า c | a
d - 1 ดังนี้
จะได้ว่า c | (a
mx - 1) เพราะ a
mx - 1 = (a
x)
m - 1
m (x > 0)
และ c | (a
-ny - 1) เพราะ a
-ny - 1 = (a
-y)
n - 1
n (y
ฃ 0)
\ c | [ (a
mx - 1) - a
d(a
-ny - 1) ] (c | a
ู c | b
ฎ c | ax + by)
ฎ c | [ (a
mx - 1) - a
mx + ny(a
-ny - 1)
ฎ c | (a
mx + ny - 1) หรือ c | (a
d - 1) นั่นคือ c
ฃ a
d - 1
\ a
d - 1 หรือ a
(m, n) - 1 จะเป็น ห.ร.ม. ของ (a
m - 1, a
n - 1)
ฎ (5
2547 - 1, 5
2004 - 1) = 5
(2547, 2004) - 1= 5
7 - 1