欧几里得算法：计算最大公约数的经典方法
需积分: 12 33 浏览量
更新于2024-07-18
收藏 1.1MB PDF 举报
欧几里得算法是数学中的一个重要概念，它由古希腊数学家欧几里得在公元前300年左右在其著作《原本》（Elements）中首次阐述。这一算法的核心在于高效地计算两个整数的最大公约数（GCD），即能同时整除这两个数且不留余数的最大正整数。由于其简洁高效，欧几里得算法至今仍然是最常用的算法之一，不仅在基础数学教育中占据重要地位，而且在数论、密码学等多个领域有着广泛的应用。
算法的工作原理基于一个基本定理：若a和b是两个整数，且a > b，则它们的最大公约数等于b和a-b的最大公约数。换句话说，每次将较大的数替换为其与较小数的差，直到两数相等或其中一个变为零，此时的非零数就是原两数的最大公约数。例如，为了找出252和105的最大公约数，我们可以一步步地计算：252 = 21 × 12，105 = 21 × 5，所以21就是它们的最大公约数。同理，我们也可以验证21也是105和252 - 105 = 147的最大公约数，因为147 = 21 × 7。
欧几里得算法的实用性体现在多个方面。首先，它可以用于简化分数，将分数化为最简形式，即将分子和分母都除以它们的最大公约数。其次，该算法是许多数值计算和数据处理的基础，比如在计算机编程中，当涉及到除法运算时，用它来优化代码性能，避免因整数溢出而产生的错误。此外，在密码学中，特别是在公钥加密系统如RSA中，欧几里得算法作为关键步骤，用于确定密钥的相关参数。
欧几里得算法作为古老的数学瑰宝，不仅展示了古人的智慧，也因其效率和广泛应用成为现代计算机科学中的基石。通过理解和掌握这一算法，不仅可以增进对数学结构的理解，还能为实际问题的解决提供强大的工具。
12/3 /2018 Euclidean algorith m - Wikipedia
ht t ps://en .wikipedia.org/wiki /Eu cl i dean _algorith m 6/3 0
St ep k Equation Quotient and remainder
0
1071 = q
0
462 + r
0
q
0
= 2 and r
0
= 147
1
462 = q
1
147 + r
1
q
1
= 3 and r
1
= 21
2
147 = q
2
21 + r
2
q
2
= 7 and r
2
= 0; algorithm ends
The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the
greatest common divisor.
[17]
Assume that we wish to cover an a-by-b rectangle with square
tiles exactly, where a is the larger of the two numbers. We first attempt to tile the rectangle
using b-by-b square tiles; however, this leaves an r
0
-by-b residual rectangle untiled, where
r
0
< b. We then attempt to tile the residual rectangle with r
0
-by-r
0
square tiles. This leaves a
second residual rectangle r
1
-by-r
0
, which we attempt to tile using r
1
-by-r
1
square tiles, and so
on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the
previous residual rectangle exactly. The length of the sides of the smallest square tile is the
GCD of the dimensions of the original rectangle. For example, the smallest square tile in the
adjacent figure is 21-by-21 (shown in red), and 21 is the GCD of 1071 and 462, the
dimensions of the original rectangle (shown in green).
At every step k, the Euclidean algorithm computes a quotient q
k
and remainder r
k
from two
numbers r
k−1
and r
k−2
r
k−2
= q
k
r
k−1
+ r
k
where the magnitude of r
k
is strictly less than that of r
k−1
. The theorem which underlies the
definition of the Euclidean division ensures that such a quotient and remainder always exist
and are unique.
[18]
In Euclid's original version of the algorithm, the quotient and remainder are found by repeated
subtraction; that is, r
k−1
is subtracted from r
k−2
repeatedly until the remainder r
k
is smaller
than r
k−1
. After that r
k
and r
k−1
are exchanged and the process is iterated. Euclidean division
reduces all the steps between two exchanges into a single step, which is thus more efficient.
Moreover, the quotients are not needed, thus one may replace Euclidean division by the
modulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply
r
k
= r
k−2
mod r
k−1
.
Implementations of the algorithm may be expressed in pseudocode. For example, the division-based version may be programmed
as
[19]
function gcd(a, b)
while b ≠ 0
t:= b;
Subtraction-based
animation of the Euclidean
algorithm. T he initial
rectangle has dimensions
a = 1071 and b = 4 62.
Squares of size 4 62×4 62
are placed within it leaving
a 4 62×147 rectangle. T his
rectangle is tiled with
14 7×14 7 squares until a
21×14 7 rectangle is left,
which in turn is tiled with
21×21 squares, leaving no
uncovered area. T he
smallest square size, 21,
is the GCD of 1071 and
4 62.
Visualization
Euclidean division
Implementations
剩余29页未读，继续阅读
8495 浏览量
143 浏览量
2009-01-06 上传
263 浏览量
144 浏览量
osakaanarg
- 粉丝: 30
- 资源: 472
我的内容管理
展开
