High School Mathematics Extensions/Primes/Full

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

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

Introduction

A prime number (or prime for short) is a natural number that has exactly two divisors: itself and the number 1. Since 1 has only one divisor — itself — we do not consider it to be a prime number but a unit. So, 2 is the first prime, 3 is the next prime, but 4 is not a prime because 4 divided by 2 equals 2 without a remainder. We've proved 4 has three divisors: 1, 2, and 4. Numbers with more than two divisors are called composite numbers.

The first 20 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71.

Primes are an endless source of fascination for mathematicians. Some of the problems concerning primes are so difficult that even decades of work by some of the most brilliant mathematicians have failed to solve them. One such problem is Goldbach's conjecture, which proposes that all even numbers greater than 3 can be expressed as the sum of two primes. No one has been able to prove it true or false.

This chapter will introduce some of the elementary properties of primes and their connection to an area of mathematics called modular arithmetic.

Geometric meaning of primes

The first three figures on top show the different ways to assemble 12 square floor tiles into a rectangle. The bottom three shows that seven cannot be fully divided by two, the image on the left, or three, the image on the right.

Given 12 pieces of square floor tiles, can we assemble them into a rectangular shape in more than one way? Of course we can, this is due to the fact that

${\begin{matrix}12&=&12\times 1\\&=&6\times 2\\&=&4\times 3\\\end{matrix}}$

We do not distinguish between 2×6 and 6×2 because they are essentially equivalent arrangements.

But what about the number 7? Can you arrange 7 square floor tiles into rectangular shapes in more than one way? The answer is no, because 7 is a prime number.

Fundamental Theorem of Arithmetic

A theorem is a non-obvious mathematical fact. A theorem must be proven; a proposition that is generally believed to be true, but without a proof, is called a conjecture or a hypothesis.

With those definitions out of the way the fundamental theorem of arithmetic simply states that:

Any natural number (except for 1) can be expressed as the product of primes in one and only one way.

For example

$12=2\times 2\times 3\,\!$

Rearranging the multiplication order is not considered a different representation of the number, so there is no other way of expressing 12 as the product of primes.

A few more examples

${\begin{matrix}99&=&3&\times &3&\times &11\\52&=&2&\times &2&\times &13\\17&=&17&\end{matrix}}$

It can be easily seen that a composite number has more than one prime factor (counting recurring prime factors multiple times).

Why?

Bearing in mind the definition of the fundamental theorem of arithmetic, why isn't the number 1 considered a prime?

Factorization

We know from the fundamental theorem of arithmetic that any integer can be expressed as the product of primes. The million dollar question is: given a number x, is there an easy way to find all prime factors of x?

If x is a small number then it is easy. For example 90 = 2 × 3 × 3 × 5. But what if x is large? For example x = 4539? Most people can't factorize 4539 into primes in their heads. But can a computer do it? Yes, the computer can factorize 4539 fairly quickly. We have 4539 = 3 × 17 × 89.

Since computers are very good at doing arithmetic, we can work out all the factors of x by simply instructing the computer to divide x by 2 then 3 then 5 then 7 ... and so on.

So there is an easy way to factorize a number into prime factors. Just apply the method described above. However, that method is too slow for large numbers: trying to factorize a number with thousands of digits would take more time than the current age of the universe. But is there a fast way? Or more precisely, is there an efficient way? There may be, but no one has found one yet. Some of the most widely used encryption schemes today (such as RSA) make use of the fact that we can't factorize large numbers into prime factors quickly. If such a method is found, a lot of internet transactions will be rendered unsafe.

Consider the following three examples of the dividing method in action.

Example 1

$x=21$

${\frac {x}{2}}=10.5$ not a whole number, so 2 is not a factor of 21

${\frac {x}{3}}=7$ hence 3 and 7 are the factors of 21.

Example 2

$x=153$

${\frac {x}{2}}=76.5$ hence 2 is not a factor of 153

${\frac {x}{3}}=51$ hence 3 and 51 are factors of 153

${\frac {51}{3}}=17$ hence 3 and 17 are factors of 153

It is clear that 3, 9, 17 and 51 are the factors of 153. The prime factors of 153 are 3, 3 and 17 (3×3×17 = 153)

Example 3

${\frac {2057}{2}}=1028.5$

$\cdots$

${\frac {2057}{11}}=187$

${\frac {187}{11}}=17$

hence 11, 11 and 17 are the prime factors of 2057.

Exercise

Factorise the given numbers below

1

13=

2

26=

3

59=

4

82=

5

101=

6

121=

7 Give up if it takes too long. There is a quick way.

2187=

Fun Fact — Is this prime?

Interestingly, there is an efficient way of determining whether a number is prime with 100% accuracy with the help of a computer.

2, 5 and 3

The primes 2, 5, and 3 hold a special place in factorization. Firstly, all even numbers have 2 as one of their prime factors. Secondly, all numbers whose last digit is 0 or 5 can be divided wholly by 5.

The third case, where 3 is a prime factor, is the focus of this section. The underlying question is: is there a simple way to decide whether a number has 3 as one of its prime factors?

Theorem — Divisibility by 3

A number is divisible by 3 if and only if the sum of its digits is divisible by 3

