Ecient Computing Techniques

This lecture notes deals with the modular exponentiation, modular multiplicative inverse,

Lucas' theorem for binomial coecients and primality tests.

1 Congruences
Divisibility: Let a and b be two integers. We say that a divides b (a|b) if there exists

an integer c such that b = ac. If a does not divides b, i.e., b ̸= ac for any integer c, then

we write a ∤ b. For example: 2|4, 3|6, 5|1000, 2 ∤ 3, 3 ∤ 10.

Proposition 1.1. For integers a, b and c, we have

(i) a|a.

(ii) If a|b and b|a, then a = ±b.

(iii) If a|b, b|c, then a|c.

Theorem 1.2 (Division Algorithm). Let a and b (=

̸ 0) be integers. Then there exists

unique integers q and r such that a = bq + r, where 0 ≤ r ≤ |b|.

Greatest common divisor: Let a and b be integers not both zero. The greatest common

divisor of a and b, denoted by gcd(a, b) is dened as the largest positive integer that divides
both a and b. Example: gcd(2, 4) = 2, gcd(13, 15) = 1 and gcd(12, 30) = 6.

Theorem 1.3 (Euclidean algorithm). Let a and b(̸= 0) be non-negative integers such that

a = bq1 + r1 , 0 ≤ r1 ≤ b.

b = r1 q2 + r2 , 0 ≤ r2 ≤ r1 .

r1 = r2 q3 + r3 , 0 ≤ r3 ≤ r2 .

1
 ..
.

rn−2 = rn−1 qn + rn , 0 ≤ rn ≤ rn−1 .

rn−1 = rn qn+1 .

Then gcd(a, b) = rn .

Remark 1.4. The Euclidean algorithm follows from the fact that if a = bq + r, then

gcd(a, b) = gcd(b, r).

Note that if gcd(a, b) = d, then there exists integers x and y such that ax + by = d.

Example 1.5. Find the gcd(48,18).

Solution:

48 = 18 × 2 + 12

18 = 12 × 1 + 6

12 = 6 × 2 + 0.

Therefore, gcd(48, 18) = 6.

Congruences: Let a and b be integers. Let n be a positive integer. Then a is congruent

to b modulo n, written a ≡ b(mod n) if n|a − b, otherwise a ̸≡ b(mod n), i.e., a is not

congruent to b modulo n. For example: 2 ≡ 4(mod 2), 3 ≡ 17(mod 7), 10 ̸≡ 1(mod 2).

Proposition 1.6. For integers a, b, c, d and n > 0, we have

(i) a ≡ a(mod n).

(ii) a ≡ b(mod n) ⇐⇒ b ≡ a(mod n).

(iii) If a ≡ b(mod n) and b ≡ c(mod n), then a ≡ c(mod n).

(iv) If a ≡ b(mod n) and c ≡ d(mod n), then a + c ≡ b + d(mod n) and ac ≡ bd(mod n).

2
2 Modular Exponentiation by Repeated Squaring
Modular exponentiation refers to nding ab (mod m), which is a common operation in

elds such as cryptography (e.g., RSA algorithm). Direct computation of ab for large

b can be computationally expensive. The method of Repeated Squaring is an ecient

technique to compute this.

Method of successive squaring

ˆ For any ab , if b is a power of 2, we can quickly compute ab (mod m) by repeatedly

squaring the congruence a(mod m).

ˆ If b is not a power of 2, we can rewrite it as a sum of powers of 2, and then multiply

them together.

Examples
(1) Determine the value of 742 (mod 11).

Solution: Note that 42 is not a power of 2, hence we write 42 as a sum of powers

of 2 as follows

42 = 32 + 8 + 2

Now,

7 ≡ 7(mod 11)

72 ≡ 49 ≡ 5(mod 11)

74 ≡ 25 ≡ 3(mod 11)

78 ≡ 9(mod 11)

716 ≡ 81 ≡ 4(mod 11)

732 ≡ 16 ≡ 5(mod 11)

Hence,

742 = 72 .78 .732 ≡ 5.9.5 ≡ 45.5 ≡ 1.5 ≡ 5(mod 11)

3
 (2) Determine the value of 999179 (mod 1763).

Solution We nd that 179 = 1 + 2 + 24 + 25 + 27 . Using repeated squaring, we

