Data Security-M2-2025-BEC613B/Dr.

Uma S V

MODULE 2

Basic Concepts in Number Theory : Modular Arithemetic and Euclid’s algorithm

Divisibility and the Division Algorithm

Divisibility

A nonzero number b divides a if a = mb for some m, where a , b, and m are integers. That is, b divides a
and there is no remainder on division. The notation b | a is commonly used to mean b divides a and b is a
divisor of a.

Examples: 1. The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24.

2. 13 | 182; -5 | 30; 17 | 289; -3 | 33; 17 | 0;

Properties of Divisibility for Integers:

If a | 1, then a =±1.

If a | b and b | a, then a =±b.

Any b ≠ 0 divides 0.

If a | b and b | c, then a | c:

11 | 66 and 66 | 198 = 11 | 198

If b | g and b | h, then b | (mg + nh) for arbitrary integers m and n. To see this last point, note that

If b | g, then g is of the form g = b * g1 for some integer g1.

If b | h, then h is of the form h = b * h1 for some integer h1.

So, mg + nh = mbg1 + nbh1 = b * (mg1 + nh1) and therefore b divides mg + nh.

Example: b = 7; g = 14; h = 63; m = 3; n = 2

Data Security-M2-2025-BEC613B/Dr. Uma S V

7 | 14 and 7 | 63.

To show 7 | (3 * 14 + 2 * 63),

We have (3 * 14 + 2 * 63) = 7(3 * 2 + 2 * 9),

And it is obvious that 7 | (7(3 * 2 + 2 * 9)).

The Division Algorithm

Given any positive integer and any non negative integer , if we divide a by n, we get an integer quotient q
and an integer remainder r that obey the following relationship:

a = qn + r 0 <= r < n; q = ɭ a/n⌡ (1.1)

Fig.10 The Relationship a=qn+r; 0<=r<n

where ɭ x⌡ is the largest integer less than or equal to x. Equation (1.1) is referred to as the division
algorithm.Fig.10(a) demonstrates that, given a and positive n , it is always possible to find q and r that
satisfy the preceding relationship. Represent the integers on the number line; ‘a’ will fall somewhere on
that line (positive a is shown, a similar demonstration can be made for negative a ). Starting at 0, proceed
to n, 2n , up to qn, such that qn<= a and (q+ 1)n > a. The distance from ‘qn’ to ‘a’ is ‘r’, and we have found
the unique values of q and r. The remainder is often referred to as residue.

Example: a = 11; n = 7;11 = 1 * 7 + 4; r = 4,q = 1

a = -11; n = 7; -11 = (-2) * 7 + 3; r = 3 ,q = -2

Fig.10(b) provides another example.

Data Security-M2-2025-BEC613B/Dr. Uma S V

The Euclidean Algorithm (Is included and important from Exam point of view)
One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for
determining the greatest common divisor of two positive integers. First, we need a simple definition: Two
integers are relatively prime if their only common positive integer factor is 1.

Greatest Common Divisor:

A nonzero b is defined to be a divisor a of if a = mb for some m,where a,b,and m are integers. The notation
gcd(a , b) means the greatest common divisor of a and b. The gcd of a and b is the largest integer that
divides both a and b. We also define gcd(0, 0)=0.

The positive integer c is said to be the greatest common divisor of a and b if,

c is a divisor of a and of b.

Any divisor of a and b is a divisor of c.

An equivalent definition is the following:

gcd(a, b) = max[k, such that k| a and k| b]

Because we require that the greatest common divisor be positive, gcd(a,

b) = gcd(a, -b) = gcd(-a, b) = gcd(-a,-b). In general, gcd(a, b) = gcd(| a | , | b |).

Example: gcd(60, 24) = gcd(60, -24) = 12

Data Security-M2-2025-BEC613B/Dr. Uma S V

Also, because all nonzero integers divide 0, we have gcd(a, 0) = | a | . Two integers a and b are relatively
prime if their only common positive integer factor is 1. This is equivalent to saying that a and b are
relatively prime if gcd(a, b) = 1.

Example: 8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and 8, and the positive
divisors of 15 are 1, 3, 5, and 15.

So 1 is the only integer on both lists.

Finding the Greatest Common Divisor: Euclid’s Algorithm

Suppose we have integers a, b such that d = gcd(a, b). Because gcd(| a |, | b | ) = gcd(a, b), there is no
harm in assuming a >= b > 0. Now dividing a by b and applying the division algorithm, we can state:

a = q1b + r1 0<= r1 < b (1.2)

