High School Mathematics Extensions/Primes/Modular Arithmetic

HSME
Content
Primes
Modular Arithmetic
Problems & Projects
Problem Set
Project
Solutions
Exercise Solutions
Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

Modular Arithmetic

Introduction

Modular arithmetic connects with primes in an interesting way.

Modular arithmetic is a system in which all numbers up to some positive integer, n say, are used. So if you were to start counting you would go 0, 1, 2, 3, ... , n - 1 but instead of counting n you would start over at 0. And what would have been n + 1 would be 1 and what would have been n + 2 would be 2. Once 2n has been reached the number is reset to 0 again, and so on. Modular arithmetic is also called clock-arithmetic because we only use 12 numbers to tell standard time. On clocks we start at 1 instead of 0, continue to 12, and then start at 1 again. Hence the name clock-arithmetic.

The sequence also continues into what would be the negative numbers. What would have been -1 is now n - 1. For example, consider modulo 7 arithmetic, it's just like ordinary arithmetic except the only numbers we use are 0, 1, 2, 3, 4, 5 and 6. If we see a number outside of this range we add 7 to (or subtract 7 from) it, until it lies within that range.

As mentioned above, modular arithmetic is not that different to ordinary arithmetic. For example in modulo 7 arithmetic, we have

$3+2=5\!$

$5+6=11=4\!$

$5-6=-1=6\!$

and

${\begin{matrix}3\times 5=15=1\\5\times -6=-30=5\\\end{matrix}}$

We have done some calculation with negative numbers. Consider 5 × -6. Since -6 does not lie in the range 0 to 6, we need to add 7 to it until it does. And -6 + 7 = 1. So in modular 7 arithmetic, -6 = 1. In the above example we showed that 5 × -6 = -30 = 5, but 5 × 1 = 5. So we didn't do ourselves any harm by using -6 instead of 1. Why?

Note - Negatives: The preferred representation of -3 is 4, as -3 + 7 = 4, but using either -3 and 4 in a calculation will give us the same answer as long as we convert the final answer to a number between 0 and 6 (inclusive).

Exercise

Find in modulo 11

1.

-1 × -5

2.

3 × 7

3. Compute the first 10 the powers of 2

2¹, 2², 2³, ... , 2¹⁰

What do you notice?
Using the powers of 2 find

6¹, 6², 6³, ... , 6¹⁰

What do you notice again?

4.

${\sqrt {4}}$

i.e. find, by trial and error (or otherwise), all numbers x such that x² = 4 (mod 11). There are two solutions, find both .

5.

${\sqrt {9}}$

i.e. find all numbers x such that x² = 9 (mod 11). There are two solutions, find both.

Inverses

Consider a number n, the inverse of n is the number that when multiplied by n gives 1. For example, if we were to solve the following equation

$5x=3{\pmod {7}}\!$

the (mod 7) is used to make it clear that we are doing arithemetic modulo 7. We want to get rid of the 5 somehow. Multiplying it by something to turn it into a 1 would do the job. Notice that

$3\times 5=15=1{\pmod {7}}\!$

because 3 multiplied by 5 gives 1, we say 3 is the inverse of 5 in modulo 7. Now we multiply both sides by 3

$3\times 5\!$	$x\!$	$=3\times 3{\pmod {7}}\!$
	$x\!$	$=9{\pmod {7}}\!$
		$=2{\pmod {7}}\!$

So x = 2 modulo 7 is the required solution.

Definition (Inverse)

The inverse of (a number) x is a number y such that xy = 1. We denote the inverse of x by x^-1 or 1/x.

Inverse is unique

From above, we know the inverse of 5 is 3, but does 5 have another inverse? The answer is no. In fact, in any reasonable number system, a number can have one and only one inverse. We can see that from the following proof

Suppose n has two inverses b and c

$b=b\times 1=b(nc)=(bn)c=1\times c=c\!$

From the above argument, all inverses of n must be equal. As a result, if the number n has an inverse, the inverse must be unique.

An interesting property of any modulo n arithmetic is that the number n - 1 has itself as an inverse. That is, (n - 1) × (n - 1) = 1 (mod n), or we can write (n - 1)² = (-1)² = 1 (mod n). The proof is left as an exercise at the end of the section.

