ขั้นตอนวิธีของยูคลิด

ขั้นตอนวิธีของยูคลิด (Euclidean Algorithm) เป็นเครื่องมือและกระบวนการทางคณิตศาสตร์ที่มีประสิทธิภาพสูง ใช้สำหรับหา ตัวหารร่วมมาก (ห.ร.ม.) หรือ Greatest Common Divisor (GCD) ของจำนวนเต็มสองจำนวนที่มีค่ามากๆ โดยไม่ต้องแยกตัวประกอบ แต่ใช้วิธีการหารเอาเศษซ้ำๆ กันจนกว่าจะหารลงตัว

The Euclidean Algorithm is a highly efficient mathematical process used to find the Greatest Common Divisor (GCD) of two large integers without needing to prime factorize them. It utilizes repeated division with remainders until an exact division is reached.

กระบวนการและรูปแบบสมการ / Process & Format

กำหนดให้ $a$ และ $b$ เป็นจำนวนเต็มบวก โดยที่ $a > b$ เราสามารถเขียนสมการการหารตาม ขั้นตอนวิธีตรรกยะ (Division Algorithm) ได้ในรูปแบบ $a = bq + r$ (ตัวตั้ง = ตัวหาร $\times$ ผลหาร + เศษ) จากนั้นให้นำ "ตัวหาร" และ "เศษ" มาตั้งหารกันไปเรื่อยๆ ตามรูปแบบดังนี้:

$$ \begin{aligned} a &= bq_1 + r_1 \quad &(0 < r_1 < b) \\ b &=r_1q_2 + r_2 \quad &(0 < r_2 < r_1) \\ r_1 &=r_2q_3 + r_3 \quad &(0 < r_3 < r_2) \\ &\ \ \vdots \\ r_{k-2} &=r_{k-1}q_k + r_k \quad &(0 < r_k < r_{k-1}) \\ r_{k-1} &=r_kq_{k+1} + 0 \quad &(\text{เศษเป็น } 0) \end{aligned} $$

สรุป: ห.ร.ม. ของ $a$ และ $b$ คือ เศษตัวสุดท้ายที่ไม่ใช่ศูนย์ (ในที่นี้คือ $r_k$)

Let $a$ and $b$ be positive integers with $a > b$. Applying the Division Algorithm, we can write $a = bq + r$ (Dividend = Divisor $\times$ Quotient + Remainder). We continuously divide the previous divisor by the previous remainder as follows:

Conclusion: The GCD of $a$ and $b$ is the last non-zero remainder (which is $r_k$).

ตัวอย่างการคำนวณ / Calculation Examples

หมายเหตุ: ใช้สัญลักษณ์ $(a, b)$ แทนความหมายของ ห.ร.ม. ของ $a$ และ $b$ หรือ $\text{GCD}(a,b)$

Example 1 : การหา ห.ร.ม. พื้นฐาน 2 ขั้นตอน

จงหา ห.ร.ม. ของ $48$ และ $18$

$$ \begin{aligned} 48 &= 18(2) + 12 \quad &\text{(เอา } 48 \text{ ตั้ง หารด้วย } 18 \text{ ได้เศษ } 12 \text{)} \\ 18 &= 12(1) + 6 \quad &\text{(ขยับ } 18 \text{ มาเป็นตัวตั้ง และ } 12 \text{ เป็นตัวหาร)} \\ 12 &= \mathbf{6}(2) + 0 \quad &\text{(เศษเป็น } 0 \text{ แล้ว หยุดการคำนวณ)} \end{aligned} $$

เศษตัวสุดท้ายที่ไม่ใช่ $0$ คือ $6$
$\therefore \text{ห.ร.ม. ของ } 48 \text{ และ } 18 \text{ คือ } 6$ หรือเขียนย่อว่า $(48, 18) = 6$

Find the GCD of $48$ and $18$.

$$ \begin{aligned} 48 &= 18(2) + 12 \quad &\text{($48$ divided by $18$ leaves remainder $12$)} \\ 18 &= 12(1) + 6 \quad &\text{(Shift $18$ to dividend and $12$ to divisor)} \\ 12 &= \mathbf{6}(2) + 0 \quad &\text{(Remainder is $0$, stop.)} \end{aligned} $$