For example, 272 is not divisible by 3, because 2 + 7 + 2 = 11, which is not divisible by 3.

945 is divisible by 3, because 9 + 4 + 5 = 18. And 18 is divisible by 3. In fact 945 / 3 = 315

Is 123456789 divisible by 3?

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = (1 + 9) × 9 / 2 = 45

4 + 5 = 9

Nine is divisible by 3, therefore 45 is divisible by 3, therefore 123456789 is divisible by 3!

The beauty of the theorem lies in its recursive nature. A number is divisible by 3 if and only if the sum of its digits is divisible by 3. How do we know whether the sum of its digits is divisible by 3? Apply the theorem again!

info — Recursion

A prominent computer scientist once said "To iterate is human, to recurse, divine." But what does it mean to recurse? Before that, what is to iterate?
"To iterate" simply means doing the same thing over and over again, and computers are very good at that. An example of iteration in mathematics is the exponential operation, e.g. xⁿ means doing x times x times x times x...n times. That is an example of iteration.

Thinking about iteration economically (in terms of mental resources), by defining a problem in terms of itself, is "to recurse". To recursively represent xⁿ, we write:

$x^{n}=1$ if n equals 0.

$x^{n}=x\times x^{n-1}$ if n > 0

What is 9⁹? It is 9 times 9 ⁸. But, 9⁸ is 9 times 9⁷. Repeating this way is an example of recursion.

Exercises

For questions 1-3, factorize:

1

45=

2

4050=

3

2187=

4 Show that the divisible-by-3 theorem works for any 3 digit number.

(do it on paper)

5 A number is divisible by 9 if and only if the sum of its digits is divisible by 9.

	True
	False

Determine whether the numbers for questions 6-9 are divisible by 9.

6 89

	Yes
	No

7 558

	Yes
	No

8 51858

	Yes
	No

9 41857

	Yes
	No

Finding primes

The prime sieve is a relatively efficient method for finding all primes less than or equal to a specified number. To find all primes less than or equal to 50, we do the following:

First, we write out the numbers 1 to 50 in a table as below

${\begin{matrix}1&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}$

Cross out 1, because it's not a prime.

${\begin{matrix}X&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}$

Now 2 is the smallest number not crossed out in the table. We mark 2 as a prime and cross out all multiples of 2 i.e. 4, 6, 8, 10 ...

${\begin{matrix}X&2_{p}&3&X&5&X&7&X&9&X\\11&X&13&X&15&X&17&X&19&X\\21&X&23&X&25&X&27&X&29&X\\31&X&33&X&35&X&37&X&39&X\\41&X&43&X&45&X&47&X&49&X\\\end{matrix}}$

Now 3 is the smallest number not marked in anyway. We mark 3 as a prime and cross out all multiples of 3 i.e. 6, 9, 12, 15 ...

${\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}$

Continue this way to find all the primes. When do you know you have found all the primes under 50? Note that this algorithm is called Sieve of Eratosthenes

Exercise

1. $${\begin{matrix}X&2&3&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&X&X&X&X&29&X\\31&X&X&X&X&X&37&X&X&X\\41&X&43&X&X&X&47&X&X&X\\\end{matrix}}$$The prime sieve has been applied to the table above. Notice that every number situated directly below 2 and 5 are crossed out. Construct a rectangular grid of numbers running from 1 to 60 so that after the prime sieve has been performed on it, all numbers situated directly below 2 and 5 are crossed out. What is the width of the grid?
2. Find all primes below 200.
3. Find the numbers which are divisible by 3 below 200. Did you change the width of your grid?

Infinitely many primes

To answer the question what is the largest prime number? let us first answer what is the largest natural number? If somebody tells you that $10^{10}$ is the largest natural number, you can immediately prove them wrong by telling them that $10^{10}+1$ is a larger natural number. You can substitute $10^{10}$ with any number other natural number $n$ and your argument will still work. This means that there is no such thing as the largest natural number. (Some of you might be tempted to say that infinity is the largest natural number. However, infinity is not a natural number but just a mathematical concept.)

The ancient Greek mathematician Euclid, had the following proof of the infinitude of primes.

Proof of infinitude of primes

Let us first assume that

there are a finite number of primes

therefore

there must be one prime that is greater than all others,

let this prime be referred to as n. We now proceed to show the two assumptions made above will lead to a contradiction, and thus there are infinitely many primes.

Take the product of all prime numbers to yield a number x. Thus:

$x=2\times 3\times 5\times \ldots \times n\!$

Then, let y equal one more than x:

$y=x+1\!$

One may now conclude that y is not divisible by any of the primes up to n, since y differs from a multiple of each such prime by exactly 1. Since y is not divisible by any prime number, y must either be prime, or its prime factors must all be greater than n, a contradiction of the original assumption that n is the largest prime! Therefore, one must declare the original assumption incorrect, and that there exists an infinite number of primes.

Fun Fact — Largest known prime

The largest known prime is 2^82,589,933-1. It has a whopping 24,862,048 digits! Primes of the form 2ⁿ-1 are called Mersenne primes named after the French monk/amateur mathematician.

Useful Off-site Resources

• "The Prime Pages. Prime Number Research, Records, and Resources"

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.

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains