请输入您要查询的字词:

 

单词 Greatest Common Divisor
释义

Greatest Common Divisor

The greatest common divisor of and GCD(), sometimes written , is the largest Divisor common to and . Symbolically, let

(1)
(2)

Then the greatest common divisor is given by
(3)

where min denotes the Minimum. The GCD is Distributive
(4)


(5)

and Associative
(6)


(7)


If and , then

(8)

so and and are said to be Relatively Prime. The GCD is also Idempotent
(9)

Commutative
(10)

and satisfies the Absorption Law
(11)


The probability that two Integers picked at random are Relatively Prime is ,where is the Riemann Zeta Function. Polezzi (1997) observed that , where is the number ofLattice Points in the Plane on the straight Line connecting theVectors (0, 0) and (excluding itself). This observation is intimately connected with theprobability of obtaining Relatively Prime integers, and also with the geometric interpretation of a ReducedFraction as a string through a Lattice of points with ends at (1,0) and . The pegs it presses against give alternate Convergents of the Continued Fraction for , while theother Convergents are obtained from the pegs it presses against with the initial end at (0, 1).


Knuth showed that

(12)


The extended greatest common divisor of two Integers and can be defined as the greatest commondivisor of and which also satisfies the constraint for and given Integers. It isused in solving Linear Diophantine Equations.

See also Bezout Numbers, Euclidean Algorithm, Least Prime Factor


References

Polezzi, M. ``A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor.'' Amer. Math. Monthly 104, 445-446, 1997.

随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2024/11/15 2:20:40