ขั้นตอนวิธีแบบยุคลิด

วิธีของยุคลิดสำหรับหาตัวหารร่วมมาก (หรม.) ของความยาวเริ่มต้น BA และ DC ซึ่งต่างนิยามให้เป็นพหุคูณของความยาว"หน่วย"เดียวกัน เพราะว่า DC สั้นกว่าจึงใช้"วัด" BA แต่เพียงครั้งเดียวเพราะเศษ EA น้อยกว่า CD ใช้ EA วัดความยาว DC ที่สั้นกว่าสองครั้ง จะเหลือเศษ FC สั้นกว่า EA แล้วใช้ FC วัดความยาว EA สามครั้ง เพราะว่าขั้นตอนนี้ไม่มีเศษ จึงจบโดยมี FC เป็น หรม. ด้านขวาเป็นตัวอย่างของนิโคมาคัสโดยจำนวน 49 และ 21 ให้ผลลัพธ์ค่าตัวหารร่วมมากเป็น 7 (ประยุกต์จาก Heath 1908:300)

ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด (อังกฤษ: Euclidean Algorithm)^[a] หรือขั้นตอนวิธีของยุคลิด เป็นวิธีคำนวณตัวหารร่วมมาก (หรม.) ของจำนวนเต็มสองจำนวน ตั้งชื่อตามยุคลิด นักคณิตศาสตร์ชาวกรีกผู้อธิบายทฤษฎีนี้ในอิลิเมนต์ของยุคลิดเล่ม VII และ X ^[1]

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

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

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

หลักฐานเกี่ยวกับขั้นตอนวิธีแบบยุคลิดพบในหนังสือ Elements ของยุคลิด (ในช่วงศตวรรษที่ 3 ก่อนคริสตกาล) ทำให้เป็นขั้นตอนวิธีเก่าแก่ที่สุดเกี่ยวกับจำนวนที่ยังใช้โดยทั่วไป ขั้นตอนวิธีฉบับดังเดิมใช้สำหรับจำนวนธรรมชาติและความยาวเชิงเรขาคณิต (จำนวนจริง) แต่นักคณิตศาสตร์ได้ขยายการใช้งานไปยังจำนวนชนิดอื่น เช่น จำนวนเต็มเกาส์เซียนและพหุนามหนึ่งตัวแปร อันนำไปสู่แนวคิดเชิงพีชคณิตนามธรรมสมัยใหม่ เช่นโดเมนแบบยุคลิด ขั้นตอนวิธีของยุคลิดได้นำไปใช้กับโครงสร้างทางคณิตศาสตร์อื่นๆ เช่น เงื่อน และพหุนามหลายตัวแปร

ขั้นตอนวิธีนี้มีการประยุกต์ใช้ในทางทฤษฎีและปฏิบัติ อาจใช้ก่อกำเนิดจังหวะดนตรีที่สำคัญหลายรูปแบบที่พบในวัฒนธรรมต่างๆ ทั่วโลก^[2] ขั้นตอนวิธีนี้เป็นส่วนประกอบสำคัญของการเข้ารหัสอาร์เอสเอ (การเข้ารหัสลับแบบกุญแจอสมมาตรที่ใช้ทั่วไปในการพาณิชย์อิเล็กทรอนิกส์) ขั้นตอนวิธีนี้ใช้แก้สมการไดโอแฟนไทน์ เช่นการหาจำนวนที่สอดคล้องกับสมภาคหลายชุด(ทฤษฎีบทเศษเหลือของจีน) หรือ ตัวผกผันการคูณของเซตจำกัด และยังสามารถใช้สร้างเศษส่วนต่อเนื่องด้วยวิธีโซ่ของสเติร์มสำหรับหารากจำนวนจริงของพหุนาม และในขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มสมัยใหม่ ที่สำคัญ เป็นเครื่องมือสำหรับพิสูจน์ทฤษฎีบทในทฤษฎีจำนวนสมัยใหม่ เช่นทฤษฎีบทผลรวมกำลังสองของลากรองจ์และทฤษฎีบทมูลฐานของเลขคณิต