If r1 = 0, then b | a and d = gcd(a, b) = b. But if r 1 ≠ 0, we can state that d | r1. This is due to the basic
properties of divisibility: the relations d | a and d | b together imply that d | (a - q1b), which is the same
as d | r1.

Note: What is the gcd(b, r1)? We know that d | b and d | r1. Take any arbitrary integer that divides both b
and r1. Therefore, c | (q1b + r1) = a. Because c divides both a and b, we must have c<=d, which is the gcd of
and b. Therefore d = gcd(b, r1).

Now in equation (2), assume that r1 ≠ 0. Because b > r1, we can divide b by r1 and apply the division
algorithm to obtain:

b = q2 r1 + r2 0<= r2 < r1

As before, if r2 = 0, then d = r1 and if r2 ≠0, then d = gcd(r1, r2). The division process continues until some
zero remainder appears, say, at the (n + 1)th stage where rn-1 is divided by rn. The result is the following
system of equations:

a = q1b + r1 0 < r1 < b

Data Security-M2-2025-BEC613B/Dr. Uma S V

b = q2r1 + r2 0 < r 2 < r1

r1 = q3r2 + r3 0 < r 3 < r2

……………………………… (1.3)

rn - 2 = qnrn - 1 + rn 0 < rn <rn - 1

rn - 1 = qn+1rn + 0

d = gcd(a, b) = rn

At each iteration, we have d = gcd(ri, ri + 1) until finally d = gcd(rn, 0) = rn. Thus, we can find the gcd of two
integers by repetitive application of the division algorithm. This scheme is known as the Euclidean
algorithm.

The first step is to show that rn divides a and b. It follows from the last division in Equation (3) that r n
divides rn-1. The next to last division shows that rn divides rn-2 because it divides both terms on the right.

Successively, one sees that rn divides all ri’s and finally a and b. It remains to show that rn is the largest
divisor that divides a and b. If any arbitrary integer is taken that divides and b, it must also divide r 1, as
explained previously. We can follow the sequence of equations in Equation (3) down and show that c must
divide all ri’s. Therefore c must divide rn , so that rn = gcd(a, b).

Euclidean algorithm example:

To find d = gcd (a,b) = gcd (1160718174, 316258250)

a = q1b + r1 1160718174 = 3 *316258250 + 211943424 d = gcd(316258250,

211943424)
Data Security-M2-2025-BEC613B/Dr. Uma S V

b = q2r1 + r2 316258250 = 1 *211943424 + 104314826 d = gcd(211943424,

104314826)

r1 = q3r2 + r3 211943424 = 2 *104314826 +3313772 d = gcd(104314826, 3313772)

r2 = q4r3 + r4 104314826 = 31 *3313772 +1587894 d = gcd(3313772, 1587894)

r3 = q5r4 + r5 3313772 =2 * 1587894+137984 d = gcd(1587894, 137984)

r4 = q6r5 + r6 1587894 =11 * 137984+ 70070 d = gcd(137984, 70070)

r5 = q7r6 + r7 137984 = 1 * 70070 + 67914 d = gcd(70070, 67914)

r6 = q8r7 + r8 70070 = 1 * 67914 + 2156 d = gcd(67914, 2156)

r7 = q9r8 + r9 67914 = 31 * 2516 + 1078 d = gcd(2156, 1078)

r8 = q10r9 2156 = 2 * 1078 + 0 d = gcd(1078, 0) = 1078

+r10

Therefore, d = gcd(1160718174, 316258250) = 1078

In this example, we begin by dividing 1160718174 by 316258250, which gives 3 with a remainder of
211943424. Next we take 316258250 and divide it by 211943424. The process continues until we get a
remainder of 0, yielding a result of 1078.

For every step of the iteration, we have ri-2 = qiri-1+ ri, where ri-2 is the dividend, ri-1 is the divisor, qi is the
quotient, and ri is the remainder.

Above table summarizes the results.

Data Security-M2-2025-BEC613B/Dr. Uma S V

MODULE 2: BASIC CONCEPS OF NUMBER THEORY AND FINITE FIELDS

Modular Arithmetic

The Modulus

If a is an integer and n is a positive integer, we define a mod n to be the remainder when is aisdivided by
n . The integer is called the modulus. Thus, for any integer, we can rewrite Equation (1.1) as follows:

a = qn + r 0<=r < 6 n; q=a/n a =a/n* n + (a mod n)

Ex:11 mod 7 = 4; - 11 mod 7 = 3

Two integers a and b are said to be congruent modulo n, if (a mod n) =(b mod n).

Properties of Congruences

Congruences have the following properties:

a ≡ b (mod n) if n | (a - b).