Existence of inverse

Not every number has an inverse in every modulo arithmetic. For example, 3 doesn't have an inverse mod 6, i.e., we can't find a number x such that 3x = 1 mod 6 (the reader can easily check).

Consider modulo 15 arithmetic and note that 15 is composite. We know the inverse of 1 is 1 and of 14 is 14. But what about 3, 6, 9, 12, 5 and 10? None of them has an inverse! Note that each of them shares a common factor with 15!

As an example, we show that 3 does not have an inverse modulo 15. Suppose 3 has an inverse x, then we have

$3x=1{\pmod {15}}\!$

We make the jump from modular arithemetic into rational number arithmetic. If 3x = 1 in modulo 15 arithmetic, then

$3x=15k+1\!$

for some integer k. Now we divide both sides by 3, we get

$x=5k+{\frac {1}{3}}\!$

But this cannot be true, because we know that x is an integer, not a fraction. Therefore 3 doesn't have an inverse in mod 15 arithmetic. To show that 10 doesn't have an inverse is harder and is left as an exercise.

We will now state the theorem regarding the existence of inverses in modular arithmetic.

Theorem

If n is prime then every number (except 0) has an inverse in modulo n arithmetic.

Similarly

If n is composite then every number that doesn't share a common factor with n has an inverse.

It is interesting to note that division is closely related to the concept of inverses. Consider the following expression

$6\times 3^{-1}{\pmod {7}}\!$

the conventional way to calculate the above would be to find the inverse of 3 (being 5). So

$6\times 3^{-1}=6\times 5=30=2{\pmod {7}}\!$

We write the inverse of 3 as 1/3, so we think of multiplying 3^-1 as dividing by 3, we get

$6\times {\frac {1}{3}}={\frac {6}{3}}=2{\pmod {7}}\!$

Notice that we got the same answer! In fact, the division method will always work if the inverse exists.

However, the expression in a different modulo system will produce the wrong answer, for example

$6\times 3^{-1}{\pmod {9}}\!$

we don't get 2, as 3^-1 does not exist in modulo 9, so we can't use the division method.

Exercise

1. Does 8 have an inverse in mod 16 arithemetic? If not, why not?

2. Find x mod 7 if x exists:

$x=2^{-1}\!$

$x=3^{-1}\!$

$x=4^{-1}\!$

$x=5^{-1}\!$

$x=6^{-1}\!$

$x=7^{-1}\!$

3. Calculate x in two ways, finding inverse and division

$x=28\cdot 7^{-1}\ \ {\mbox{(mod 29)}}\!$

4. (Trick) Find x

$x=5^{99}\times (40+3^{-1})\ {\pmod {11}}\!$

5. Find all inverses mod n (n ≤ 19)

Coprime and greatest common divisor

Two numbers are said to be coprimes if their greatest common divisor (gcd) is 1. E.g. 21 and 55 are both composite, but they are coprime as their greatest common divisor is 1. In other words, they do not share a common divisor other than 1.

There is a quick and elegant way to compute the gcd of two numbers, called Euclid's algorithm. Let's illustrate with a few examples:

Example 1:

Find the gcd of 21 and 49.

We set up a two-column table where the larger of the two numbers is on the right hand side as follows

smaller	larger
21	49

We now compute 49 (mod 21) which is 7 and put it in the second row smaller column, and put 21 into the larger column.

smaller	larger
21	49
7	21

Perform the same action on the second row to produce the third row.

smaller	larger
21	49
7	21
0	7

Whenever we see the number 0 appear on the smaller column, we know the corresponding larger number is the gcd of the two numbers we started with, i.e. 7 is the gcd of 21 and 49. This algorithm is called Euclid's algorithm.

Example 2

Find the gcd of 31 and 101

smaller	larger
31	101
8	31
7	8
1	7
0	1

Example 3

Find the gcd of 132 and 200

smaller	larger
132	200
68	132
64	68
4	64
0	4

Important to note

1. The gcd need not be a prime number.
2. The gcd of two different primes is 1. In other words, two different primes are always coprime.

Exercise

1. Determine whether the following sets of numbers are coprimes