ถ้าปรับปรุงขั้นตอนวิธีให้ใช้เศษหารจากวิธีหารแบบยุคลิดแทนที่จะเป็นการลบ ขั้นตอนวิธีของยุคลิดคำนวณค่าตัวหารร่วมมากของจำนวนขนาดใหญ่อย่างมีประสิทธิภาพ: ขั้นตอนวิธีนี้ไม่ใช้ขั้นตอนการหารจำนวนมากกว่าห้าเท่าของจำนวนหลัก(สำหรับเลขฐานสิบ)ของจำนวนขนาดเล็กกว่า โดย Gabriel Lamé พิสูจน์เมื่อปี ค.ศ. 1844 และริเริ่มการศึกษา ทฤษฎีความซับซ้อนในการคำนวณ วิธีเพิ่มประสิทธิภาพของขั้นตอนวิธีได้พัฒนาในคริสต์ศตวรรษที่ 20

เมื่อย้อนขั้นตอนวิธีแบบยุคลิด ตัวหารร่วมมากสามารถเขียนในรูปผลรวมเชิงเส้นของสองจำนวนที่นำมาดำเนินการ แต่ละจำนวนคูณกับจำนวนเต็ม เช่น ตัวหารร่วมมากของ 252 และ 105 คือ 21 และ 21 = [5 × 105] + [(−2) × 252] สมบัตินี้เรียกว่าเอกลักษณ์ของเบซู

พื้นฐาน — ตัวหารร่วมมาก[แก้]

ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของจำนวนธรรมชาติสองจำนวน a และ b ค่าตัวหารร่วมมาก g เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง a และ b ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ ตัวประกอบร่วมค่ามากสุด (อังกฤษ: greatest common factor, GCF), ตัวประกอบร่วมค่ามากสุด (อังกฤษ: highest common factor, HCF) และ greatest common measure (GCM) ตัวหารร่วมมากมักเขียนแทนด้วย gcd(a, b) หรือ (a, b),^[3] แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ

ถ้า gcd(a, b) = 1 แล้ว a กับ b เป็นจำนวนเฉพาะสัมพัทธ์^[4] ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า a หรือ b เป็นจำนวนเฉพาะเองแต่อย่างใด^[5] เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6 = 2 × 3 and 35 = 5 × 7 อย่างไรก็ตาม 6 และ 35 เป็นจำนวนเฉพาะสัมพัทธ์ ไม่มีจำนวนธรรมชาตินอกเหนือจาก 1 หารทั้ง 6 และ 35 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน

"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."

สี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 ประกอบด้วยสี่เหลี่ยมขนาดด้านละ 12 จำนวนสิบรูป ซึ่ง 12 คือตัวหารร่วมมากของ 24 และ 60 ในกรณีทั่วไป สี่เหลี่ยมผืนผ้ากว้าง a ยาว b จะแบ่งเป็นสี่เหลี่ยมจัตุรัสย่อยด้านละ c ได้เฉพาะในกรณีที่ c เป็นตัวหารร่วมของ a และ b

ให้ g = gcd(a, b) จากการที่ a และ b เป็นพหุคูณของ g สามารถเขียนในรูป a = mg และ b = ng และไม่มีจำนวนเต็ม G ที่มากกว่า g ที่ทำให้ข้อความดังกล่าวเป็นจริง m และ n ต้องเป็นจำนวนเฉพาะสัมพัทธ์ เพราะหากมีตัวประกอบร่วมของ m และ n จะทำให้ g มีค่ามากขึ้น ดังนั้นจำนวนเต็ม c ใด ๆ ที่หาร a และ b ลงตัว จะต้องหาร g ลงตัวด้วย ตัวหารร่วมมาก g ของ a และ b คือตัวหารร่วมบวกเพียงหนึ่งตัวของ a และ b ที่หารด้วยตัวหารร่วมอื่น c ลงตัว

ตัวหารร่วมมากสามารถอธิบายได้ด้วยการสมมติสี่เหลี่ยมผืนผ้ากว้าง a ยาว b และตัวหารร่วม c ที่หาร a และ b ลงตัว ด้านของสี่เหลี่ยมสามารถแบ่งเป็นส่วนย่อยยาว c ซึ่งแบ่งสี่เหลี่ยมผืนผ้าเป็นตารางสี่เหลี่ยมจัตุรัสย่อยยาวด้านละ c โดยตัวหารร่วมมาก g คือค่าที่มากที่สุดที่เป็นไปได้ของ c ตัวอย่างดังภาพคือสี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 สามารถแบ่งได้เป็นตารางของสี่เหลี่ยมจัตุรัส 1 $\times$ 1, สี่เหลี่ยมจัตุรัส 2 $\times$ 2, สี่เหลี่ยมจัตุรัส 3 $\times$ 3, สี่เหลี่ยมจัตุรัส 4 $\times$ 4, สี่เหลี่ยมจัตุรัส 6 $\times$ 6 หรือสี่เหลี่ยมจัตุรัส 12 $\times$ 12 ดังนั้น 12 คือตัวหารร่วมมากของ 24 และ 60 โดยสี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 สามารถแบ่งเป็นตารางของสี่เหลี่ยมจัตุรัสยาวด้านละ 12 ที่มีสี่เหลี่ยมจัตุรัส 2 รูปติดด้านกว้าง (24/12 = 2) และสี่เหลี่ยมจัตุรัส 5 รูปติดด้านยาว (60/12 = 5)