a ≡ b (mod n) implies b ≡ a (mod n).

a ≡ b (mod n) and b ≡ c (mod n) imply a ≡ c (mod n).

To demonstrate the first point, if n | (a - b), then (a - b) = kn for some k. So we can write a = b + kn.
Therefore, (a mod n) = (remainder when b + kn is divided by n) = (remainder when b is divided by n) = (b
mod n).

23 ≡ 8 (mod 5) because 23 - 8 = 15 = 5 * 3

-11 ≡ 5 (mod 8) because -11 - 5 = -16 = 8 * (-2)

81 K 0 (mod 27) because 81 - 0 = 81 = 27 * 3

The remaining points are as easily proved.

Modular Arithmetic Operations

By definition, the(mod n) operator maps all integers into the set of integers {0, 1,…., (n - 1)}. We can
perform arithmetic operations within the confines of this set. This technique is known as modular
arithmetic.
Data Security-M2-2025-BEC613B/Dr. Uma S V

Modular arithmetic exhibits the following properties:

Data Security-M2-2025-BEC613B/Dr. Uma S V

[(a mod n) + (b mod n)] mod n = (a + b) mod n

[(a mod n) - (b mod n)] mod n = (a - b) mod n

[(a mod n) * (b mod n)] mod n = (a * b) mod n

We demonstrate the first property. Define (a mod n) = ra and (b mod n) = rb. Then we can write a = ra + jn
for some integer j and b = rb + kn for some integer k. Then, (a + b) mod n = (ra + jn + rb + kn) mod n

= (ra + rb + (k + j)n) mod n

= (ra + rb) mod n

= [(a mod n) + (b mod n)] mod n

The remaining properties are proven as easily. Here are examples of the three properties

11 mod 8 = 3; 15 mod 8 = 7

[(11mod 8) + (15mod 8)] mod 8 = 10mod 8 = 2

(11 + 15) mod 8 = 26 mod 8 = 2

[(11 mod 8) - (15 mod 8)] mod 8 = - 4 mod 8 = 4

(11 - 15) mod 8 = - 4 mod 8 = 4

[(11 mod 8) * (15 mod 8)] mod 8 = 21mod 8 = 5

(11 * 15) mod 8 = 165 mod 8 = 5

Data Security-M2-2025-BEC613B/Dr. Uma S V

Exponentiation is performed by repeated multiplication, as in ordinary arithmetic.

To find117mod13, we can proceed as follows: 112= 121 ≡ 4 (mod 13)

114 = (112)2 ≡ 42 ≡ 3 (mod 13)

117 ≡ 11 * 4 * 3 ≡ 132 ≡ 2 (mod 13)

Thus, the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into
modular arithmetic.

Table 2 provides an illustration of modular addition and multiplication modulo

Looking at addition, the results are straightforward, and there is a regular pattern to the matrix. Both
matrices are symmetric about the main diagonal in conformance to the commutative property of addition
and multiplication. As in ordinary addition, there is an additive inverse, or negative, to each integer in
modular arithmetic. In this case, the negative of an integer x is the integer y such that (x + y) mod 8=0.

To find the additive inverse of an integer in the left-hand column, scan across the corresponding row of
the matrix to find the value 0; the integer at the top of that column is the additive inverse; thus, (2 + 6)
mod 8 = 0.

Similarly, the entries in the multiplication table are straightforward. In ordinary arithmetic, there is a
multiplicative inverse, or reciprocal, to each integer. In modular arithmetic mod 8, the multiplicative
inverse of x is the integer y such that (x * y) mod 8 = 1 mod 8. Now, to find the multiplicative inverse of an
integer from the multiplication table, scan across the matrix in the row for that integer to find the value 1;
the integer at the top of that column is the multiplicative inverse; thus, (3 * 3) mod 8 = 1. Note that not all
integers mod 8 have a multiplicative inverse;
Data Security-M2-2025-BEC613B/Dr. Uma S V

Table 2 Arithmetic Modulo 8

Properties of Modular Arithmetic

Define the set Zn as the set of nonnegative integers less than n: Zn = {0, 1,….., (n - 1)}

This is referred to as the set of residues, or residue classes (mod n). To be more precise, each integer in Zn
represents a residue class. We can label the residue classes (mod n) as [0], [1], [2],….., [n - 1], where

[r] = {a : a is an integer, a ≡ r (mod n)}

Data Security-M2-2025-BEC613B/Dr. Uma S V

The residue classes (mod 4) are

[0] = {…., - 16, - 12, - 8, - 4, 0, 4, 8, 12, 16,…}