1. 5050 5051
2. 59 78
3. 111 369
4. 2021 4032

2. Find the gcd of the numbers 15, 510 and 375

info -- Algorithm

An algorithm is a step-by-step description of a series of actions when performed correctly can accomplish a task. There are algorithms for finding primes, deciding whether 2 numbers are coprimes, finding inverses and many other purposes.
You'll learn how to implement some of the algorithms we have seen using a computer in the chapter [[../../../Mathematical Programming/]].

Finding Inverses

Let's look at the idea of inverse again, but from a different angle. In fact we will provide a sure-fire method to find the inverse of any number. Let's consider:

5x = 1 (mod 7)

We know x is the inverse of 5 and we can work out it is 3 reasonably quickly. But x = 10 is also a solution, so is x = 17, 24, 31, ... 7n + 3. So there are infinitely many solutions; therefore we say 3 is equivalent to 10, 17, 24, 31 and so on. This is a crucial observation.

Now let's consider

$216x\equiv 1\ \ {\mbox{(mod 811)}}$

A new notation is introduced here, it is the equal sign with three strokes instead of two. It is the "equivalent" sign; the above statement should read "216x is EQUIVALENT to 1" instead of "216x is EQUAL to 1". From now on, we will use the equivalent sign for modulo arithmetic and the equal sign for ordinary arithmetic.

Back to the example, we know that x exists, as gcd(811,216) = 1. The problem with the above question is that there is no quick way to decide the value of x! The best way we know is to multiply 216 by 1, 2, 3, 4... until we get the answer, there are at most 811 calculations, way too tedious for humans. But there is a better way, and we have touched on it quite a few times!

We notice that we could make the jump just like before into rational mathematics:

${\begin{matrix}216a&=&1+811b\\0&\equiv &1+163b&{\pmod {216}}\\\end{matrix}}$

We jump into rational maths again

${\begin{matrix}216c&=&1+163b\\53c&\equiv &1&{\pmod {163}}\\\end{matrix}}$

We jump once more

${\begin{matrix}53c&=&1+163d\\0&\equiv &1+4d&{\pmod {53}}\\\end{matrix}}$

Now the pattern is clear, we shall start from the beginning so that the process is not broken:

${\begin{matrix}216a&=&1+811b\\216c&=&1+163b\\53c&=&1+163d\\53e&=&1+4d\\e&=&1+4f\\\end{matrix}}$

Now all we have to do is choose a value for f and substitute it back to find a! Remember a is the inverse of 216 mod 811. We choose f = 0, therefore e = 1, d = 13, c = 40, b = 53 and finally a = 199! If f is chosen to be 1 we will get a different value for a.

The very perceptive reader should have noticed that this is just Euclid's gcd algorithm in reverse.

Here are a few more examples of this ingenious method in action:

Example 1

Find the smallest positive value of a:

${\begin{matrix}33a&\equiv &1\ \ {\mbox{(mod 101)}}\\33a&=&1+101b\\33c&=&1+2b\\c&=&1+2d\\\end{matrix}}$

Choose d = 0, therefore a = 49.

Example 2 Find the smallest positive value of a:

${\begin{matrix}27a&\equiv &1\ \ {\mbox{(mod 821)}}\\27a&=&1+821b\\27c&=&1+11b\\5c&=&1+11d\\5e&=&1+d\\\end{matrix}}$

Choose e = 0, therefore a = -152 = 669

Example 3 Find the smallest positive value of a:

${\begin{matrix}34a&\equiv &1\ \ {\mbox{(mod 55)}}\\34a&=&1+55b\\34c&=&1+21b\\13c&=&1+21d\\13e&=&1+8d\\5e&=&1+8f\\5g&=&1+3f\\2g&=&1+3h\\2i&=&1+h\\\end{matrix}}$

Set i = 0, then a = -21 = 34. Why is this so slow for two numbers that are so small? What can you say about the coefficients?

Example 4 Find the smallest positive value of a:

${\begin{matrix}21a&\equiv &1\ \ {\mbox{(mod 102)}}\\21a&=&1+102b\\21c&=&1+18b\\3c&=&1+18d\\3d&=&1\\\end{matrix}}$