ตัวหารร่วมมากของสองจำนวน a และ b คือผลคูณของตัวประกอบเฉพาะที่สองจำนวนนี้มีร่วมกัน โดยตัวประกอบเฉพาะหนึ่งค่าสามารถนำมาคูณได้หลายรอบ ตราบที่ผลคูณของตัวประกอบเหล่านี้หาร a และ b ลงตัว ตัวอย่างเช่น 1386 แยกตัวประกอบได้เป็น 2 $\times$ 3 $\times$ 3 $\times$ 7 $\times$ 11 และ 3213 แยกตัวประกอบได้เป็น 3 $\times$ 3 $\times$ 3 $\times$ 7 $\times$ 17 ตัวหารร่วมมากของ 1386 และ 3213 จึงเท่ากับ 63 = 3 $\times$ 3 $\times$ 7 ซึ่งก็คือผลคูณของตัวประกอบเฉพาะร่วม ถ้าสองจำนวนไม่มีตัวประกอบเฉพาะร่วมกัน ตัวหารร่วมมากคือ 1 (เท่ากับค่าผลคูณว่าง) หรือก็คือทั้งสองจำนวนนั้นเป็นจำนวนเฉพาะสัมพัทธ์ ข้อได้เปรียบของขั้นตอนวิธีแบบยุคลิดคือสามารถหาค่าตัวหารร่วมมากโดยไม่ต้องหาตัวประกอบเฉพาะร่วม

หรม. ของสามจำนวนขึ้นไปมีค่าเท่ากับผลคูณของตัวประกอบเฉพาะของจำนวนเหล่านั้น แต่ก็สามารถหาได้จากการหา หรม. ของแต่ละคู่จำนวน

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).

ดังนั้นขั้นตอนวิธีแบบยูคลิดที่หาหรม.ของสองจำนวนจะสามารถหาหรม.ของหลายจำนวนได้ด้วยเช่นกัน

คำอธิบาย[แก้]

กระบวนการ[แก้]

ขั้นตอนวิธีแบบยูคลิดดำเนินเป็นขั้นตอน โดยผลลัพธ์ในแต่ละขั้นตอนจะถูกใช้ในขั้นตอนต่อไป ให้ k เป็นจำนวนเต็มที่นับจำนวนขั้นตอนในวิธีการยูคลิด เริ่มจากศูนย์ ดังนั้นในขั้นตอนที่หนึ่งมีค่า k = 0 ขั้นตอนที่สองมีค่า k = 1 เป็นแบบนี้ไปเรื่อย ๆ

แต่ละขั้นตอนเริ่มด้วยเศษสองจำนวนที่มีค่าไม่เป็นลบ r_k−1 และ r_k−2 เนื่องจากวิธีการนี้จะทำให้เศษมีค่าลดลงในทุกขั้นตอนเสมอ r_k−1 มีค่าน้อยกว่าเศษตัวก่อน r_k−2 เป้าหมายของขั้นตอนที่ k คือหาผลหาร q_k และเศษ r_k ที่สอดคล้องกับสมการ

r_{k-2}=q_{k}r_{k-1}+r_{k}

จะได้ว่า 0 ≤ r_k < r_k−1 กล่าวได้ว่า จำนวนที่มากกว่า r_k−2 ถูกลบด้วยพหุคูณของจำนวนที่น้อยกว่า r_k−1 จนกว่าเศษ r_k จะมีค่าน้อยกว่า r_k−1

ในขั้นแรก (k = 0) เศษ r₋₂ และ r₋₁ มีค่าเท่ากับ a และ b ตามลำดับ ในขั้นต่อมา (k = 1) เศษมีค่าเท่ากับ b และเศษ r₀ ของขั้นแรก ทำแบบนี้ต่อไปเรื่อย ๆ ขั้นตอนวิธีดังกล่าวเขียนออกมาในรูปแบบลำดับของสมการได้ว่า

