สูตรเมื่อสมัยเด็ก - วิธีการหาห.ร.ม.ของยูคลิด

มีคนมาทำให้นึกถึงสูตรเมื่อสมัยเด็กอีกแล้ว ... ใครที่ยังความจำเลือนลาง ลองมาหาห.ร.ม.ของ 20 กับ 88 ด้วยวิธีของยูคลิดกันก่อน

88	=	(4)20 + 8
20	=	(2)8 + 4
8	=	(2)4

ดังนั้น 4 จึงเป็นห.ร.ม.ของ 20 กับ 88 ... แต่ทำไมหละ?

มอง ๆ ดู จะเห็นว่าสมการแต่ละอัน มันเขียนได้เป็น

a = qb + r

โดยที่ q เป็นจำนวนเต็มที่มากที่สุด ที่ทำให้ 0 ≤ r < b

เราจะพิสูจน์ว่า ห.ร.ม. ของ a กับ b มันเท่ากับ ห.ร.ม. ของ b กับ r นะ

เริ่มโดยกำหนดให้

x = ห.ร.ม. ของ a กับ b → x หาร a และ b ลงตัว
y = ห.ร.ม. ของ b กับ r → y หาร a และ b ลงตัว

ดังนั้น จะสามารถหาจำนวนเต็ม A B B' R' ที่ทำให้...

a = Ax
b = Bx = B'y
r = R'y

ได้ คราวนี้เราจะพิสูจน์ว่า x กับ y เป็นตัวเดียวกัน

เริ่มโดยแทนค่าเหล่านี้ลงไปในสมการแรก ครั้งแรกแทนด้วย a = Ax และ b = Bx สมการจะกลายเป็น

Ax = Bxq + r
(A - Bq)x = r

ดังนั้น x หาร r ลงตัว

แล้วก็ แทนค่าในสมการแรกอีกครั้งด้วย b = B'y และ r = R'y จะได้

a = B'yq + R'y
a = y(B'q + R')

ดังนั้น y หาร a ลงตัว

จากที่คิด ๆ มาทั้งหมด จะเห็นว่า

1. x เป็นห.ร.ม.ของ a b และ r
2. y เป็นห.ร.ม.ของ a b และ r

ก็เลยสรุปได้ว่า x = y