ตัวหารร่วมมากของจำนวนเต็มสองจำนวนคือจำนวนมากที่สุดที่หารทั้งสองได้โดยไม่เหลือเศษ

รูปอย่างง่ายที่สุดของขั้นตอนวิธีแบบยุคลิดเริ่มด้วยจำนวนเต็มบวกคู่หนึ่ง และสร้างจำนวนคู่หนึ่งที่ประกอบด้วยจำนวนที่น้อยกว่าและผลต่างระหว่างจำนวนทั้งสอง กระบวนการทำซ้ำจนจำนวนทั้งสองเท่ากัน จำนวนสุดท้ายเป็นตัวหารร่วมมากของจำนวนเต็มบวกที่ขั้นตอนเริ่ม

หลักการสำคัญคือ หรม. ไม่เปลี่ยนค่าถ้านำจำนวนที่น้อยกว่าลบจำนวนที่มากกว่า เช่น หรม. ของ 252 และ 105 เท่ากับ หรม. ของ 147 (= 252 − 105) และ 105 เพราะว่าจำนวนที่มากกว่าถูกลด การทำวิธีนี้ซ้ำทำให้ได้จำนวนเล็กลง การซ้ำนี้จึงจบอย่างแน่นอนเมื่อทั้งสองจำนวนมีค่าเท่ากัน (ถ้าทำอีกหนึ่งครั้ง จำนวนใดจำนวนหนึ่งจะเป็น 0)

ข้อความเดิมเขียนโดยคุณ Thamma (ข้อความที่ 186278) หาจํานวนเต็มบวก $x$ ที่มากที่สุดที่ทำให้ $\frac{(x-2)^2(x+1)}{2x-1}$ เป็นจํานวนเต็ม $\text{gcd}(a, b)$ หมายถึง หรม. ของ $a$ และ $b$ $d \mid n$ หมายถึง $n$ หารด้วย $d$ ลงตัว โดยขั้นตอนวิธีแบบยุคลิด, ตัวหารร่วมมากของจำนวนเต็มสองจำนวนคือจำนวนมากที่สุดที่หารทั้งสองได้โดยไม่เหลือเศษ รูปอย่างง่ายที่สุดของขั้นตอนวิธีแบบยุคลิดเริ่มด้วยจำนวนเต็มบวกคู่หนึ่ง และสร้างจำนวนคู่หนึ่งที่ประกอบด้วยจำนวนที่น้อยกว่าและผลต่างระหว่างจำนวนทั้งสอง กระบวนการทำซ้ำจนจำนวนทั้งสองเท่ากัน จำนวนสุดท้ายเป็นตัวหารร่วมมากของจำนวนเต็มบวกที่ขั้นตอนเริ่ม หลักการสำคัญคือ หรม. ไม่เปลี่ยนค่าถ้านำจำนวนที่น้อยกว่าลบจำนวนที่มากกว่า เช่น หรม. ของ 252 และ 105 เท่ากับ หรม. ของ 147 (= 252 − 105) และ 105 เพราะว่าจำนวนที่มากกว่าถูกลด การทำวิธีนี้ซ้ำทำให้ได้จำนวนเล็กลง การซ้ำนี้จึงจบอย่างแน่นอนเมื่อทั้งสองจำนวนมีค่าเท่ากัน (ถ้าทำอีกหนึ่งครั้ง จำนวนใดจำนวนหนึ่งจะเป็น 0) จะได้ว่า $\text{gcd}(x-2,2x-1)=\text{gcd}(x-2,3) \leq 3$ (อาจเป็น $1$ หรือ $3$) $\text{gcd}(x+1,2x-1)=\text{gcd}(x+1,3) \leq 3$ (อาจเป็น $1$ หรือ $3$) ดังนั้น $\text{gcd}((x-2)^2(x+1),2x-1)\leq 3^3 $ สมมุติว่า $2x-1>3^3$ จะได้ว่ามีจำนวนเฉพาะ $p$ ที่ $p \mid 2x-1$ แต่ $ p \not\mid (x-2)^2(x+1)$ ทำให้ $2x-1 \not\mid (x-2)^2(x+1)$ ซึ่งขัดแย้ง ดังนั้น $2x-1=3^y$ และ $ y \leq 3$ จะได้ $x=\frac{3^y+1}{2}$ โดย $x$ จะมีค่ามากที่สุด เมื่อ $y =3$