9.2 – Modular Arithmetic

You’ll terribly ‘love’ this section.

---

Consider how you read your time on the clock. Every time the short hand goes one round, it will be 12 hours. So when the shorthand goes past another hour, it will be 13 hours, and the time might be 13 o’ clock. We know, however that 13’ o clock is actually 1 o’ clock. Same to 25 o’ clock, it still means the same thing. We say that the clock follows a modular system.

Modular Arithmetic, is the calculations of numbers in a modular system. In the clock’s system, it is of modulo 12. When two numbers a and b are congruent to each other in the same modulo, we denote it by
a ≡ b (mod m)

This equation is read as ‘a is congruent to b modulo m’. For example, 13 ≡ 1 (mod 12), this means that 13 is the same as 1 in a modulo 12 system. Note that the main equation is the part on the left hand side, 13 ≡ 1, while the right hand side, (mod 12), tells you that this equation is valid only in modulo 12. This modulo system also has another explanation for it. a ≡ b (mod m) means that a and b give the same remainder when divided by m. Notice that 13 divided by 12 gives remainder 1, while 1 divided by 12 also gives the remainder 1. Or using the mod terminology, we say that
a mod m = b mod m

Take note that a ≡ b (mod m) and a = b mod m both bring different meanings. The latter says that ‘a is the remainder when b is divided by m’.

Now, bringing divisibility in, we say that
a ≡ b (mod m) if and only if m | (a – b)

Can you see that m divides a and b? And if that is the case, a and b actually have a difference of a multiple of m. So this means that, 49 ≡ 37 ≡ 25 ≡ 13 ≡ 1 (mod 12). You just add 12 to the number, you get another number which is congruent modulo 12.

If I convert this notation a ≡ b (mod m) into algebra, it can be written as a = b + km, where k is a constant (try verifying this with the divisibility notation above). So to summarize things up:

When a ≡ b (mod m), then
a mod m = b mod m
m | (a – b)
a = b + km

---

Before we go into solving linear congruences, we need to know some basic rules of modular arithmetic. These rules below can be proven by yourself, and so try doing it.

If a ≡ b (mod m) and c ≡ d (mod m), then

1. a + c ≡ b + d (mod m)
2. a – c ≡ b – d (mod m)
When in the same modulo m, the addition and subtraction rules work as usual. This will be useful when you are solving simultaneous modular arithmetic equations. This can be proven by using its algebraic form, a = b + km, c = d + lm.

3. ac ≡ bd (mod m)
This is also important, and uses the same method above to prove.

4. a^k ≡ b^k (mod m)
Where k is a constant, a positive integer. I’ll proof this one here for you:
When a – b = km, then a^k – b^k = (a – b)(a^k-1 + a^k-2b + a^k-3b² + … + ab^k-2 + b^k-1), which is a multiple of (a – b). Therefore, a^k – b^k = lm, where l is a constant, and therefore
a^k – b^k ≡ 0 (mod m)
a^k ≡ b^k (mod m)

5. ak ≡ bk (mod m)
The congruence holds even when a constant is multiplied to both sides of the equation. Same proof as 1, 2 and 3.

