Overview

greatest common factor

More Like This

Show all results sharing this subject:

• Mathematics

GO

Show Summary Details

Quick Reference

For two non-zero integers a and b, any integer that is a divisor of both is a common divisor. Of all the common divisors, the greatest is the greatest common divisor (or g.c.d.), denoted by (a, b). The g.c.d. of a and b has the property of being divisible by every other common divisor of a and b. It is an important theorem that there are integers s and t such that the g.c.d. can be expressed as sa+tb. If the prime decompositions of a and b are known, the g.c.d. is easily found: for example, if a=168=23×3×7 and b=180=22×32×5, then the g.c.d. is 22×3=12. Otherwise, the g.c.d. can be found by the Euclidean Algorithm, which can be used also to find s and t to express the g.c.d. as sa+tb. Similarly, any finite set of non-zero integers a1, a2,…, an has a g.c.d., denoted by (a1, a2,…, an), and there are integers s1, s2,…, sn such that this can be expressed as s1a1+s2a2+…+snan.

Subjects: Mathematics.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.