{\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\r_{0}&=q_{2}r_{1}+r_{2}\\r_{1}&=q_{3}r_{2}+r_{3}\\&\,\,\,\vdots \end{aligned}}

ถ้า a มีค่าน้อยกว่า b ให้สลับตัวเลขในขั้นแรก ตัวอย่างคือ ถ้า a < b ผลหารในขั้นแรก q₀ จะมีค่าเท่ากับศูนย์ และเศษ r₀ มีค่าเท่ากับ a ดังนั้น r_k จะมีค่าน้อยกว่า r_k−1 สำหรับทุก k ≥ 0

เพราะเศษมีค่าลดลงในทุกขั้นตอน แต่ไม่สามารถเป็นมีค่าเป็นลบ เศษ r_N จึงจะต้องเท่ากับศูนย์ในสักขั้นตอน

การพิสูจน์ความถูกต้อง[แก้]

ความถูกต้องของขั้นตอนวิธีแบบยูคลิดสามารถพิสูจน์ได้โดยสองขั้นตอน ในขั้นตอนแรก เห็นได้ว่าเศษตัวสุดท้ายที่ไม่เท่ากับศูนย์ r_N−1 จะหารทั้ง a และ b ลงตัว เพราะมันเป็นตัวหารร่วม จึงมีค่าน้อยกว่าหรือเท่ากับตัวหารร่วมมาก g และในขั้นตอนที่สอง เห็นได้ว่าตัวหารร่วมใด ๆ ของ a และ b (รวมถึงตัวหารร่วมมาก g ด้วย) ต้องหาร r_N−1 ลงตัว ดังนั้น g ต้องมีค่าน้อยกว่าหรือเท่ากับ r_N−1 ข้อสรุปสองอันนี้ไม่แน่นอน เว้นแต่ r_N−1 = g

เพื่อแสดงให้เห็น

r N -2 = q N r N -1

เพราะ

r N -3 = q N -1 r N -2 + r N -1

ตัวอย่างการใช้งาน[แก้]

แอนิเมชั่นแสดงขั้นตอนวิธีแบบยุคลิดโดยใช้วิธีการลบ แรกเริ่ม สี่เหลี่ยมผืนผ้ามีขนาด a = 1071 และ b = 462 ต่อมา สี่เหลี่ยมจัตุรัสขนาด 462×462 ถูกวางลงไป ทำให้เหลือสี่เหลี่ยมพืนผ้าขนาด 462×147 โดยสี่เหลี่ยมพืนผ้านี้จะถูกวางทับโดยสี่เหลี่ยมจัตุรัสขนาด 147×147 จนกระทั่งเหลือสี่เหลี่ยมพื้นผ้าขนาด 21×147 ที่เหลือก็นำสี่เหลี่ยมจัตุรัสขนาด 21×21 มาวางให้ครบ ทำให้ไม่เหลือพื้นที่ที่ยังไม่ได้ปิด จึงสรุปได้ว่า ขนาดของสี่เหลี่ยมจัตุรัสที่เล็กที่สุด (21) คือ ห.ร.ม. ของ 1071 และ 462

เพื่อให้เห็นภาพ ขั้นตอนวิธีแบบยุคลิดสามารถนำมาใช้หาตัวหารร่วมมากของ a = 1071 และ b = 462 ได้ เริ่มต้นด้วย นำ 1071 เป็นตัวตั้ง ลบกับตัวคูณของ 462 จนกว่าเศษจะน้อยกว่า 462 ซึ่งเมื่อพิจารณาแล้ว การคูณด้วย 2 นั้นสามารถนำมาใช้ในการลบออกได้ (q₀ = 2) โดยมีเศษคือ 147

1071 = 2 \times 462 + 147.

ต่อมา ตัวคูณของ 147 จะถูกลบออกจาก 462 จนกว่าเศษจะมีค่าน้อยกว่า 147 เมื่อพิจารณาแล้ว การคูณด้วย 3 นั้นสามารถนำมาใช้ในการลบออกได้

462 = 3 \times 147 + 21.

ต่อมา ตัวคูณของ 21 จะถูกลบออกจาก 147 จนกว่าเศษจะมีค่าน้อยกว่า 21 ซึ่งการคูณด้วย 7 นั้นสามารถนำมาใช้ในการลบออกได้ (q₂ = 7) ไม่เหลือเศษแล้ว

147 = 7 \times 21 + 0.