Next, try proving both the equations below (make use of the information that
a ≡ (a mod m) (mod m):
6. (a + b) mod m ≡ [(a mod m) + (b mod m)] (mod m)
7. ab mod m ≡ [(a mod m)(b mod m)] (mod m)

8. The Simplification Law
If c | a, c | b, c | m, and a ≡ b (mod m), then

To summarize this rule, it means that a constant c can only be divided out from a, b and m if it divides all of them. Provable too.

Here’s another one not to be confused with the former, the cancellation law. If gcd (c,m) = 1, then
9. ac ≡ bc (mod m) ⇒ a ≡ b (mod m)
You can prove this too. Suppose ac – bc = (a – b)c = km. Since gcd (c, m) = 1, c and m have no common divisors, and therefore c | k. Since c divides this constant k, c can be cancelled out, and thus a – b = nm for some integer n. Here we see that a ≡ b (mod m), which was to be shown.

---

FINDING THE INVERSE 

b, the multiplicative inverse of a number a is such that ab = 1. Here, we can find that b is actually the reciprocal of the number a. Here in modular arithmetic, we are going to look for an inverse of a, such that
ab ≡ 1 (mod m)

Let us recall the Euclidean Algorithm. We learnt that we could find gcd (a, m) by dividing the bigger number with the smaller number, and continue to divide the smaller number with its remainder, and so on until there is no remainder. Indeed, we could make use of this information to find the gcd in terms of a linear combination of these 2 integers, such that
gcd (a, m) = m • n + a • b

where n and b are integers. If gcd (a, m) = 1, then an inverse of a exist, and the integer b happens to be the inverse of a. We will see why this is true in the following example:

Find gcd (123, 2347) and write it as a linear combination of these integers, and further find the inverse of 123 modulo 2347.

2347 = 123 • 19 + 10
123 = 10 • 12 + 3
10 = 3 • 3 + 1
3 = 1 • 3
∴ gcd (123, 2347) = 1

Now, to get the linear combination thingy, we have to reverse all of the above equations. Let me rewrite them again:
10 = 2347 – 123 • 19 (1)
3 = 123 – 10 • 12        (2)
1 = 10 – 3 • 3               (3)

Now we will do some back substitution. We want an equation of gcd (123, 2347) (which is 1) to be in terms of 123 and 2347. We start with equation (3), and substitute equation (2), we have
1 = 10 – 3 • (123 – 10 • 12)
   = 10 – 3 • 123 + 10 • 36
   = 10 • 37 – 3 • 123

Repeating the process with equation (1),
1 = (2347 – 123 • 19) • 37 – 3 • 123
1 = 2347 • 37 – 123 • 706

We have now shown the gcd (123, 2347) in terms of a linear combination of its numbers. This is what we called as the extended Euclidean Algorithm. Here, we find that the inverse of 123 modulo 2347 is –706. We see that
-706 • 123 ≡ –86838 ≡ 1 (mod 2347)

Note that every integer congruent to –706 modulo 2347 is also the inverse of 123, which we find it best to represent the inverse of 123 as 1641, a positive integer less than 2347.

I haven’t tell you why this works. Since gcd (a, m) = 1, and we know that it can be represented as a linear combination 1 = m • n + a • b, we can show that
m • n + a • b ≡ 1 (mod m)

You should understand this equation. If 1 = 3 – 2, then 1 ≡ 3 – 2 for whatever modulo, and that make sense. Here, since m • n ≡ 0 (mod m), as this is obvious, since m divides itself completely, in whatever given n. So in the end, we have a • b ≡ 1 (mod m), which was what we used just now. Note that not all integers have inverses in a particular modulo. It is only in the case where gcd (a, m) such that there will be an inverse.

By the way, the inverse could also slowly be found by trial and error for small moduli. For example, 2 mod 3. Try multiplying the numbers between 1 to 3 to the number 2, and you find that 2 • 2 ≡ 4 ≡ 1 (mod 3). And thus, 2 is the inverse of 2 modulo 3.

---

SOLVING LINEAR CONGRUENCES

A linear congruence equation has the form
ax ≡ b (mod m)

In which we want to find x. If you can relate this to the section above, it has a solution only if gcd (a, m) = 1. This can be solved by finding the inverse of a. Let’s try an example:

Solve the linear congruence 3x ≡ 4 (mod 7).

We have checked that gcd (3, 7) = 1, and so an inverse of 3 exist, and thus the solution exists. Using the extended Euclidean Algorithm, we get the inverse of 3 as –2. So multiplying –2 to both sides,

-2 • 3x ≡ –2 • 4 (mod 7)

We know that –2 • 3 ≡ 1 (mod 7), and therefore

x ≡ –8 ≡ 6 (mod 7)

substituting 6 back into x, you get the answer correct. Besides, substituting any integer which is congruent to 6 modulo 7, like 13, 20, –8, –1 and etc are also solutions of the linear congruence.

In cases where gcd (a, m) ≠ 1, there are solutions too, only if gcd (a, m) | b, and there are gcd (a, m) solutions. For example,
2x ≡ 6 (mod 8) has gcd (2, 8) = 2 solutions, but 2x ≡ 5 (mod 8) has no solution. Let’s try to solve the linear congruence 2x ≡ 6 (mod 8). You can solve it as follows:

Using the simplification law, you see that 2 divides 2, 6 and 8 and therefore
x ≡ 3 (mod 4)
which is in another modulo system. If you want the solution to be in the same modulo system, then you need to do some modification. By looking at the equation, you know that
x ≡ 3 (mod 8)
is one solution. The other solution is by adding 3 to the new modulo system you get above, which is 4. You get another solution,
x ≡ 7 (mod 8)

So your solution for the linear congruence 2x ≡ 6 (mod 8) is x ≡ 3 (mod 8), x ≡ 7 (mod 8).

This same method applies: When there are 10 solutions, you keep on adding the new modulo system integer value to the existing answer, until you get 10 solutions.

Let’s try another one, 2x ≡ 6 (mod 9). Using rule number 9 above, you can quickly see that gcd (2, 9) = 1, and therefore x ≡ 3 (mod 9). Try not to confuse this one with the one above.

---

SIMULTANEOUS LINEAR CONGRUENCES

Similar to the one above, now you have 2 congruences with 2 unknowns, under the same modulo. Let’s consider a system of linear congruences with 2 unknowns:
ax + by ≡ k (mod m)
cx + dy ≡ n (mod m)

We first write this in matrix form:

For this system of congruences to have a solution, there must be an inverse for the matrix. This means, that ad – bc must not be zero, and must exist. Let’s multiply the left and right hand side with its adjoint matrix:

Now we get 2 linear congruences,
(ad – bc) x ≡ (dk – bn) (mod m)
(ad – bc) y ≡ (an – ck) (mod m)

and for such linear congruences to have solution, again we must make sure that the equation gcd (ad – bc, m) = 1 holds. With that you can solve the above 2 linear congruences for x and y. This kind of question came out in STPM 2009, my year. Try solving it with the method I just showed you.

---

QUADRATIC RESIDUE MODULO M

a quadratic residue modulo m has the form
x² ≡ q (mod m)

You are supposed to solve the equation in terms of x. I don’t know of any short cut to solve such a problem, but one way is to list out all the possible values, draw a table, and find the answer. Example,

Solve the quadratic residue modulo x² ≡ 2 (mod 7).

We proceed to draw a table:

Therefore, we conclude that x ≡ 3 (mod 7) and x ≡ 4 (mod 7).
If you have noticed, we could actually solve linear congruences with the above trial & error method too.

If m is very big but divisible, we could break the modulo system up. For example,
x² ≡ 14 (mod 35)

We can make it into 2 equations, namely x² ≡ 14 ≡ 0 (mod 7) and x² ≡ 14 ≡ 4 (mod 5).
Tabulating the table,
x² ≡ 0 (mod 7) has the solution x ≡ 0 (mod 7).
x² ≡ 4 (mod 5) has solutions x ≡ 2 (mod 5) and x ≡ 3 (mod 5)

x ≡ 0 (mod 7) means that
x ≡ 0, 7, 14, 21, 28 (mod 35) are solutions of modulo 35.

x ≡ 2 (mod 5) means that
x ≡ 2, 7, 12, 17, 22, 27, 32 (mod 35) are solutions of modulo 35.

x ≡ 3 (mod 5) means that
x ≡ 8, 13, 18, 23, 28, 33 (mod 35) are solutions of modulo 35.

We find the intersections of x ≡ 0 (mod 7) and x ≡ 2 (mod 5), we get
x ≡ 7 (mod 35)
And we find the intersections of x ≡ 0 (mod 7) and x ≡ 3 (mod 35), we get
x ≡ 28 (mod 35)

And our final answer solution is
x ≡ 7, 28 (mod 35)

---

MODULAR EXPONENTIATION

I don’t think this is in the syllabus, but it is good for you to know. Modular exponentiations are of the form aⁿ mod m. You are normally asked to compute it with a very big value of n. For example,

Find 3¹⁰¹ mod 100.

First, do you still remember what are binary numbers? Express the term n in binary form, by keep on dividing the number with 2, writing the remainder by the side. Recall your Form 4 Maths:

So we get 101 = (1100101)₂ = 2⁶ + 2⁵ + 2² + 2⁰ = 64 + 32 + 4 + 1
Substituting it back to the congruence,
3^64+32+4+1 mod 100 = 3⁶⁴3³²3⁴3¹ mod 100

Now, we need to tabulate the amounts congruent to 3⁶⁴ 3³² 3⁴ and 3¹.

3² ≡ 9
3⁴ ≡ 9² ≡ 81
3⁸ ≡ 81² ≡ 61
3¹⁶ ≡ 61² ≡ 21
3³² ≡ 21² ≡ 41
3⁶⁴ ≡ 41² ≡ 81

Now you know all the values, substitute them back into the equation,
3⁶⁴3³²3⁴3¹ ≡ 81 • 41 • 81 • 3 ≡ 3 (mod 100)

Spend some time understanding my calculations. If not, just pray that it won’t come out in exams.

---

CHINESE REMAINDER THEOREM

In the 1st century, the Chinese Mathematician Sun-Tsu asked:

There are certain things whose number is unknown. When divided by 3, the remainder is 2; when divided by 5, the remainder is 3; and when divided by 7, the remainder is 2. What will be the number of things?

This puzzle can be translated into the following question: What are the solutions of the systems of congruences

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7) ?

The Chinese Remainder Theorem, named after the Chinese heritage of problems involving systems of linear congruences, states that when the moduli of a system of linear congruences are pairwise relatively prime, there is a unique solution of the system modulo the product of the moduli.

I will omit the proof, because I don’t understand it either. Here are the steps to solve this kind of problems:

Firstly, for a system of linear congruences with different moduli,
x ≡ a (mod m)
x ≡ b (mod n)
x ≡ c (mod o)

We construct a number M being the product of the moduli,
M = m • n • o

Then, we construct a number M_m, M_n and M_o such that they are the product of the all the moduli in the system other than itself. Which means,

Then, find the inverse of M_m, M_n and M_o respectively:
M_mM̅_m ≡ 1 (mod m)
M_nM̅_n ≡ 1 (mod n)
M_oM̅_o ≡ 1 (mod o)

And finally, your answer will be:

Let’s try to solve Sun Tsu’s problem.
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

M = 105,
M₃ = 35 ≡ 2 (mod 3), inverse M̅₃ is 2.
M₅ = 21 ≡ 1 (mod 5), inverse M̅₅ is 1.
M₇ = 15 ≡ 1 (mod 7), inverse M̅₇ is 1.

∴ x ≡ (2 • 2 • 35) + (1 • 3 • 21) + (1 • 2 • 15) ≡ 233 ≡ 23 (mod 105)

