Greatest Common Divisor

Greatest Common Divisor (GCD) •

a common problem in number theory

•

GCD (a,b) of a and b is the largest number that divides evenly into both a and b –

•

eg GCD(60,24) = 12

often want no common factors (except 1) and hence numbers are relatively prime –

eg GCD(8,15) = 1

–

hence 8 & 15 are relatively prime

Euclid's GCD Algorithm •

an efficient way to find the GCD(a,b)

•

uses theorem that: –

•

GCD(a,b) = GCD(b, a mod b)

Euclid's Algorithm to compute GCD(a,b): –

A=a, B=b

–

while B>0

–

•

R = A mod B

•

A = B, B = R

return A

Euler's Theorem •

a generalisation of Fermat's Theorem

•

aø(n)mod n = 1

•

–

where gcd(a,n)=1

–

a=3;n=10; ø(10)=4;

–

hence 34 = 81 = 1 mod 10

–

a=2;n=11; ø(11)=10;

–

hence 210 = 1024 = 1 mod 11

eg.

Galois Fields

GF

Relatively Prime Numbers & GCD •

two numbers a, b are relatively prime if have no common divisors apart from 1 –

•

eg. 8 & 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only common factor

conversely can determine the greatest common divisor by comparing their prime factorizations and using least powers –

eg. 300=21×31×52 18=21×32 hence GCD(18,300)=21×31×50=6

Euclid's GCD Algorithm •

An efficient way to find the GCD(a,b)

•

uses theorem that:

•

–

GCD(a,b) = GCD(b, a mod b)

–

gcd(55,22)=gcd(22,55 mod 22)=gcd(22,11)=11

Euclid's Algorithm to compute GCD(a,b):

EUCLID(a,b) 1. A ←a; B ←b 2. If B=0 return A=gcd(a,b) 3. R = A mod B 4. A ← B 5. B ← R 6. goto 2

Example GCD(1970,1066) 1970 = 1 x 1066 + 904

gcd(1066, 904)

1066 = 1 x 904 + 162

gcd(904, 162)

904 = 5 x 162 + 94

gcd(162, 94)

162 = 1 x 94 + 68

gcd(94, 68)

94 = 1 x 68 + 26

gcd(68, 26)

68 = 2 x 26 + 16

gcd(26, 16)

26 = 1 x 16 + 10

gcd(16, 10)

16 = 1 x 10 + 6

gcd(10, 6)

10 = 1 x 6 + 4

gcd(6, 4)

6=1x4+2

gcd(4, 2)

4=2x2+0

gcd(2, 0)

Greatest common divisor The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for the GCD include the greatest common factor (GCF), the highest common factor (HCF), and the greatest common measure (GCM). The greatest common divisor is often written as GCD(a, b) or, more simply, as (a, b),[2] although the latter notation is also used for other mathematical concepts, such as two-dimensional vectors. If GCD(a, b) = 1, then a and b are said to be coprime.[3] This property is independent of whether a and b are themselves prime numbers.[4] For example, neither 6 nor 35 is a prime number, since they both have two prime factors: 6 = 2 × 3 and 35 = 5 × 7. Nevertheless, 6 and 35 are coprime. No natural number other than 1 divides both 6 and 35, since they have no prime factors in common.

A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-b rectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b. Let g = GCD(a, b). Since a and b are both multiples of g, they can be written a = mg and b = ng, and there is no larger number G > g for which this is true. The natural numbers m and n must be coprime, since any common factor can be factored out of m and n to make g greater. Thus, any other number c that divides both a and b must also divide g. The greatest common divisor g of a and b can be defined as the common divisor that is divisible by any other common divisor c.[5] The GCD can be visualized as follows.[6] Consider a rectangular area a by b, and any common divisor c that divides both a and b exactly. The sides of the rectangle can be divided into segments of length c, which divides the rectangle into a grid of squares of side length c. The greatest common divisor g is the largest value of c for which this is possible. For illustration, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24

and 60. A 24-by-60 rectangular area can be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5). The GCD of two numbers a and b can be defined as the product of the prime factors shared by the two numbers.[7] For example, since 462 can be factored into 2 × 3 × 7 × 11 and 1071 can be factored into 3 × 3 × 7 × 17, the greatest common divisor of 462 and 1071 equals 21 = 3 × 7, the product of their shared prime factors. If two numbers have no prime factors in common, their greatest common divisor is 1—they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors. Factorization of large integers is believed to be such a difficult problem that many modern cryptography systems are based upon it.[10] A more subtle definition of the GCD is helpful in advanced mathematics, particularly ring theory.[11] The greatest common divisor g of two numbers a and b is also their smallest integer multiple, that is, the smallest number of the form ua + vb where u and v are integers. It follows that the set of all integer multiples of a and b (all numbers ua + vb) is the same as the set of all integer multiples of g (mg, where m is an integer). In modern mathematical language, the ideal formed by a and b is a principal ideal generated by g. The equivalence of this GCD definition with the other definitions is described below. The GCD of three or more numbers equals the product of the prime factors common to all the numbers,[12] which can be calculated by taking the GCDs of pairs of numbers.[13] For example, GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b). Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers. Euclid’s GCD Algorithm Euclid’s algorithm for computing the GCD repeatedly applies the formula gcd(a, b) = gcd(b, a mod b) Example gcd(412, 260) = 4 a 412 260 152 108 44 20 4 b 260 152 108 44 20 4 0