Giải thuật Euclid
Chú thích

↑  Stark 1978, tr. 16
↑  Stark 1978, tr. 21
↑  LeVeque 1996, tr. 32
↑  LeVeque 1996, tr. 31
↑  Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan. tr. 213. ISBN 0-02-348331-8.
↑  Schroeder 2005, tr. 21–22
↑  Schroeder 2005, tr. 19
↑  Ogilvy, C. S.; Anderson, J. T. (1966). Excursions in number theory. New York: Oxford University Press. tr. 27–29.
↑  Schroeder 2005, tr. 216–219
↑  LeVeque 1996, tr. 33
↑  Stark 1978, tr. 25
↑  Ore 1948, tr. 47–48
↑  Stark 1978, tr. 18
↑  Stark 1978, tr. 16–20
↑  Knuth 1997, tr. 320
↑  Lovász, L.; Pelikán, J.; Vesztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. tr. 100–101. ISBN 0-387-95584-4.
↑  Kimberling, C. (1983). “A Visual Euclidean Algorithm”. Mathematics Teacher. 76: 108–109.
↑  Dummit, David S.; Foote, Richard M. (2004). Abstract Algebra. John Wiley & Sons, Inc. tr. 270-271. ISBN 978-0-471-43334-7.
↑  Knuth 1997, tr. 319–320
↑  Knuth 1997, tr. 318–319
↑  Stillwell 1997, tr. 14
1 2  Ore 1948, tr. 43
1 2  Stewart, B. M. (1964). Theory of Numbers (ấn bản thứ 2). New York: Macmillan. tr. 43–44. LCCN 64010964.
↑  Lazard, D. (1977). “Le meilleur algorithme d'Euclide pour K[X] et Z”. Comptes rendus de l'Académie des Sciences (bằng tiếng Pháp). 284: 1–4.
1 2  Knuth 1997, tr. 318
↑  Weil, A. (1983). Number Theory. Boston: Birkhäuser. tr. 4–6. ISBN 0-8176-3141-0.
↑  Jones, A. (1994). “Greek mathematics to AD 300”. Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. tr. 46–48. ISBN 0-415-09238-8.
↑  van der Waerden, B. L. (1954). Science Awakening. Arnold Dresden dịch. Groningen: P. Noordhoff Ltd. tr. 114–115.
↑  von Fritz, K. (1945). “The Discovery of Incommensurability by Hippasus of Metapontum”. Annals of Mathematics. 46 (2): 242–264. doi:10.2307/1969021. JSTOR 1969021.
↑  Heath, T. L. (1949). Mathematics in Aristotle. Oxford Press. tr. 80–83.
↑  Fowler, D. H. (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. tr. 31–66. ISBN 0-19-853912-6.
↑  Becker, O. (1933). “Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid”. Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333.
1 2  Stillwell 1997, tr. 31
1 2  Tattersall 2005, tr. 70
↑  Rosen 2000, tr. 86–87
↑  Ore 1948, tr. 247–248
↑  Tattersall 2005, tr. 72, 184–185
↑  Saunderson, Nicholas (1740). The Elements of Algebra in Ten Books. University of Cambridge Press. Truy cập ngày 6 tháng 7 năm 2020.
↑  Tattersall 2005, tr. 72–76
↑  Gauss, C. F. (1832). “Theoria residuorum biquadraticorum”. Comm. Soc. Reg. Sci. Gött. Rec. 4. In lại trong Gauss, C. F. (2011). “Theoria residuorum biquadraticorum commentatio prima”. Werke. 2. Cambridge Univ. Press. tr. 65–92. doi:10.1017/CBO9781139058230.004. và Gauss, C. F. (2011). “Theoria residuorum biquadraticorum commentatio secunda”. Werke. 2. Cambridge Univ. Press. tr. 93–148. doi:10.1017/CBO9781139058230.005.
↑  Stillwell 1997, tr. 31–32
↑  Lejeune Dirichlet 1894, tr. 29–31
↑  Richard Dedekind trong Lejeune Dirichlet 1894, phụ lục XI
↑  Stillwell 2003, tr. 41–42
↑  Sturm, C. (1829). “Mémoire sur la résolution des équations numériques”. Bull. des sciences de Férussac (bằng tiếng Pháp). 11: 419–422.
↑  Weisstein, Eric W., "Integer Relation" từ MathWorld.
↑  Peterson, I. (ngày 12 tháng 8 năm 2002). “Jazzing Up Euclid's Algorithm”. ScienceNews.
↑  Cipra, Barry Arthur (ngày 16 tháng 5 năm 2000). “The Best of the 20th Century: Editors Name Top 10 Algorithms” (PDF). SIAM News. Society for Industrial and Applied Mathematics. 33 (4). Bản gốc (PDF) lưu trữ ngày 22 tháng 9 năm 2016. Truy cập ngày 6 tháng 7 năm 2020.
↑  Cole, A. J.; Davie, A. J. T. (1969). “A game based on the Euclidean algorithm and a winning strategy for it”. Math. Gaz. 53 (386): 354–357. doi:10.2307/3612461. JSTOR 3612461.
↑  Spitznagel, E. L. (1973). “Properties of a game based on Euclid's algorithm”. Math. Mag. 46 (2): 87–92. doi:10.2307/2689037. JSTOR 2689037.
↑  Rosen 2000, tr. 95
↑  Roberts, J. (1977). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. tr. 1–8. ISBN 0-262-68028-9.
Một hình chữ nhật kích thước 24 × 60 được chia thành 10 hình vuông nhỏ cạnh 12, trong đó 12 là ƯCLN của 24 và 60. Tổng quát hơn, một hình chữ nhật kích thước a × b có thể được chia thành các hình vuông cạnh c khi và chỉ khi c là ước chung của a và b.
Hình ảnh động minh họa giải thuật Euclid qua phép trừ. Hình chữ nhật ban đầu có hai cạnh a = 1071 và b = 462. Đặt vào đó các hình vuông kích thước 462 × 462 thì còn lại hình chữ nhật 462 × 147. Tiếp tục đặt vào hình chữ nhật đó các hình vuông 147 × 147 đến khi còn lại hình chữ nhật 21 × 147. Cuối cùng, đặt vào phần hình còn lại đó các hình vuông 21 × 21 thì không còn chỗ trống nào. Cạnh của hình vuông nhỏ nhất, 21, chính là ƯCLN của 1071 và 462.
Giải thuật Euclid có thể đã xuất hiện từ trước thời của Euclid, người đang cầm com-pa trong một tranh vẽ khoảng năm 1474.