[1] = {…, - 15, - 11, - 7, - 3, 1, 5, 9, 13, 17, …}

[2] = {…, - 14, - 10, - 6, - 2, 2, 6, 10, 14, 18,…}

[3] = {…, - 13, - 9, - 5, - 1, 3, 7, 11, 15, 19,…}

Of all the integers in a residue class, the smallest nonnegative integer is the one used to represent the
residue class. Finding the smallest nonnegative integer to which k is congruent modulo n is called reducing
k modulo n.

If we perform modular arithmetic within Zn, the properties shown in Table 3 hold for integers in Zn. We
show in the next section that this implies that Zn is a com- mutative ring with a multiplicative identity
element.

Table 3 Properties of Modular Arithmetic for Integers in Zn

Property Expression

(w + x) mod n = (x + w) mod n

Commutative Laws (w * x) mod n = (x * w) mod n

[(w + x) + y] mod n = [w + (x +

Associative Laws y)] mod n

[(w * x) * y] mod n = [w * (x *

y)] mod n

Distributive Law [w * (x + y)] mod n = [(w * x) + (w

* y)] mod n

(0 + w) mod n = w mod n

Identities (1 * w) mod n = w mod n

Additive Inverse (- w) For each w ∈ Zn, there exists a z such that w + z ≡ 0

mod n
Data Security-M2-2025-BEC613B/Dr. Uma S V

There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic. First, observe
that (as in ordinary arithmetic) we can write the following:

if (a + b) ≡ (a + c) (mod n) then, b ≡ c (mod n) (1.4)

(5 + 23) K (5 + 7) (mod 8); 23 ≡ 7(mod 8)

Equation (1.4) is consistent with the existence of an additive inverse. Adding the additive inverse of to
both sides of Equation (1.4), we have

(( -a) + a + b) ≡ ((-a) + a + c) (mod n) b ≡ c (mod n)

However, the following statement is true only with the attached condition:

if (a * b) ≡ (a * c)(mod n) then b ≡ c (mod n) if a is relatively prime to n (1.5)

Recall that two integers are relatively prime if their only common positive integer factor is 1. Similar to the
case of Equation (1.4), Equation (1.5) is consistent with the existence of a multiplicative inverse. Applying
the multiplicative inverse of to both sides of Equation (1.5), we have

((a - 1)ab) ≡ ((a - 1)ac)(mod n) b ≡ c (mod n)

To see this, consider an example in which the condition of Equation (1.5) does not hold. The
integers 6 and 8 are not relatively prime, since they have the common factor 2. We have
the following:
6 * 3 = 18 ≡ 2(mod8)

6 * 7 = 42 ≡ 2(mod8)

Yet 3 is not congruent to 7 (mod 8).

Data Security-M2-2025-BEC613B/Dr. Uma S V

The reason for this strange result is that for any general modulus, a multiplier that is applied in turn to the
integers 0 through (n - 1) will fail to produce a complete set of residues if a and n have any factors in
common.

In general, an integer has a multiplicative inverse in Zn if that integer is relatively prime to n. Table 2c
shows that the integers 1,3,5 and 7 have a multiplicative inverse in Z8; but 2, 4, and 6 do not.

Euclidean Algorithm Revisited

The Euclidean algorithm can be based on the following theorem: For any integers

a, b, with a>=b>=0,

gcd(a, b) = gcd(b, a mod b) (1.6)

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

To see that Equation(1.6) works, let d = gcd(a, b). Then, by the definition of gcd, d | a and d | b. For any
positive integer b, we can express as
Data Security-M2-2025-BEC613B/Dr. Uma S V

a = kb + r ≡ r (mod b)

a mod b = r

with k, integers. Therefore,(a mod b) = a - kb for some integer k. But because d | b, it also divides
kb. We also have d | a. Therefore, d | (a mod b). This shows that d is a common divisor of b and
(a mod b). Conversely, if d is a common divisor of b and (a mod b), then d | kb and thus d | [kb +
(a mod b)], which is equivalentto d |a. Thus, the set of common divisors of and b is equal to the
set of common divisors of b and ( mod b). Therefore, the gcd of one pair is the same as the gcd
of the other pair, proving the theorem.

Equation (1.6) can be used repetitively to determine the greatest common divisor.

gcd(18,12) = gcd(12,6) = gcd(6,0) = 6

gcd(11,10) = gcd(10,1) = gcd(1,0) = 1

This is the same scheme shown in Equation(1.3), which can be rewritten in the following way. We
can define the Euclidean algorithm concisely as the following recursive function.

Euclid(a,b)

if (b=0) then return a;

else return Euclid(b, a mod b);