Now d is not an integer, therefore 21 does not have an inverse mod 102.

What we have discussed so far is the method of finding integer solutions to equations of the form:

ax + by = 1

where x and y are the unknowns and a and b are two given constants, these equations are called linear Diophantine equations. It is interesting to note that sometimes there is no solution, but if a solution exists, it implies that infinitely many solutions exist.

Diophantine equation

In the Modular Arithmetic section, we stated a theorem that says if gcd(a,m) = 1 then a^-1 (the inverse of a) exists in mod m. It is not difficult to see that if p is prime then gcd(b,p) = 1 for all b less than p, therefore we can say that in mod p, every number except 0 has an inverse.

We also showed a way to find the inverse of any element mod p. In fact, finding the inverse of a number in modular arithmetic amounts to solving a type of equations called Diophantine equations. A Diophantine equation is an equation of the form

ax + by = d

where x and y are unknown.

As an example, we should try to find the inverse of 216 in mod 811. Let the inverse of 216 be x, we can write

$216x\equiv 1{\pmod {811}}\!$

we can rewrite the above in every day arithmetic

$216x+811y=1\!$

which is in the form of a Diophantine equation.

Now we are going to do the inelegant method of solving the above problem, and then the elegant method (using Magic Tables).

Both methods mentioned above uses the Euclid's algorithm for finding the gcd of two numbers. In fact, the gcd is closely related to the idea of an inverse. Let's apply the Euclid's algorithm on the two numbers 216 and 811. This time, however, we should store more details; more specifically, we want to set up an additional column called PQ which stands for partial quotient. The partial quotient is just a technical term for "how many n goes into m" e.g. The partial quotient of 3 and 19 is 6, the partial quotient of 4 and 21 is 5 and one last example the partial quotient of 7 and 49 is 7.

smaller	larger	PQ
216	811	3
163

The tables says three 216s goes into 811 with remainder 163, or symbollically:

811 = 3×216 + 163.

Let's continue:

smaller	larger	PQ
216	811	3
163	216	1
53	163	3
4	53	13
1	4	4
0	1

Reading off the table, we can form the following expressions

811 = 3× 216 + 163

216 = 1× 163 + 53

163 = 3× 53 + 4

53 =13× 4 + 1

Now that we can work out the inverse of 216 by working the results backwards

1 = 53 - 13×4

1 = 53 - 13×(163 - 3×53)

1 = 40×53 - 13×163

1 = 40×(216 - 163) - 13×163

1 = 40×216 - 53×163

1 = 40×216 - 53×(811 - 3×216)

1 = 199×216 - 53×811

Now look at the equation mod 811, we will see the inverse of 216 is 199.

Magic Table

The Magic Table is a more elegant way to do the above calculations, let us use the table we form from Euclid's algorithm

smaller	larger	PQ
216	811	3
163	216	1
53	163	3
4	53	13
1	4	4
0	1

Now we set up the so-called "magic table" which looks like this initially

0	1
1	0

Now we write the partial quotient on the first row:

		3	1	3	13	4
0	1
1	0

We produce the table according to the following rule:

Multiply a partial quotient one space to the left of it in a different row, add the product to the number two space to the left on the same row and put the sum in the corresponding row.

It sounds more complicated then it should. Let's illustrate by producing a column:

		3	1	3	13	4
0	1	3
1	0	1

We put a 3 in the second row because 3 = 3×1 + 0. We put a 1 in the third row because 1 = 3×0 + 1.

We shall now produce the whole table without disruption:

		3	1	3	13	4
0	1	3	4	15	199	811
1	0	1	1	4	53	216

We can check that

|199×216 - 811×53| = 1

In fact, if the magic table is contructed properly, and we cross multiplied and subtracted the last two column correctly, then we will always get 1 or -1, provided the two numbers we started with were coprimes. The magic table is just a cleaner way of doing the mathematics.

Exercises

1. Find the smallest positive x:

$216x\equiv 1\ \ {\mbox{(mod 816)}}$

2. Find the smallest positive x:

$42x\equiv 7\ \ {\mbox{(mod 217)}}$

3.

(a) Produce the magic table for 33a = 1 (mod 101)

(b) Evaluate and express in the form p/q