The last non-zero remainder is $6$.
$\therefore \text{GCD}(48, 18) = 6$

Example 2 : ตัวเลขหลักร้อย

จงหาค่าของ $(252, 105)$

$$ \begin{aligned} 252 &= 105(2) + 42 \\ 105 &= 42(2) + 21 \\ 42 &= \mathbf{21}(2) + 0 \end{aligned} $$

$\therefore (252, 105) = 21$

Evaluate $(252, 105)$.

$$ \begin{aligned} 252 &= 105(2) + 42 \\ 105 &= 42(2) + 21 \\ 42 &= \mathbf{21}(2) + 0 \end{aligned} $$

$\therefore \text{GCD}(252, 105) = 21$

Example 3 : กรณีที่หารลงตัวตั้งแต่ขั้นตอนแรก

จงหา ห.ร.ม. ของ $100$ และ $25$

$$ \begin{aligned} 100 &= \mathbf{25}(4) + 0 \end{aligned} $$

เนื่องจากหารลงตัวทันที เศษคือ $0$ แสดงว่าตัวหารนั้นคือ ห.ร.ม. ได้เลย
$\therefore (100, 25) = 25$

Find the GCD of $100$ and $25$.

$$ \begin{aligned} 100 &= \mathbf{25}(4) + 0 \end{aligned} $$

Since it divides evenly in the first step, the divisor itself is the GCD.
$\therefore \text{GCD}(100, 25) = 25$

Example 4 : จำนวนเฉพาะสัมพัทธ์ (ห.ร.ม. เท่ากับ 1)

จงหาค่าของ $(71, 15)$

$$ \begin{aligned} 71 &= 15(4) + 11 \\ 15 &= 11(1) + 4 \\ 11 &= 4(2) + 3 \\ 4 &= 3(1) + 1 \\ 3 &= \mathbf{1}(3) + 0 \end{aligned} $$

เศษสุดท้ายที่ไม่ใช่ศูนย์คือ $1$ (ทั้งสองจำนวนไม่มีตัวประกอบร่วมกันนอกจาก 1)
$\therefore (71, 15) = 1$

Evaluate $(71, 15)$.

$$ \begin{aligned} 71 &= 15(4) + 11 \\ 15 &= 11(1) + 4 \\ 11 &= 4(2) + 3 \\ 4 &= 3(1) + 1 \\ 3 &= \mathbf{1}(3) + 0 \end{aligned} $$

The last non-zero remainder is $1$ (They are relatively prime).
$\therefore \text{GCD}(71, 15) = 1$

Example 5 : ตัวเลขหลักพัน (ข้อสอบบ่อย)

จงหา ห.ร.ม. ของ $1239$ และ $735$

$$ \begin{aligned} 1239 &= 735(1) + 504 \\ 735 &= 504(1) + 231 \\ 504 &= 231(2) + 42 \\ 231 &= 42(5) + 21 \\ 42 &= \mathbf{21}(2) + 0 \end{aligned} $$

$\therefore (1239, 735) = 21$

Find the GCD of $1239$ and $735$.

$$ \begin{aligned} 1239 &= 735(1) + 504 \\ 735 &= 504(1) + 231 \\ 504 &= 231(2) + 42 \\ 231 &= 42(5) + 21 \\ 42 &= \mathbf{21}(2) + 0 \end{aligned} $$

$\therefore \text{GCD}(1239, 735) = 21$

Example 6 : การหา ห.ร.ม. ของจำนวนเต็มลบ

จงหา ห.ร.ม. ของ $-504$ และ $1188$

ตามทฤษฎีบท: ห.ร.ม. ของจำนวนเต็มใดๆ จะเป็นบวกเสมอ ดังนั้น $(a, b) = (|a|, |b|)$

$$ \begin{aligned} \text{จะได้ว่า } (-504, 1188) &= (504, 1188) \\ 1188 &= 504(2) + 180 \\ 504 &= 180(2) + 144 \\ 180 &= 144(1) + 36 \\ 144 &= \mathbf{36}(4) + 0 \end{aligned} $$