compute:

9992 ≡ 143(mod 1763),

9994 = 1432 ≡ 1056(mod 1763),

9998 = 10562 ≡ 920(mod 1763),

99916 = 9202 ≡ 160(mod 1763),

99932 = 1602 ≡ 918(mod 1763),

99964 = 9182 ≡ 10(mod 1763),

999128 = 102 ≡ 100(mod 1763).

Hence,

999179 ≡ 999 · 143 · 160 · 918 · 100(mod 1763). ≡ 54 · 160 · 918 · 100 ≡ 1219(mod 1763).

Exercises
(a) Compute 1155 (mod 19).

(b) Compute 31300 (mod 100).

3 Modular Multiplicative Inverse

The modular multiplicative inverse of an integer a with respect to a modulus m is

an integer x such that:

a·x≡1 (mod m).

In other words, when a is multiplied by x, the result is congruent to 1 modulo m.

4
Existence
A modular multiplicative inverse of a modulo m exists if and only if a and m are coprime,
i.e., gcd(a, m) = 1.

Finding the Inverse

There are several methods to nd the modular multiplicative inverse:

1. Extended Euclidean Algorithm

The Extended Euclidean Algorithm is an ecient method to nd the inverse. It works as

follows:

ˆ Use the Euclidean algorithm to express gcd(a, m) as a linear combination of a and

m, i.e., gcd(a, m) = ax + my for some integers x and y.

ˆ Since gcd(a, m) = 1, we have ax + my = 1.

ˆ Taking modulo m on both sides gives ax ≡ 1 (mod m).

ˆ Thus, x is the modular multiplicative inverse of a modulo m.

2. Fermat's Little Theorem (For Prime Modulus)

If m is a prime number, Fermat's Little Theorem provides a straightforward way to nd

the inverse:

am−1 ≡ 1 (mod m).

Multiplying both sides by a−1 , we get:

am−2 ≡ a−1 (mod m).

Thus, am−2 is the inverse of a modulo m.

5
3. Using Modular Exponentiation

In general, when m is not prime, we can use the method of modular exponentiation to

compute the inverse by:

aϕ(m)−1 (mod m),

where ϕ(m) is the Euler's totient function, which counts the number of integers up to m
that are coprime to m.

Example
(1) Find the modular multiplicative inverse of 3 modulo 7.

Solution: Using the Extended Euclidean Algorithm:

7 = 3 × 2 + 1,

3 = 1 × 3 + 0.

Thus, gcd(3, 7) = 1. We back-substitute to nd the inverse:

1 = 7 − 3 × 2.

Taking modulo 7 gives:

−3 × 2 ≡ 1 (mod 7).

Multiplying both sides by −1, we get:

3 × (−2) ≡ 1 (mod 7).

Thus, x = 5 (since −2 ≡ 5 (mod 7)) is the modular multiplicative inverse of 3

modulo 7.

(2) Find the modular multiplicative inverse of 4 modulo 9.

Solution: We need to nd x such that:

4·x≡1 (mod 9).

6
 Using the Extended Euclidean Algorithm:

9 = 4 × 2 + 1,

4 = 1 × 4 + 0.

Thus, gcd(4, 9) = 1, and we back-substitute:

1 = 9 − 4 × 2.

Taking modulo 9, we get:

4 × (−2) ≡ 1 (mod 9).

Therefore, x=7 (since −2 ≡ 7 (mod 9)) is the inverse.

(3) Find the modular multiplicative inverse of 17 modulo 43.

Solution: We need to nd x such that:

17 · x ≡ 1 (mod 43).

Using the Extended Euclidean Algorithm:

43 = 17 × 2 + 9,

17 = 9 × 1 + 8,

9 = 8 × 1 + 1,

8 = 1 × 8 + 0.

Thus, gcd(17, 43) = 1, and we back-substitute:

1 = 9 − 8 × 1,

8 = 17 − 9 × 1,

9 = 43 − 17 × 2.

Substituting back, we get:

1 = 9 − (17 − 9) = 2 × 9 − 17 = 2 × (43 − 2 × 17) − 17 = 2 × 43 − 5 × 17.

7
 Taking modulo 43, we get:

−5 × 17 ≡ 1 (mod 43).

Thus, x = 38 (since −5 ≡ 38 (mod 43)) is the inverse.