$3+{1 \over 16+{1 \over 2}}$

What do you notice?

4.

(a) Produce the magic table for 17a = 1 (mod 317)

(b) Evaluate and express in the form p/q

$18+{1 \over 1+{1 \over {1+{1 \over 1+{1 \over 5}}}}}$

What do you notice?

Chinese remainder theorem

The Chinese remainder theorem is known in China as Han Xing Dian Bing, which in its most naive translation means Han Xing counts his soldiers. The original problem goes like this:

There exists a number x, when divided by 3 leaves remainder 2, when divided by 5 leaves remainder 3 and when divided by 7 leaves remainder 2. Find the smallest x.

We translate the question into symbolic form:

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {5}}\\x&\equiv &2{\pmod {7}}\\\end{matrix}}$

How do we go about finding such a x? We shall use a familiar method and it is best illustrated by example:

Looking at x = 2 (mod 3), we make the jump into ordinary mathematics

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&=&2+3a\qquad (1)\end{matrix}}$

Now we look at the equation modulo 5

$2+\!$	$3a\!$	$\equiv 3{\pmod {5}}\!$
	$3a\!$	$\equiv 1{\pmod {5}}\!$
	$a\!$	$\equiv 2{\pmod {5}}\!$
	$a\!$	$=2+5b\!$

Substitute into (1) to get the following

$x\!$	$=2+3(2+5b)\!$
	$=8+15b\!$

Now look at the above modulo 7

$x=8+15b\equiv 2{\pmod {7}}\!$

we get

$b\equiv 1{\pmod {7}}\!$

We choose b = 1 to minimize x, therefore x = 23. And a simple check (to be performed by the reader) should confirm that x = 23 is a solution. A good question to ask is what is the next smallest x that satisfies the three congruences? The answer is x = 128, and the next is 233 and the next is 338, and they differ by 105, the product of 3, 5 and 7.

We will illustrate the method of solving a system of congruences further by the following examples:

Example 1 Find the smallest x that satisfies:

$x\equiv 1{\pmod {3}}\!$

$x\equiv 2{\pmod {5}}\!$

$x\equiv 3{\pmod {7}}\!$

Solution

$x=\!$	$1+3\!$	$a\!$	$\equiv \!$	$2{\pmod {5}}\!$
		$a\!$	$=\!$	$2+5b\!$

now substitute back into the first equation, we get

$x\!$	$=1+3(2+5b)\!$
	$=7+15b\!$
	$\equiv 3{\pmod {7}}\!$

we obtain

$b\equiv 3{\pmod {7}}\!$

$b=3+7c\!$

again substituting back

$x\!$	$=7+15(3+7c)\!$
	$=52+15\times 7c\!$

Therefore 52 is the smallest x that satisfies the congruences.

Example 2

Find the smallest x that satisfies:

$x\equiv 5{\pmod {11}}\!$

$x\equiv 3{\pmod {7}}\!$

$x\equiv 8{\pmod {9}}\!$

Solution

$x\!$	$=5+11\!$	$a\equiv 3{\pmod {7}}\!$
		$a\equiv 3{\pmod {7}}\!$
		$a=3+7b\!$

substituting back

$x=\!$	$5+11(3+7b)\!$
$=\!$	$38+11\times 7b\!$
$\equiv \!$	$8{\pmod {9}}\!$

now solve for b

$2+2\times 7b\!$	$\equiv 8{\pmod {9}}\!$
$b\!$	$\equiv 3{\pmod {9}}\!$
$b\!$	$=3+9c\!$

again, substitue back

$x\!$	$=\!$	$38+11\times 7(3+9c)\!$
	$=\!$	$269+11\times 7\times 9c\!$

Therefore 269 is the smallest x that satisfies the congruences.

Exercises

1. Solve for x

${\begin{matrix}3x&\equiv &5{\pmod {14}}\\2x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {15}}\\\end{matrix}}$

2. Solve for x

${\begin{matrix}3x&\equiv &5{\pmod {19}}\\7x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {11}}\\\end{matrix}}$

*Existence of a solution*

The exercises above all have a solution. So does there exist a system of congruences such that no solution could be found? It certainly is possible, consider:

x ≡ 5 (mod 15)

x ≡ 10 (mod 21)

a cheekier example is:

x ≡ 1 (mod 2)

x ≡ 0 (mod 2)

but we won't consider silly examples like that.

Back to the first example, we can try to solve it by doing:

${\begin{matrix}x&=&5+15k&\equiv &10&{\pmod {21}}\\&&15k&\equiv &5&\\&&3k&\equiv &1&\\\end{matrix}}$

the above equation has no solution because 3 does not have an inverse modulo 21!

One may be quick to conclude that if two modulo systems share a common factor then there is no solution. But this is not true! Consider:

$x\equiv 4{\pmod {15}}\!$

$x\equiv 7{\pmod {21}}\!$

we can find a solution

$x=\!$	$4+15k\!$	$\equiv 7{\pmod {21}}\!$
	$15k\!$	$\equiv 3{\pmod {21}}\!$
	$5\times 3k\!$	$\equiv 3{\pmod {21}}\!$

we now multiply both sides by the inverse of 5 (which is 17), we obtain

$3k\equiv 9\!$

obviously, k = 3 is a solution, and the two modulo systems are the same as the first example (i.e. 15 and 21).

So what determines whether a system of congruences has a solution or not? Let's consider the general case:

$x\equiv a{\pmod {m}}\!$

$x\equiv b{\pmod {n}}\!$

we have

$x=a+km\!$

$x=b+ln\!$

essentially, the problem asks us to find k and l such that the above equations are satisfied.

We can approach the problem as follows

$0=(a-b)+(km-ln)\,\!$

$(ln-km)=(a-b)\,\!$

now suppose m and n have gcd(m,n) = d, and m = dm_o, n = dn_o. We have

$dln_{o}-dkm_{o}=(a-b)\,\!$

$ln_{o}-km_{o}=(a-b)/d\,\!$

if (a - b)/d is an integer then we can read the equation mod m_o, we have:

$ln_{o}\equiv (a-b)/d{\pmod {m_{o}}}\,\!$

Again, the above only makes sense if (a - b)/d is integeral. Also if (a - b)/d is an integer, then there is a solution, as m_o and n_o are coprimes!

In summary: for a system of two congruent equations

$x\equiv a{\pmod {m}}\,\!$

$x\equiv b{\pmod {n}}\,\!$

there is a solution if and only if

d = gcd(m,n) divides (a - b)

And the above generalises well into more than 2 congruences. For a system of n congruences:

$x\equiv a_{1}{\pmod {m_{1}}}\,\!$

$x\equiv a_{2}{\pmod {m_{2}}}\,\!$

...

$x\equiv a_{n}{\pmod {m_{n}}}\,\!$

for a solution to exist, we require that if i ≠ j

gcd(m_i,m_j) divides (a_i - a_j)

Exercises

Decide whether a solution exists for each of the congruences. Explain why.

1.

x ≡ 7 (mod 25)

x ≡ 22 (mod 45)

2.

x ≡ 7 (mod 23)

x ≡ 3 (mod 11)

x ≡ 3 (mod 13)

3.

x ≡ 7 (mod 25)

x ≡ 22 (mod 45)

x ≡ 7 (mod 11)

4.

x ≡ 4 (mod 28)

x ≡ 28 (mod 52)

x ≡ 24 (mod 32)

To go further

This chapter has been a gentle introduction to number theory, a profoundly beautiful branch of mathematics. It is gentle in the sense that it is mathematically light and overall quite easy. If you enjoyed the material in this chapter, you would also enjoy Further Modular Arithmetic, which is a harder and more rigorous treatment of the subject.

Also, if you feel like a challenge you may like to try out the Problem Set we have prepared for you. On the other hand, the project asks you to take a more investigative approach to work through some of the finer implications of the Chinese Remainder Theorem.

Acknowledgement

Acknowledgement: This chapter of the textbook owes much of its inspiration to Terry Gagen, Emeritus Associate Professor of Mathematics at the University of Sydney, and his lecture notes on "Number Theory and Algebra". Terry is a much loved figure among his students and is renowned for his entertaining style of teaching.

Reference

1. The Largest Known Primes--A Summary

Feedback

What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.