ขั้นที่ k	สมการ	ผลหาร (q) และเศษเหลือ (r)
0	$1071 = q 0 462 + r 0$	$q 0 = 2$ และ $r 0 = 147$
1	$462 = q 1 147 + r 1$	$q 1 = 3$ และ $r 1 = 21$
2	$147 = q 2 21 + r 2$	$q 2 = 7$ และ $r 2 = 0$ ; อัลกอริทึมจบลง

การอธิบายเป็นภาพ[แก้]

เราสามารถทำขั้นตอนวิธีแบบยูคลิดให้เห็นภาพได้ โดยใช้วิธีคล้ายกับการปูกระเบื้องในการหาตัวหารร่วมมาก^[6] สมมุติว่าเราต้องการปูพื้นที่สี่เหลี่ยมผืนผ้าขนาด $a\times b$ โดยใช้กระเบื้องสี่เหลี่ยมจัตุรัส โดยที่ a เป็นค่าที่มีค่ามากกว่าอีกจำนวน เริ่มแรก เราจะปูโดยใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด $b\times b$ แต่ว่า กลับเหลือพื้นที่ที่ปูไม่ได้ มีขนาดเป็น $r_{0}\times b$ โดยที่ $r_{0}<b$ เราก็เลยเปลี่ยนไปใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด $r_{0}\times r_{0}$ แทน แต่ก็ยังปูพื้นที่ได้ไม่ครบอีก เหลือพื้นที่เป็น $r_{1}\times r_{0}$ เราก็เลยเปลี่ยนไปใช้กระเบื้องขนาด $r_{1}\times r_{1}$ แทน ทำแบบนี้ซ้ำไปเรื่อย ๆ จนกระทั่งไม่เหลือพื้นที่ที่ยังไม่ได้ปู นั่นคือ เมื่อกระเบื้องสี่เหลียมจัตุรัสสามารถปูพื้นที่ที่ยังไม่ได้ปูในขั้นที่แล้วได้ทั้งหมด โดยความยาวของด้านของสี่เหลี่ยมจัตุรัสที่เล็กที่สุดก็คือตัว ห.ร.ม. ของขนาดของสี่เหลี่ยมรูปต้นแบบนั่นเอง เช่น กระเบื้องสี่เหลี่ยมจัตุรัสขนาดเล็กที่สุดในรูปคือ $21\times 21$ (ในรูปแสดงโดยใช้สีแดง) และ 21 เป็นตัวหารร่วมมากของ 1071 และ 462 ซึ่งเป็นรูปสี่เหลี่ยมต้นฉบับ (แสดงโดยใช้สีเขียว)

การหารแบบยูคลิด[แก้]

ในทุกขั้นตอน

r k -2 = q k r k -1 + r k

r k = r k -2 mod r k -1 .

การนำไปใช้งาน[แก้]

การนำไปใช้งานของขั้นตอนวิธีแบบยูคลิดจะถูกเขียนในรูปแบบโค้ดเทียม

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

ในรูปแบบเรียกซ้ำ^[7] จะขึ้นอยู่กับความเท่ากันของตัวหารร่วมมากของเศษเหลือต่อเนื่อง โดยมีเงื่อนไขการหยุดคือ gcd(r_N−1, 0) = r_N−1

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

(หากค่าที่รับมาเป็นลบ หรือฟังก์ชัน mod อาจให้ค่าที่ติดลบ ต้องเปลี่ยน "return a" เป็น "return max(a, −a)")

หมายเหตุ[แก้]

ก. ^{^} ตำราบางเล่มที่ใช้โดยทั่วไป เช่น Topics in Algebra ของ I. N. Herstein และ Algebra ของ Serge Langใช้คำว่า "Euclidean algorithm" หมายถึงวิธีหารแบบยุคลิด

อ้างอิง[แก้]

↑ Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
↑ http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf
↑ Stark 1978, p. 16
↑ Stark 1978, p. 21
↑ LeVeque 1996, p. 32
↑ Kimberling, C. (1983). "A Visual Euclidean Algorithm". Mathematics Teacher. 76: 108–109.
↑ Stillwell 1997, p. 14

แหล่งข้อมูลอื่น[แก้]

[1] Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

[2] ttp://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf

[3] Stark 1978, p. 16

[4] Stark 1978, p. 21

[5] LeVeque 1996, p. 32

[Kimberling_1983-6] Kimberling, C. (1983). "A Visual Euclidean Algorithm". Mathematics Teacher. 76: 108–109.

[7] Stillwell 1997, p. 14

[a]

[1]

[2]

[3]

[4]

[5]

[6]

[7]