 # Greatest Common Divisor (gcd)

The greatest common divisor of two numbers a and b, gcd(a, b), is the largest integer d that divides both a and b. If we have prime factorization of a and b then gcd(a, b) can be easily written as follows:

• • Given a = pf' ■ pf1 ■...pfk and b = pf1 pf- •... • pf*.
• • Take all the primes which occur in both factorizations raised to the minimum of two exponents.
• gcd(a,b) = prM)......р'»'"<“ь0о

Relatively prime numbers: The integers aua2,......, ak are pairwise relatively

prime if gcd(a,, a,) = 1, V 1 < i, j < k.

## Euclid’s theorem

Let b, c > 0 and c f b; using the division theorem we can obtain the following equations: Then, gcd[b, c) = r„ which represents the last non-zero remainder in the above set of equations.

In the above algorithm, we see that the remainder decreases until it becomes 0. Further, the remainders do not only decrease but they decrease rather rapidly. In every two steps the size of the remainder becomes at least

half, i.e. ri+2 <^rr

1 11

Proof • If r,-+i < — r; then rj+2 < r(+1 < — r(. Suppose r/+] > — r, then r, = 1 • r/+[ + rj+1.

1 1

Alternatively, we can write, rj+1 = r( - r;+1. If rl+l > —r„ then r!+2 < —rr

## Extended Euclidean algorithm

Let d = gcd(u, b). Then there exists integers и and v such that d = ua + vb, i.e. GCD of two numbers can be expressed as a linear combination of the numbers with integer coefficient.

For example: gcd(560,1547)

First, apply Euclid’s theorem to find the gcd as follows:

• 1. 1547 = 2-560 + 427
• 2. 560 = 1-427 + 133
• 3. 427 = 3-133 + 28
• 4. 133 = 4-28 + 21
• 5. 28 = 1-21 + 7

Now, backtrack from the last equations and recursively put values until we get the original numbers:

7 = 28-1-(21)

= 28-1 (133-4 28)

= 28 —133 + 4(28)

= 5-(28)-133 = 5 (427-3 (133))-133 = 5-427-16-133 = 5-427-16(560-427)

= 21-427-16-560 = 21(1547 - 2 • 560)-16 • 560 = 21-1547+ (-58)-560

The extended Euclid algorithm has application in finding the multiplicative inverse.

# Congruence

If an integer m divides the difference a-b, then we say a is congruent to bmodm, i.e. a = b modm iff ma-b , .

## Congruence relation properties

The following are the key properties of congruence:

• • If a=b(modm) and c=d(modm), then a±c=(b±d)modm and ac=bdmodm.
• • If a = b(modm) and b = c(modm), then a = c(modm).
• • If a = b(modm), b - a(modm) and a-b = 0(modm) are equivalent.
• • If a = b{modm) and dm, d > 0 then a = b(modd).
• • If a = b(modm) then ac - bc(modmc) for c > 0.
• • If a = bmodm, a = bmodn and m, n are relatively prime then a = bmodmn-
• • Congruence modulo n is an equivalence relation on Z.
• • Reflexive: a = amodn /a e Z
• • Symmetry: If a = bmodn then b = amodn
• • Transitive: If a = bmodn and b - cmodn then a - cmodn

The proof of these properties can be done with the help of the definition of congruence and basic integer algebra. We will provide the proof of the first property and others can also be proven in the same manner as follows: If a = b(modm) then by the congruence definition and divisibility theorem, we can write: a-b = s m and c-d = t ■ m, where s, t e Z; a + c = (s + t)m + (b + d), s + fe. Hence, a + c = (b±d)modm. Similarly, ac = (st)m + (bd), steZ. Hence, ac = bdmodm.

1.1.4.1.1 Congruence (residue) classes modulo m

If x = y(modm), then у is called a residue when we divide x by m. A set xi,x2, -,x,„ is called a complete residue system modulo m, if VyeZ, 3 a unique xу = Xj(modm).

For fixed integer a and m > 0, the set of all integers, x, satisfying x = a(modm)

forms an arithmetic progression (AP), {......a-2m, a-m, a + m, a + 2m......}

and this set is called a residue class or congruence class modulo m. For example: equivalence classes of 0 and 1 for congruence modulo 4 are: 4 = {......-8,-4, 0, 4, 8......) and 4 = {......-9,-5, 1, 5, 9......}.

## Reduced residue system modulo m

A reduced residue system modulo m is a set of integers, r,: (rn m) = 1, г, ф r,{modm) if i * j and such that every integer relatively prime to m is congruent modulo m to some member r, of the set. To get the reduced residue from the complete residue system, delete all members у for which (y, m) * 1.

## Inverse modulo m

If gcd(a,m) = 1 or (a,m) = 1 then there is an x: ax = lmodm and x is called the multiplicative inverse of amodm.

Proof: By the extended Euclidean algorithm: gcdfa, m) = ax + my = 1 => max-=>ax = mod. Conversely, if ax = lmodm =>т|лх-1, then 3y: ax + my = 1.

Therefore, if m > 1 and gcd [a, m) = 1, then inverse of amodm exists and is equal to x in the following representation of gcd(a, m): ax л-my = 1.

## Euler’s phi function (totient function)

The number of elements in a reduced residue system modulo m is denoted by ф(m) called Euler’s phi function or the totient function or indicator function. It is used for counting relatively prime numbers. For example: how many positive numbers less than 20 are relatively prime to 20? The answer is: 1,3,7,9,11,13,17,19.

To find a formula for ф(я):

• Make a table for ф(n) for n = 1,2,......, 15 • • If p is prime check in the table what is ф(р)?
• • ф(р) = р-1
• • If p is a prime number and k is a whole number
• • The numbers less than (or equal to) pk that are not relatively prime to

pk would surely be multiples of p, i.e. p, 2p,......, pk~'p

• • So there are pk~' out of pk which are not relatively prime
• ц>(рк) = ркк-г

## Fermat’s theorem

Let p denotes a prime. If pa then ap~' = modp

Proof: If pa => (a, p) = 1 => лф|р| = 1 modp by the Euler’s generalization of Fermat’s theorem. ф(р) denotes the number of integers relatively prime to p, which are p — 1. Hence, ap~' = lmodp.

## Euler’s generalization of Fermat’s theorem

If (a, m) = 1, then дф|"'1 = 1 modm.

Proof: Let fi, r2, -, гф(от) be a reduced residue system modulo m. Then ar, лгт,- arv(m) is also a reduced residue system modulo m, since (a, m) = 1 and (r,,m) = 1, which implies {arhm) = . Therefore, corresponding to each rn there is one and only one art such that ar, = rmodm). Multiply all such ф(m) relations: ar, = ГТ,='Г' ri(modm) = ащ'п) = modm.