$\therefore (-504, 1188) = 36$

Find the GCD of $-504$ and $1188$.

By theorem: The GCD is always positive, so $\text{GCD}(a, b) = \text{GCD}(|a|, |b|)$

$$ \begin{aligned} \text{Thus, } \text{GCD}(-504, 1188) &= \text{GCD}(504, 1188) \\ 1188 &= 504(2) + 180 \\ 504 &= 180(2) + 144 \\ 180 &= 144(1) + 36 \\ 144 &= \mathbf{36}(4) + 0 \end{aligned} $$

$\therefore \text{GCD}(-504, 1188) = 36$

Example 7 : จำนวนฟีโบนัชชี (Fibonacci Sequence)

จงหา ห.ร.ม. ของ $55$ และ $34$ (ลำดับที่ติดกันของลำดับฟีโบนัชชี)

น่ารู้: ลำดับฟีโบนัชชีที่อยู่ติดกัน จะทำให้เกิดขั้นตอนการหาของยูคลิดที่ยาวที่สุดเมื่อเทียบกับขนาดตัวเลข และ ห.ร.ม. จะเป็น 1 เสมอ

$$ \begin{aligned} 55 &= 34(1) + 21 \\ 34 &= 21(1) + 13 \\ 21 &= 13(1) + 8 \\ 13 &= 8(1) + 5 \\ 8 &= 5(1) + 3 \\ 5 &= 3(1) + 2 \\ 3 &= 2(1) + 1 \\ 2 &= \mathbf{1}(2) + 0 \end{aligned} $$

$\therefore (55, 34) = 1$

Find the GCD of $55$ and $34$ (Consecutive Fibonacci numbers).

Fun Fact: Consecutive Fibonacci numbers require the most steps in the Euclidean algorithm for their size, and their GCD is always 1.

$$ \begin{aligned} 55 &= 34(1) + 21 \\ 34 &= 21(1) + 13 \\ 21 &= 13(1) + 8 \\ 13 &= 8(1) + 5 \\ 8 &= 5(1) + 3 \\ 5 &= 3(1) + 2 \\ 3 &= 2(1) + 1 \\ 2 &= \mathbf{1}(2) + 0 \end{aligned} $$

$\therefore \text{GCD}(55, 34) = 1$

คำศัพท์ที่น่าสนใจ / Key Vocabulary

คำศัพท์คณิตศาสตร์ภาษาอังกฤษ พร้อมรากศัพท์

คำศัพท์	รากศัพท์ / Root	ความหมาย / Meaning
Euclidean Algorithm	Eukleidēs (Greek) + algorismus (Arabic)	ขั้นตอนวิธีของยูคลิด · อัลกอริทึมสำหรับหาตัวหารร่วมมากโดยการหารเอาเศษซ้ำๆ
Greatest Common Divisor (GCD)	dividere (to force apart, divide)	ตัวหารร่วมมาก (ห.ร.ม.) · จำนวนเต็มบวกที่มีค่ามากที่สุดที่นำไปหารกลุ่มจำนวนที่กำหนดได้ลงตัว
Divisibility	dividere (to force apart, divide)	การหารลงตัว · คุณสมบัติของจำนวนเต็มที่สามารถหารด้วยอีกจำนวนเต็มหนึ่งได้โดยไม่มีเศษ (เศษเป็น 0)
Quotient	quotiens (how many times)	ผลหาร · ผลลัพธ์ที่ได้จากการนำจำนวนหนึ่งไปหารด้วยอีกจำนวนหนึ่ง
Remainder	re- (back) + manere (to stay)	เศษ · จำนวนที่เหลือจากการหารที่ไม่ลงตัว
Relatively Prime	relativus (reference) + primus (first)	จำนวนเฉพาะสัมพัทธ์ · จำนวนเต็มสองจำนวนที่ไม่มีตัวประกอบร่วมกันนอกจาก 1 (ห.ร.ม. = 1)