Note that you cannot let M₃ = 2, M₅ = 1 and M₇ = 1, as you will get a total different answer. However, the inverses can be any other number congruent to itself in its particular modulo.

---

FERMAT’S LITTLE THEOREM

If p is a prime number and a is an integer not divisible by p, then
a^p-1 ≡ 1 (mod p)
a^p ≡ a (mod p)

This theorem is here for you to identify if a congruence can be solved easily. Similarly, I won’t prove it, so just keep this theorem in mind and use it if needed.

---

Very hard, isn’t it? That is why Number Theory is known as the “Queen of Mathematics”. Spend some time digesting this section, and figuring out why numbers can be so complicated.☺

9.1 – Divisibility

Number Theory is considered one of the hardest sections in Mathematics. It is the study of the very fundamentals of numbers, yet can be very complicated. Information on this chapter for such a level of study is very rare, so I hope you will appreciate everything that I have for you over here.

---

We have been learning division since standard 2. But today, we will look at it at a different manner. If a and b are integers with a ≠ 0, then we say that a divides b if there is an integer c such that b = ac. When a divides b we say that a is a factor of b and that b is a multiple of a. The notation a | b denotes that a divides b (which means, there is no remainder). We write a ł b when a doesn’t divide b. For example, 2 | 4, but 4 ł 2. Take note that the notation 2 | 4 and 2/4 are 2 different things. The former is the notation for divisibility, while the latter is simply a fraction.

