“Euclidean Algorithm”的概念、定义、习题解题方法及翻译-数学辞典

单词

Euclidean Algorithm

释义

Euclidean Algorithm

A process, based on the Division Algorithm, for finding the greatest common divisor (a, b) of two positive integers a and b. Assuming that a > b, write a = bq1 + r1, where 0 ≤ r1 < b. If r1 = 0, the gcd (a,b) is equal to b; if r1 ≠ 0, then (a,b) = (b,r1), so the step is repeated with b and r1 in place of a and b. After further repetitions, the last non‐zero remainder obtained is the required gcd. For example, for a = 1274 and b = 871, write

and then (1274,871) = (871,403) = (403, 65) = (65,13) = 13.

The algorithm also enables s and t to be found such that the gcd can be expressed as sa + tb (see Bézout's lemma). We use the previous equations in turn to express each remainder in this form. Thus,

随便看

数学辞典收录了4151条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。