(4) Find the modular multiplicative inverse of 12 modulo 17.

Solution: We need to nd x such that:

12 · x ≡ 1 (mod 17).

Using the Extended Euclidean Algorithm:

17 = 12 × 1 + 5,

12 = 5 × 2 + 2,

5 = 2 × 2 + 1,

2 = 1 × 2 + 0.

Thus, gcd(12, 17) = 1, and we back-substitute:

1 = 5 − 2 × 2,

2 = 12 − 5 × 2,

5 = 17 − 12.

Substituting back, we get:

1 = 5 − (12 − 5 × 2) × 2 = 5 × 3 − 12 × 2 = (17 − 12) × 3 − 12 × 2.

Taking modulo 17, we get:

−2 × 12 ≡ 1 (mod 17).

Thus, x = 15 (since −2 ≡ 15 (mod 17)) is the inverse.

8
4 Lucas' Theorem for Computing Binomial Coecients
Modulo a Prime
Lucas' Theorem provides a powerful method to compute binomial coecients modulo a

n


prime number. Specically, it gives a way to compute
r
(mod p) for any non-negative

integers n and r, where p is a prime.

Statement of Lucas' Theorem

Let p be a prime number. For any non-negative integers n and r, express n and r in base

p as follows:

n = nk pk + nk−1 pk−1 + · · · + n1 p + n0 ,

r = rk pk + rk−1 pk−1 + · · · + r1 p + r0 ,

where 0 ≤ ni , ri < p for alli. Then,

       
n nk nk−1 n1 n0
≡ ··· (mod p).
r rk rk−1 r1 r0
n


If any ri > ni , then
r
≡ 0 (mod p).

Proof Outline
The proof of Lucas' Theorem relies on properties of binomial coecients and modular

arithmetic. The key idea is to break down n and r into their base p components and use

the properties of the binomial coecients under modulo p arithmetic.

100


Problem 4.1. Compute 35
mod 7.

Solution

Express 100 and 35 in base 7:

100 = 2 × 72 + 0 × 71 + 2 = 2027 ,

35 = 0 × 72 + 5 × 71 + 0 = 0507 .

9
Using Lucas' Theorem:
     
100 2 0 2
mod 7 ≡ mod 7
35 0 5 0
0


Since
5
= 0, we have:
 
100
≡0 (mod 7).
35
 
1000
Problem 4.2. Compute mod 13.
300
Solution

Express 1000 and 300 in base 13:

1000 = 5 × 132 + 11 × 13 + 12,

300 = 1 × 132 + 10 × 13 + 1.

Using Lucas' Theorem:

     
1000 5 11 12
mod 13 ≡ mod 13
300 1 10 1
≡ 5 × 11 × 12 mod 13

≡ 5(−2)(−1) mod13 ≡ 10 mod 13.

Applications
Lucas' Theorem is particularly useful in competitive programming and number theory,

where computing binomial coecients modulo a prime is common. It allows breaking

down the computation into smaller, manageable parts.

Exercises
(1) Find the modular multiplicative inverse of 13 modulo 701.

100


(2) Compute
50
(mod 13).

500


(3) Find
123
(mod 5).

n


(4) Prove that
r
≡ 0 (mod p) if n<r for a prime p.

10
5 Primality Testing
An integer p>1 is called a prime number if it has no proper divisors, that is, if its only

divisors are ±1 and ±p. A positive integer greater than 1 is composite if it is not a prime

number. The prime numbers which are less than 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,

31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

The fundamental theorem of arithmetic stated below describes prime numbers as basic

building blocks of natural numbers.

Theorem 5.1. Every positive integer n>1 is either a prime or a product of primes; this

representation is unique, apart from the order in which the factors occur.

Example 5.2. (i) 130 = 21 × 51 × 131. (ii) 212 = 22 × 53.

The problem of determining whether a given integer is prime is one of the important

problems in number theory. A primality test is an algorithm for determining whether an

input number is prime. The advent of cryptographic systems that use large primes, such

as RSA, was the main driving force for the development of fast and reliable methods for

primality testing.

The following is the oldest and most direct primality test.

 An integer n>1 is prime if and only if it has no prime divisors less than or equal to
√
n. "

Problem 5.3. Determine whether the integer 701 is prime. Also check 1009.

Solution:

