请输入您要查询的字词:

 

单词 GreatestCommonDivisor
释义

greatest common divisor


Let a and b be given integers, with at least one of them different from zero. The greatest common divisorMathworldPlanetmathPlanetmath of a and b, denoted by gcd(a,b), is the positive integer d satisfying

  1. 1.

    da and db,

  2. 2.

    if ca and cb, then cd.

More intuitively, the greatest common divisor is the largest integer dividing both a and b.

For example, gcd(345,135)=15, gcd(-7,-21)=7, gcd(18,0)=18, and gcd(44,97)=1

Given two (rational) integers, one can construct their gcd via Euclidean algorithmMathworldPlanetmath. Once the gcd is found, it can be written as a linear combinationMathworldPlanetmath of the two integers. That is, for any two integers a and b, we have gcd(a,b)=ra+sb for some integers r and s. This expression is known as the Bezout identityMathworldPlanetmath.

One can generalize the notion of a gcd of two integers into a gcd of two elements in a commutative ring. However, given two elements in a general commutative ring, even an integral domain, a gcd may not exist. For example, in [x2,x3], a gcd for the elements x5 and x6 does not exist, for x2 and x3 are both common divisorsMathworldPlanetmathPlanetmath of x5 and x6, but neither one divides another.

The idea of the gcd of two integers can be generalized in another direction: to the gcd of a non-empty set of integers. If S is a non-empty set of integers, then the gcd of S, is a positive integer d such that

  1. 1.

    da for all aS,

  2. 2.

    if ca,aS, then cd.

We denote d=gcd(S).

Remarks.

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

  • If TS, then gcd(S)gcd(T).

  • For any S, there is a finite subset TS such that gcd(T)=gcd(S).

Titlegreatest common divisor
Canonical nameGreatestCommonDivisor
Date of creation2013-03-22 11:46:50
Last modified on2013-03-22 11:46:50
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id22
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 11-00
Classificationmsc 03E20
Classificationmsc 06F25
Synonymgcd
Synonymgreatest common factor
Synonymhighest common factor
Synonymhcf
Related topicGcdDomain
Related topicCorollaryOfBezoutsLemma
Related topicExampleOfGcd
Related topicExistenceAndUniquenessOfTheGcdOfTwoIntegers
Related topicDivisionOfCongruence
Related topicCongruencesMathworldPlanetmathPlanetmathPlanetmath
Related topicRationalSineAndCosine
Related topicIntegralBasisOfQuadraticField
Related topicSquareRootsOfRationals
Related topicIntegerContraharmonicMeans
Related topicSubgroupsWithCoprim
随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 15:43:53