# 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' ■ pf*•^{1}■...*pf*and^{k}*b =*pf^{1}*■*pf- •... • pf*. - • Take all the primes which occur in both factorizations raised to the minimum of two exponents.
- •
*gcd(a,b) = pr*......р'»'"<“ь0о^{M)}

*Relatively prime numbers*: The integers *a _{u}a_{2},*......

*, a*are pairwise relatively

_{k}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. *r _{i+2} <^r_{r}*

1 11

*Proof* • If r,-+i < — r_{;} *then r _{j+2} <* r

_{(+1}< — r

_{(}. Suppose r

_{/+]}> —

*r,*then r, = 1 •

*r*+

_{/+[}*r*

_{j+1}.1 1

Alternatively, we can write, *r _{j+1} =* r

_{(}- r

_{;+1}. If

*r*—r„ then

_{l+l}>*r*

_{!+2}< —r_{r}## 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* [2], [3].

## 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,x _{2}, -,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: [0]_{4} = {......-8,-4, 0, 4, 8......) and [1]_{4} = {......-9,-5, 1, 5, 9......}.

## Reduced residue system modulo m

*A* reduced residue system modulo m is a set of integers, *r,: (r _{n} 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
is prime check in the table what is ф(р)?**p** - • ф(р) = р-1
- • If
is a prime number and**p**is a whole number**k** - • The numbers less than (or equal to)
that are not relatively prime to**p**^{k}

* p^{k}* would surely be multiples of

*i.e.*

**p,***......,*

**p, 2p,**

**p**^{k}~'p- • So there are
out of**p**^{k}~'which are not relatively prime**p**^{k} - •
*ц>(р*^{к}) = р^{к}-р^{к}-^{г}

## Fermat’s theorem

Let *p* denotes a prime. If *pa* then *a ^{p}~' = 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, *a ^{p}~' = lmodp.*

## Euler’s generalization of Fermat’s theorem

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

*Proof:* Let fi, *r _{2}, -,* г

_{ф(от)}be a reduced residue system modulo

*m.*Then

*ar*,

*лгт,- ar*is also a reduced residue system modulo

_{v(m)}*m,*since

*(a, m) =*1 and

*(r,,m) =*1, which implies

*{ar*Therefore, corresponding to each

_{h}m) = .*r*there is one and only one

_{n}*ar*such that

_{t}*ar, = rmodm).*Multiply all such ф(m) relations:

*ar,*= ГТ,='Г'

*ri(modm) = а*

^{щ}'^{п)}= modm.