√
We have 701 = 26.47640459. Since none of the prime numbers less than 27, that is,
√
2,3,5,7,11,131,7,19 and 23 divides 701. The integer 701 is a prime number. Also, 1009 =
31.76476035 and none of the prime numbers less than 32, that is, 2,3,5,7,11,131,7,19, 23,

29 and 31 divides 1009. Thus, 1009 is a prime number.

11
Sieve of Eratosthenes:
√
We have noted that if an integer n > 1 is not divisible by any prime p ≤ n, then

n is prime. Eratosthenes used this fact as the basis of a technique, called the Sieve of

Eratosthenes, for nding all primes below a given integer n. In this method, we rst write

down the integers from 2 to n in their natural order and then systematically eliminate

all the composite numbers by striking out all multiples 2p, 3p, 4p, 5p, . . . of the primes
√
p ≤ n. The integers that are left on the listthose that do not fall through the

sieveare primes.

Problem 5.4. Employing the Sieve of Eratosthenes, obtain all the primes between 1 and

100.

Solution:

Consider the sequence of consecutive integers from 1 to 100: 1, 2, 3, ..., 100. Since
√
100 = 10, we will eliminate all composite numbers by striking out all multiples of 2, 3,

5, and 7. After doing this, we will be left with the prime numbers between 1 and 100,

which are highlighted in the following list.

2 3 4
A 5 6
A 7 8
A 9
A 10

Z


Z 11 12
Z


Z 13 14
Z


Z 15
Z
 

Z 16
Z

Z 17 18
Z


Z

19 20
Z


Z 21
Z


Z 22
Z


Z 23 24
Z


Z 25
Z


Z 26
Z


Z 27
Z


Z 28
Z


Z 29 30
Z


Z 31 32
Z


Z 33
Z
 

Z 34
Z

Z 35
Z


Z 36
Z


Z

37 38
Z


Z 39
Z


Z 40
Z


Z 41 42
Z


Z 43 44
Z


Z 45
Z


Z 46
Z


Z 47 48
Z


Z 49
Z


Z 50
Z


Z 51
Z
 

Z 52
Z

Z 53 54
Z


Z

55
Z


Z 56
Z


Z 57
Z


Z 58
Z


Z 59 60
Z


Z 61 62
Z


Z 63
Z


Z 64
Z


Z 65
Z


Z 66
Z


Z 67 68
Z


Z 69
Z
 

Z 70
Z

Z 71 72
Z


Z

73 74
Z


Z 75
Z


Z 76
Z


Z 77
Z


Z 78
Z


Z 79 80
Z


Z 81
Z


Z 82
Z


Z 83 84
Z


Z 85
Z


Z 86
Z


Z 87
Z
 

Z 88
Z

Z 89 90
Z


Z

91
Z


Z 92
Z


Z 93
Z


Z 94
Z


Z 95
Z


Z 96
Z


Z 97 98
Z


Z 99
 H
Z

Z 100.

H

Problem 5.5. Employing the Sieve of Eratosthenes, obtain all the primes between 151

and 200.

Solution:

Consider the sequence of consecutive integers from 151 to 200: 151, 152, 153, ..., 200.

12
 √
Since 200 ∼
= 14.1421, we will eliminate all composite numbers by striking out all mul-

tiples of 2, 3, 5, 7, 11 and 13. After doing this, we will be left with the prime numbers

between 151 and 200, which are highlighted in the following list.

151 152
H

H 153
H

H 154
H

H 155
H

H 156
H

H 157 158
H

H 159
H

H 160
H

H 161
H

H 162
H

H 163 164
H

H 165
H

H

166
H

H 167 168
H

H 169
H

H 170
H

H 171
H

H 172
H

H 173 174
H

H 175
H

H 176
H

H 177
H

H 178
H

H 179 180
H

H

181 182
H

H 183
H

H 184
H

H 185
H

H 186
H

H 187
H

H 188
H

H 189
H

H 190
H
H 191 192
H

H 193 194
H

H 195
H

H

196
H

H 197 198
H

H 199 200.
H

H

Exercises

√
1. Determine whether the integer 773 is prime by testing all primes p≤ 773 as possible

divisors. Do the same for the integer 1013.

2. Employing the Sieve of Eratosthenes, obtain all the primes between 100 and 200.

13