There are certain rules of divisibility that you should know. These are:

1. If a | b, b | c, then a | c.
You should know how to prove this. As above, the term a | b can be written as ak = b, bl = c, and therefore akl = bl = c. Here, k and l are integers.

2. If a | b, a | c, then a | (b + c) and a | (mb + nc).

3. If a | b, then a | bc.

The above 2 can also be proven with the similar notation as 1.

Not every 2 numbers can divide each other. For example, 2 does not divide 7, as it leaves a remainder of 1. Here we represent the above in an equation, which is
7 = 2•3 + 1

Here, 3 is the quotient, we denote the quotient as a div b, which in this case, 2 div 7 = 3. 1 is the remainder,  which we denote as a mod b, and here we have 2 mod 7 = 1. Note that a remainder has to be positive. For example, –7 = 2• –3 – 1 is wrong, because it then gives us 2 div –7 = –3 and 2 mod –7 = –1, a negative remainder. It should be –7 = 2• –4 + 1, which in turns give 2 div –7 = –4 and 2 mod –7 = 1. Try doing –2 mod 7 and –2 div 7, and see whether the answers are different.

---

A prime number is a number that is only divisible by 1 and by the number itself. A number which is not prime, is called as a composite number. The smallest prime number is 2, and it goes on as 3, 5, 7, 11, 13, 17, 19… and so on. The interesting thing about prime numbers is that, you are unable to write a formula to determine the sequence or series of prime numbers. So therefore, if we want to find a very huge prime number, we need to slowly divide the number by almost every possible number before we say that it is prime. One very famous example used in the past is the sieve of Eratosthenes, which is used to find all the primes below 100. It is done by first listing down all the numbers from 1 to 100. Then, slowly cross out the multiples of 2, 3, 4 and so on, until you have nothing to cross out. The rest of the numbers, are primes! Another one is The Prime Number Theorem. You might wanna google about it.

So how do you know whether a number is prime, for a relatively small number? There is a way to find out, at least a little faster than trying to divide the number by any number smaller than itself. It is found that if a number is not divisible by primes less than its square root, then it is a prime number. This can be proven. If we have a composite number n such that ab = n, then if a > √n and b > √n, then we have ab > √n • √n > n, which is a contradiction. Although it does speed up the process of finding primes, it is still quite a slow method.

Prime numbers are the building blocks of all numbers. the Fundamental Theorem of Arithmetic states that:

Every positive integer > 1 can be written uniquely as a prime or as the product of 2 or more primes where the prime factors are written in order of non-decreasing size.

This is what we called as prime factorisation. For example, 4 = 2², 100 = 2²5², 641 = 641 and so on. We can write down any number in terms of products of primes, a = 2^x3^y5^z7^w… and so on.

There’s a lot to talk about prime numbers. One famous argument was to prove that there are infinitely many primes. Suppose you label every prime number as p₁, p₂, p₃ and so on. You found the greatest prime number in the world, called as p_n. So if we write a particular number a such that a = p₁p₂p₃…p_n + 1, it must have been a prime, since it couldn’t be represented as the product of any primes smaller than p_n. This contradicts with what we said earlier on about finding the greatest prime number, and therefore proves that there are indeed infinitely many primes.

Another 2 interesting stuff on prime numbers are the Goldbach’s Conjecture and the Twin Prime Conjecture. Go look up on it if you are free.

---

Now, let’s move on to the gcd and lcm. Try recalling whether this sounds familiar to your Form 1 Mathematics. gcd is the  greatest common divisor (you are probably more familiar to the name highest common factor, or HCF), while lcm is the lowest common multiple. Here we denote k = gcd (a, b) to have the meaning of “k is the greatest common divisor of the integers a and b”. Similarly, k = lcm (a, b) means “k is the lowest common multiple of the integers a and b”. For example, gcd (4, 6) = 2 and lcm (5, 6) = 30.

Relating this back to prime numbers, for any 2 integers a and b, if gcd (a, b) = 1, we say that they are relatively prime. For example, 5 and 6 are relatively prime.

Do you still remember the method to find your lcm and gcd in Form 1? You had to draw out something like a ladder or so. But here, we will use another method, which has something to do with the prime factorization. For example,

Find gcd (120, 500) and lcm (120, 500).

We first start by representing the numbers 120 and 500 in terms of primes.
120 = 2³ • 3 • 5
500 = 2² • 5³

Now, the formulas to find the gcd and lcm are easy, it is just
gcd (a, b) = p₁^min(a1,b1)p₂^min(a2,b2)p₃^min(a3,b3)…p_n^min(an,bn)
lcm (a, b) = p₁^max(a1,b1)p₂^max(a2,b2)p₃^max(a3,b3)…p_n^max(an,bn)

You first compare the primes present among the 2 numbers 120 and 500. p₁^max(a1,b1) means the maximum of the powers of that particular prime p₁ of the 2 numbers a and b, while p₁^min(a,b) means the minimum. So plugging in the numbers, we have
gcd (120, 500) = 2^min(3,2) • 3^min(1,0) • 5^min(1,3) = 2²3⁰5¹ = 20
lcm (120, 500) = 2^max(3,2) • 3^max(1,0) • 5^max(1,3) = 2³3¹5³ = 3000

From here, we obtain a new formula, as we can see that
ab = gcd (a,b) • lcm (a,b)

---

The method described for computing the greatest common divisor of 2 integers, using the prime factorizations of these integers, is inefficient. The reason is that it is time consuming to find prime factorizations. Now I will teach you a more efficient method of finding the gcd, called the Euclidian Algorithm (also Euclid’s Algorithm). It is named after the ancient Greek mathematician Euclid, who included a description of this algorithm in his book The Elements. Let’s start with an example.

Find gcd (91, 287).

First, we use the smaller term to divide the bigger term. Then, we take the divisor of and the remainder of the equation, repeat the process, until we get no more remainder. The last remainder is  the gcd that we are finding. So we have
287 = 91 • 3 + 14
91 = 14 • 6 + 7
14 = 7 • 2

∴ gcd (91, 287) = 7

You might be puzzled as in how did this method work. Basically, this method is formulated from the results
if a = bq + r, then gcd (a, b) = gcd (b, r)

From
a = bq + r

I know that if some integer k divides a, it must divide b and r as well. Now I turn the equation around
a – bq = r

If some integer divides both a and b, then it must divide r. So here, the biggest integer that can divide a, b and r must be the same integer, which is gcd (a, b), and also gcd (b, r). So therefore, the Euclidean Algorithm is valid.

---

That’s all for this section. The Euclidean Algorithm will be further used in the next section, so make sure you do some practices on it. ☺