Discrete Mathematics/Number theory

Introduction

'Number theory' is a large encompassing subject in its own right. Here we will examine the key concepts of number theory.

Unlike real analysis and calculus which deals with the dense set of real numbers, number theory examines mathematics in discrete sets, such as N or Z. If you are unsure about sets, you may wish to revisit Set theory.

Number Theory, the study of the integers, is one of the oldest and richest branches of mathematics. Its basic concepts are those of divisibility, prime numbers, and integer solutions to equations -- all very simple to understand, but immediately giving rise to some of the best known theorems and biggest unsolved problems in mathematics. The Theory of Numbers is also a very interdisciplinary subject. Ideas from combinatorics (the study of counting), algebra, and complex analysis all find their way in, and eventually become essential for understanding parts of number theory. Indeed, the greatest open problem in all mathematics, the Riemann Hypothesis, is deeply tied into Complex Analysis. But never fear, just start right into Elementary Number Theory, one of the warmest invitations to pure mathematics, and one of the most surprising areas of applied mathematics!

Divisibility

Note that in R, Q, and C, we can divide freely, except by zero. This property is often known as closure -- the quotient of two rationals is again a rational, etc.. However, if we move to performing mathematics purely in a set such as Z, we come into difficulty. This is because, in the integers, the result of a division of two integers might not be another integer. For example, we can of course divide 6 by 2 to get 3, but we cannot divide 6 by 5, because the fraction 6/5 is not in the set of integers.

However we can introduce a new relation where division is defined. We call this relation divisibility, and if ${\frac {b}{a}}$ is an integer, we say:

• $a$ divides $b$
• $a$ is a factor of $b$
• $b$ is a multiple of $a$
• $b$ is divisible by $a$

Formally, if there exists an integer $q$ such that $b=qa$ then we say that $a$ divides $b$ and write $a\mid b$. If $a$ does not divide $b$ then we write $a\nmid b$:

Proposition. The following are basic consequences of this definition. Let a, b, and c be integers:

• (a) If a|b then a|(bc).
• (b) If a|b and b|c, then a|c.
• (c) If a|b and a|c, then for any integers x and y, a|(xb+yc) -- in other words a divides any linear combination of its multiples.
• (d) If both a|b and b|a, then a = b or a = -b.
• (e) If c is not 0, then a|b is equivalent to ca|cb.

Quotient and divisor theorem

For any integer n and any k > 0, there is a unique q and r such that:

n = qk + r (with 0 ≤ r < k)

Here n is known as dividend.

We call q the quotient, r the remainder, and k the divisor.

It is probably easier to recognize this as division by the algebraic re-arrangement:

n/k = q + r/k (0 ≤ r/k < 1)

Modular arithmetic

What can we say about the numbers that divide another? Pick the number 8 for example. What is the remainder on dividing 1 by 8? Using the division theorem above

0 = 8*0 + 0

1 = 8*0 + 1

2 = 8*0 + 2

:

8 = 8*1 + 0

9 = 8*1 + 1

10 = 8 * 1 + 2

:

and so on

We have a notation for the remainders, and can write the above equations as

0 mod 8 = 0

1 mod 8 = 1

2 mod 8 = 2

3 mod 8 = 3

4 mod 8 = 4

5 mod 8 = 5

6 mod 8 = 6

7 mod 8 = 7

8 mod 8 = 0

9 mod 8 = 1

10 mod 8 = 2

:

We can also write

1 ≡ 1 (mod 8)

2 ≡ 2 (mod 8)

3 ≡ 3 (mod 8)

4 ≡ 4 (mod 8)

5 ≡ 5 (mod 8)

6 ≡ 6 (mod 8)

7 ≡ 7 (mod 8)

8 ≡ 0 (mod 8)

9 ≡ 1 (mod 8)

10 ≡ 2 (mod 8)

:

These notations are all short for

a = 8k+r for some integer k.

So x ≡ 1 (mod 8), for example, is the same as saying

x = 8k+1

Observe that the remainder here, in comparing it with the division algorithm is 1. x ≡ 1 (mod 8) asks what numbers have the remainder 1 on division by 8? Clearly the solutions are x=8×0+1, 8×1+1,... = 1, 9, ...

Often the entire set of remainders on dividing by n - which we say modulo n - are interesting to look at. We write this set Z_n. Note that this set is finite. The remainder on dividing 9 by 8 is 1 - the same as dividing 1 by 8. So in a sense 9 is really "the same as" 1. In fact, the relation "≡"

x ≡ y iff x mod n = y mod n.

is an equivalence relation. We call this relation congruence. Note that the equivalence classes defined by congruence are precisely the elements of Z_n.

We can find some number a modulo n (or we say a congruent to n) by finding its decomposition using the division algorithm.

Addition, subtraction, and multiplication work in Z_n - for example 3 + 6 (mod 8) = 9 (mod 8) = 1 (mod 8). The numbers do look strange but they follow many normal properties such as commutativity and associativity.

If we have a number greater than n we often reduce it modulo n first - again using the division algorithm. For example if we want to find 11+3 mod 8, its often easier to calculate 3 + 3 (mod 8) rather than reducing 14 mod 8. A trick that's often used is that, say, if we have 6 + 7 (mod 8) we can use negative numbers instead so the problem becomes -2 + -1 = -3 = 5 (mod 8).

We often use the second notation when we want to look at equations involving numbers modulo some n. For example, we may want to find a number x such that

3x ≡ 5 (mod 8)

We can find solutions by trial substitution (going through all the numbers 0 through 7), but what if the moduli are very large? We will look at a more systematic solution later.

Note: we often say that we are working in Z_n and use equals signs throughout. Familiarize yourself with the three ways of writing modular equations and expressions.

The Consistency of Modular Arithmetic

Let $n\geq 2$ denote an arbitrary base. Given an arbitrary integer $x$, the sequence of integers $...,x-2n,x-n,x,x+n,x+2n,...$ are all congruent to each other modulo $n$:

$...\equiv x-2n\equiv x-n\equiv x\equiv x+n\equiv x+2n\equiv ...\;\;({\text{mod}}\;n)$

In modular arithmetic, two integers $x$ and $y$ that are congruent modulo $n$ ($x\equiv y\;\;({\text{mod}}\;n)$) both "represent" the same quantity from $\mathbb {Z} _{n}$. It should be possible to substitute an arbitrary integer $x$ in place of integer $y$ provided that $x\equiv y\;\;({\text{mod}}\;n)$.

This means that:

• Given arbitrary integers $x_{1},x_{2}$ and $y_{1},y_{2}$, if $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$ and $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$, then $x_{1}+y_{1}\equiv x_{2}+y_{2}\;\;({\text{mod}}\;n)$.

Proof

Since $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$, there exists an integer $k_{x}\in \mathbb {Z}$ such that $x_{2}=x_{1}+k_{x}n$.

Since $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$, there exists an integer $k_{y}\in \mathbb {Z}$ such that $y_{2}=y_{1}+k_{y}n$.

It can be derived that $x_{2}+y_{2}=(x_{1}+k_{x}n)+(y_{1}+k_{y}n)=(x_{1}+y_{1})+(k_{x}+k_{y})n$ so therefore $x_{1}+y_{1}\equiv x_{2}+y_{2}\;\;({\text{mod}}\;n)$.

• Given arbitrary integers $x_{1},x_{2}$ and $y_{1},y_{2}$, if $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$ and $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$, then $x_{1}y_{1}\equiv x_{2}y_{2}\;\;({\text{mod}}\;n)$.

Proof

Since $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$, there exists an integer $k_{x}\in \mathbb {Z}$ such that $x_{2}=x_{1}+k_{x}n$.

Since $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$, there exists an integer $k_{y}\in \mathbb {Z}$ such that $y_{2}=y_{1}+k_{y}n$.

It can be derived that $x_{2}y_{2}=(x_{1}+k_{x}n)(y_{1}+k_{y}n)=x_{1}y_{1}+k_{x}y_{1}n+x_{1}k_{y}n+k_{x}k_{y}n^{2}$$=x_{1}y_{1}+(k_{x}y_{1}+x_{1}k_{y}+k_{x}k_{y}n)n$ so therefore $x_{1}y_{1}\equiv x_{2}y_{2}\;\;({\text{mod}}\;n)$.

Number Bases

Converting between various number bases is one of the most tedious processes in mathematics.

The numbers that are generally used in transactions are all in base-10. This means that there are 10 digits that are used to describe a number. These ten digits are {0,1,2,3,4,5,6,7,8,9}.

Similarly, base-4 has 4 digits {0,1,2,3} and base-2 has two digits {0,1}. Base two is sometimes referred to as Binary.

There are also bases greater than 10. For these bases, it is customary to use letters to represent digits greater than 10. An example is Base-16 (Hexadecimal). The digits used in this base are {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}.

In order to convert between number bases, it is critical that one knows how to divide numbers and find remainders.

To convert from decimal to another base one must simply start dividing by the value of the other base, then dividing the result of the first division and overlooking the remainder, and so on until the base is larger than the result (so the result of the division would be a zero). Then the number in the desired base is the remainders read from end to start.

The following shows how to convert a number (105) which is in base-10 into base-2.

Operation	Remainder
105 / 2 = 52	1
52 / 2 = 26	0
26 / 2 = 13	0
13 / 2 = 6	1
6 / 2 = 3	0
3 / 2 = 1	1
1 / 2 = 0	1

Answer : 1101001

After finishing this process, the remainders are taken and placed in a row (from bottom to top) after the final quotient (1101001, in this example) is shown as the base-2 equivalent of the number 105.

To sum up the process, simply take the original number in base 10, and divide that number repeatedly, keeping track of the remainders, until the quotient becomes less than the numerical value of the base.

This works when converting any number from base-10 to any base. If there are any letters in the base digits, then use the letters to replace any remainder greater than 9. For example, writing 11(of base-10) in base 14.

Operation	Remainder
11 / 14 = 0	B (=11)

Answer: B

As 11 is a single remainder, it is written as a single digit. Following the pattern {10=A, 11=B, 12=C...35=Z}, write it as B. If you were to write "11" as the answer, it would be wrong, as "11" Base-14 is equal to 15 in base-10!

In order to convert from a number in any base back to base ten, the following process should be used:

Take the number 3210 (in base-10). In the units place (10⁰), there is a 0. In the tens place (10¹), there is a 1. In the hundreds place (10²), there is a 2. In the thousands place (10³), there is a 3.

The formula to find the value of the above number is:

3×10³ + 2×10² + 1×10¹ + 0×10⁰ = 3000 + 200 + 10 + 0 = 3210.

The process is similar when converting from any base to base-10. For example, take the number 3452 (in base-6). In the units place (6⁰), there is a 2. In the sixths place (6¹) there is a 5. In the thirty-sixths place (6²), there is a 4. In the 216th place (6³), there is a 3.

The formula to find the value of the above number (in base-10) is:

3×6³ + 4×6² + 5×6¹ + 2×6⁰ = 648 + 144 + 30 + 2 = 824.

The value of 3452 (base-6) is 824 in base-10.

A more efficient algorithm is to add the left-most digit and multiply by the base, and repeat with the next digit and so on.

((3 * 6 + 4) * 6 + 5) * 6 + 2 = 824

The processes to convert between number bases may seem difficult at first, but become easy if one practices often.

Prime numbers

Prime numbers are the building blocks of the integers. A prime number is a positive integer greater than one that has only two divisors: 1, and the number itself. For example, 17 is prime because the only positive integers that divide evenly into it are 1 and 17. The number 6 is not a prime since more than two divisors 1, 2, 3, 6 divide 6. Also, note that 1 is not a prime since 1 has only one divisor.

Some prime numbers

The prime numbers as a sequence begin

2, 3, 5, 7, 11, 13, 17, 19, 23, ...

Euclid's Proof that There are Infinitely Many Primes

The Greek mathematician Euclid gave the following elegant proof that there are an infinite number of primes. It relies on the fact that all non-prime numbers --- composites --- have a unique factorization into primes.

Euclid's proof works by contradiction: we will assume that there are a finite number of primes, and show that we can derive a logically contradictory fact.

So here we go. First, we assume that that there are a finite number of primes:

p₁, p₂, ... , p_n

Now consider the number M defined as follows:

M = 1 + p₁ * p₂ * ... * p_n

There are two important --- and ultimately contradictory --- facts about the number M:

1. It cannot be prime because p_n is the biggest prime (by our initial assumption), and M is clearly bigger than p_n. Thus, there must be some prime p that divides M.
2. It is not divisible by any of the numbers p₁, p₂, ..., p_n. Consider what would happen if you tried to divide M by any of the primes in the list p₁, p₂, ... , p_n. From the definition of M, you can tell that you would end up with a remainder of 1. That means that p --- the prime that divides M --- must be bigger than any of p₁, ..., p_n.

Thus, we have shown that M is divisible by a prime p that is not on the finite list of all prime. And so there must be an infinite number of primes.

These two facts imply that M must be divisible by a prime number bigger than p_n. Thus, there cannot be a biggest prime.

Note that this proof does not provide us with a direct way to generate arbitrarily large primes, although it always generates a number which is divisible by a new prime. Suppose we know only one prime: 2. So, our list of primes is simply p₁=2. Then, in the notation of the proof, M=1+2=3. We note that M is prime, so we add 3 to the list. Now, M = 1 +2 *3 = 7. Again, 7 is prime. So we add it to the list. Now, M = 1+2*3*7 = 43: again prime. Continuing in this way one more time, we calculate M = 1+2*3*7*43 = 1807 =13*139. So we see that M is not prime.

Viewed another way: note that while 1+2, 1+2*3, 1+2*3*5, 1+2*3*5*7, and 1+2*3*5*7*11 are prime, 1+2*3*5*7*11*13=30031=59*509 is not.

Testing for primality

There are a number of simple and sophisticated primality tests. We will consider some simple tests here. In upper-level courses we will consider some faster and more sophisticated methods to test whether a number is prime.

Inspection

The most immediate and simple test to eliminate a number n as a prime is to inspect the units digit or the last digit of a number.

If the number n ends in an even number 0, 2, 4, 6, 8 we can show that number n cannot be a prime. For example, take n = 87536 = 8753(10) + 6. Since 10 is divisible by 2 and 6 is divisible by 2 then 87536 must be divisible by 2. In general, any even number can be expressed in the form n = a*10 + b, where b = 0, 2, 4, 6, 8. Since 10 is divisible by 2 and b is divisible by 2 then n = a*10 + b is divisible by 2. Consequently, any number n which ends in an even number such as 7777732 or 8896 is divisible by 2 so n is not a prime.

In a similar type of argument, if a number n ends in a 5 we can show the number n cannot be a prime. If the last digit of n, call it b, is a 5 we can express n in the form n = a*10 + b, where b = 5. Since 10 is divisible by 5 and b = 5 is divisible by 5 then n = a*10 + b is divisible by 5. Hence, any number n which ends in a 5 such as 93475 is divisible by 5 so n is not a prime.

Thus, if a number greater than 5 is a prime it must end with either a 1, 3, 7, or 9. Note that this does not mean all numbers that end in a 1, 3, 7, or 9 are primes. For example, while the numbers 11, 23, 37, 59 are primes, the numbers 21 = 3*7, 33 = 3*11, 27 = 3*9, 39 = 3*13 are not primes. Consequently, if a number ends in a 1, 3, 7, or 9 we have to test further.

Trial Division Method

To test if a number n that ends in a 1, 3, 7, or 9 is prime, we could simply try the smallest prime number and try to divide it in n. If that doesn't divide, we would take the next largest prime number and try again etc. Certainly, if we took all primes numbers in this manner that were less than n and we could not divide n then we would be justified in saying n is prime. However, it can be shown that you don't have to take all primes smaller than n to test if n is prime. We can stop earlier by using the Trial Division Method.

The justification of the Trial Division Method is if a number n has no divisors less than or equal to ${\sqrt {n}}$ then n must be a prime. We can show this by contradiction. Let us assume n has no divisors less than or equal to ${\sqrt {n}}$. If n is not a prime, there must be two numbers a and b such that $a*b=n$. In particular, by our assumption ${\sqrt {n}}<a$ and ${\sqrt {n}}<b$. But then $n={\sqrt {n}}{\sqrt {n}}<a*b=n$. Since a number can not be greater than itself the number n must be a prime.

Trial Division Method is a method of primality testing that involves taking a number n and then sequentially dividing it by primes up to ${\sqrt {n}}$.

For example, is 113 prime? ${\sqrt {113}}$ is approximately 10.63... We only need to test whether 2, 3, 5, 7 divide 113 cleanly (leave no remainder, i.e., the quotient is an integer).

113/2 is not an integer since the last digit is not even.

113/3 (=37.666...) is not an integer.

113/5 is not an integer since the last digit does not end in a 0 or 5.

113/7 (=16.142857...) is not an integer.

So we need not look at any more primes such as 11, 13, 17 etc. less than 113 to test, since 2, 3, 5, 7 does not divide 113 cleanly, 113 is prime.

Notice that after rejecting 2 and 3 as a divisor, we next considered the next prime number 5 and not the next number 4. We know not to consider 4 because we know 2 does not divide 113. If 2 cannot divide 113 then certainly 4 cannot because if 4 divided 113 and since 2 divides 4 then 2 would divide 113. So we only use the next cheapest available prime to test not the next consecutive number.

If we test 91 we get,

91/2 is not an integer since that last digit is not even.

91/3= (30.333) is not an integer.

91/5= is not an integer since the last digit does not end in a 0 or 5.

91/7=13 is an integer

So we know since 7 divides 91, 91 is not a prime.

Trial division is normally only used for relatively small numbers due to its inefficiency. However this technique has the two advantages that firstly once we have tested a number we know for sure that it is prime and secondly if a number is not prime it also gives us the number's factors.

To obtain a few small primes, it may be best to use the Sieve of Eratosthenes than to test each number sequentially using trial division. The Sieve of Eratosthenes method is basically a process of finding primes by elimination. We start by taking a list of consecutive numbers say 1 to 100. Cross out the number 1 because the number is not prime. Take the next least uncrossed off number which is 2 and circle it. Now cross out all multiples of 2 on the list. Next take the next least uncircled number which is 3. Circle the number 3 and cross out all multiples of 3. The next least uncircled number should be 5 since 4 is a multiple of 2 and should have been crossed off. Circle the number 5 and cross out all multiples of 5. The next least uncircled number should be a 7 since 6 is a multiple of 2. Circle the 7 and mark off all multiples of 7. Now the next uncrossed off number should be 11 since 8,9,10 is a multiple of 2, 3, and 2. If we continue in this manner what is left is the circled numbers which are primes. But notice we can actually stop now and circle all the unmarked numbers after crossing off multiples of 7 because of the result that since ${\sqrt {100}}=10$ any number less than 100 which is not prime must be divisible by 2, 3, 5, or 7.

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic is an important theorem relating to the factorization of numbers. The theorem basically states that every positive integer can be written as the product of prime numbers in a unique way (ignoring reordering the product of prime numbers).

In particular, The Fundamental Theorem of Arithmetic means any number such as 1,943,032,663 is either a prime or can be factored into a product of primes. If a number such as 1,943,032,663 can be factored into primes such as 11×13×17×19×23×31×59 it is futile to try to find another different combination of prime numbers that will also give you the same number.

To make the theorem work even for the number 1, we think of 1 as being the product of zero prime numbers.

More formally,

For all n∈N

n=p₁p₂p₃...

where the p_i are all prime numbers, and can be repeated.

Here are some examples.

4 = 2 × 2 = 2²

12 = 2 × 2 × 3 = 2² × 3

11 = 11.

A proof of the Fundamental Theorem of Arithmetic will be given after Bezout's identity has been established.

LCM and GCD

Two characteristics we can determine between two numbers based on their factorizations are the lowest common multiple, the LCM and greatest common divisor, the GCD (also greatest common factor, GCF)

LCM

The lowest common multiple, or the least common multiple, for two numbers a and b is the smallest number designated by LCM(a,b) that is divisible by both the number a and the number b. We can find LCM(a,b) by finding the prime factorization of a and b and choosing the maximum power for each prime factor.

In another words, if the number a factors to $p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{n}^{\alpha _{n}}$, and the number b factors to $p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}\cdots p_{n}^{\beta _{n}}$, then LCM(a,b) = $p_{1}^{\gamma _{1}}p_{2}^{\gamma _{2}}\cdots p_{n}^{\gamma _{n}}$ where $\gamma _{i}=Maximum(\alpha _{i},\beta _{i})$ for i = 1 to n.

An example, let us see the process on how we find lowest common multiple for 5500 and 450 which happens to be 49500. First, we find the prime factorization for 5500 and 450 which is

5500=2² 5³ 11

450=2 3 ² 5²

Notice the different primes we came up for both the number 5500 and the number 450 are 2, 3, 5, and 11. Now let us express 5500 and 450 completely in a product of these primes raised to the appropriate power.

5500=2² 5³ 11 = 2² 3⁰ 5³ 11¹

450=2 3² 5² = 2¹ 3² 5² 11⁰

The LCM(5500,450) is going to be in the form 2^? 3^? 5^? 11^?. All we now have to do is find what the powers of each individual prime will be.

So now we compare the power of each prime for 5500 and 450. Let us consider the powers of the first prime 2. In the number 5500, the prime 2 is raised to the second power and in the number 450, prime 2 is raised to the first power. Since the maximum between 2 and 1 for the power of the prime 2 is 2, we use 2 for the power of the prime 2.

Now let us consider the powers of the prime 3. In the number 5500, the prime 3 is raised to the zero power and in the number 450 the prime 3 is raised to the second power. Since the maximum between 0 and 2 for the power of the prime 3 is 2, we use 2 for the power of the prime 3.

Similarly, let us consider the powers of the next prime 5. In the number 5500, the prime 5 is raised to the third power and in the number 450 the prime 5 is raised to the second power. Since the maximum between 3 and 2 for the power of the prime 5 is 3, we use 3 for the power of the prime 5.

Finally, let us consider the powers of the prime 11, the last prime on our list. In the number 5500, the prime 11 is raised to the first power and in the number 450 the prime 11 is raised to the zero power. Since the maximum between 1 and 0 for the power of the prime 11 is 1, we use 1 for the power of the last prime 11.

Consequently, the product of our results is LCM(5500,450)=2² 3² 5³ 11¹ = 49500.

GCD

The greatest common divisor for two numbers a and b is the biggest number designated by GCD(a,b) that divides both the number a and the number b. In a similar process to finding LCM(a,b), we can find GCD(a,b) by finding the prime factorization of a and b but choosing the minimum power for each prime factor instead.

In other words, if the number a factors to $p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{n}^{\alpha _{n}}$, and the number b factors to $p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}\cdots p_{n}^{\beta _{n}}$, then GCD(a,b) = $p_{1}^{\gamma _{1}}p_{2}^{\gamma _{2}}\cdots p_{n}^{\gamma _{n}}$ where $\gamma _{i}=Minimum(\alpha _{i},\beta _{i})$ for i = 1 to n.

An example, let us see the process on how we find the greatest common divisor for 5500 and 450 which happens to be 50. First, we find the prime factorization for 5500 and 450 which is

5500=2² 5³ 11

450=2 3 ² 5²

Notice the different primes we came up for both the number 5500 and the number 450 are 2, 3, 5, and 11. Now let us express 5500 and 450 completely in a product of these primes raised to the appropriate power.

5500=2² 5³ 11 = 2² 3⁰ 5³ 11¹

450=2 3² 5² = 2¹ 3² 5² 11⁰

The GCD(5500,450) is going to be in the form 2^? 3^? 5^? 11^?. All we now have to do is find what the powers of each individual prime will be.

So now we compare the power of each prime for 5500 and 450. Let us consider the powers of the first prime 2. In the number 5500, the prime 2 is raised to the second power and in the number 4</syntaxhighlight> 50, prime 2 is raised to the first power. Since the minimum between 2 and 1 for the power of the prime 2 is 1, we use 1 for the power of the prime 2.

Now let us consider the powers of the prime 3. In the number 5500, the prime 3 is raised to the zero power and in the number 450 the prime 3 is raised to the second power. Since the minimum between 0 and 2 for the power of the prime 3 is 0, we use 0 for the power of the prime 3.

Similarly, let us consider the powers of the next prime 5. In the number 5500, the prime 5 is raised to the third power and in the number 450 the prime 5 is raised to the second power. Since the minimum between 3 and 2 for the power of the prime 5 is 2, we use 2 for the power of the prime 5.

Finally, let us consider the powers of the prime 11, the last prime on our list. In the number 5500, the prime 11 is raised to the first power and in the number 450 the prime 11 is raised to the zero power. Since the minimum between 1 and 0 for the power of the prime 11 is 0, we use 0 for the power of the last prime 11.

Consequently, the product of our results is GCD(5500,450)=2¹ 3⁰ 5² 11⁰ = 50.

Properties

• gcd(a,b)=gcd(b,a)
• gcd(a,b) = gcd(b,q), where q is the remainder of a divided by b
• gcd(a/d, b/d)=1, where d is gcd(a,b)

The Euclidean algorithm

The Euclidean algorithm is such that we can find the gcd of two numbers without finding the factorization^*. The Euclidean algorithm consists of only addition and multiplication, and uses the above properties of gcd as its basis.

^* Factorization is a "hard" process, that is, to factor a number takes a long time depending on the length of the number. This is why later, when you need to find the gcd of a pair of numbers, you will most likely never factorize the numbers and use the properties of the primes but will use the Euclidean algorithm instead.

An example

We will see how this works by calculating gcd(458,44)

First, divide 458 by 44 and obtain the remainder:

458 = 44 × 10 + 18

Now suppose that a number is a common divisor of 458 and 44. Then it must also be a divisor of 18. To see this, rearrange the above equation to:

458 - 44×10 =18

When this equation is divided by a common divisor of 44 and 458, an integer is obtained on the left, and so must also be obtained on the right. This, by definition, means that the number is also a divisor of 18. By the same reasoning, any common divisor of 18 and 44 is also a divisor of 458. Since all of the common divisors of 458 and 44 are equal to common divisors of 44 and 18, then in particular the greatest common divisors are equal. So we have gcd(458,44)=gcd(44,18)

The next step in the algorithm is to divide 44 by 18 and find the remainder.

44 = 18 × k + r

44 = 18 × 2 + 8

Repeat this process; keep dividing the previous divisor by the previous remainder:

18 = 8 × 2 + 2

8 = 2 × 4 + 0

Our gcd is the last remainder before the zero, in this case, 2. This is because the reasoning that proved gcd(458,44)=gcd(44,18) applies at every step, so gcd(458,44)=gcd(44,18)=gcd(18,8)=gcd(8,2)=gcd(2,0)=2.

The Matrix Method

We can construct a matrix that provides an alternative method for calculating the greatest common divisor. In its general form, the matrix is

${\begin{bmatrix}1&0&b\\0&1&a\\\end{bmatrix}}$

Recall that one way to write the gcd of two numbers is as an integral linear combination. If we are finding the gcd, for example, we could represent it as as + bt, where a and b are the two numbers we are comparing, and s and t are integers. We also know that b = aq + r where r is the remainder upon division of b by a. After we subtract row 2 from row 1, we get

${\begin{bmatrix}1&-q_{1}&r_{1}\\0&1&a\\\end{bmatrix}}$

If r_2 is nonzero, we must continue the process; this time, subtracting row 1 from row 2. We continue this process until one of the r's has been reduced as far as possible. We now have our gcd. The numbers that are in that row, where the 1 and the 0 used to be, represent t and s, respectively.

Let us now look at a computational example.

${\begin{bmatrix}1&0&99\\0&1&7\\\end{bmatrix}}\rightsquigarrow {\begin{bmatrix}1&0&99\\0&14&98\\\end{bmatrix}}\rightsquigarrow {\begin{bmatrix}1&-14&1\\0&14&98\\\end{bmatrix}}$

We see that it would be trivial at this point to go any further; we would just end up with row-2 containing a zero where a used to be. So we look at row-1 and remember that the 1 represents our remainder, 1(=t) multiplies b and -14(=s) multiplies a such that

$1=99\times 1+-14\times 7$

This can be checked by the Euclidean algorithm that gcd(7,99)=1.

The extended Euclidean algorithm

What happens if we try and reverse the process of the Euclidean algorithm by substituting back? Back-substitution is rather tedious and prone to error, so here is a faster method.

Draw up a table with four columns, label these from left to right q, r, u, v. For convenience label a column i representing the step we're currently up to. Place a and b with the greater of these on top in the column r, and place 1s and 0s accordingly:

${\begin{matrix}i&q&r&u&v\\-1&.&b&0&1\\0&.&a&1&0\\\end{matrix}}$

Now iterate downwards by taking the quotient of b/a and putting it in the next space in the q column, then of b-aq in the r column.

To update u and v, take

u_i = u_i-2-u_i-1q_i

v_i = v_i-2-v_i-1q_i

Indeed, you are looking for u and v such that au + bv = gcd (a,b). At some point, gcd (a,b) is in fact the remainder at the ith stage, so you might as well compute u_i and v_i such that au_i + bv_i = r_i, at EACH stage.

Deriving the recurrences found above results from these three equations (the second equation is Euclid's algorithm's basic property, the other two are constraints we set to attain our desired goal):

au_i-1 + bv_i-1 = r_i-1

r_i-2 = q_ir_i-1 + r_i

au_i + bv_i = r_i

The trick is to then appropriately express r_i-2.

Stop writing when you obtain a 0 in the r column.

Finding then, gcd(450,44) (this is the same as gcd(44,450) )

${\begin{matrix}i&q&r&u&v\\-1&.&450&0&1\\0&.&44&1&0\\1&10&10&-10&1\\2&4&4&41&-4\\3&2&\mathbf {2} &-92&9\\4&2&0&-&-\\\end{matrix}}$

The bold number is the gcd. Observe (9)×450+(-92)×44=2 Clearly these u and v are very special. What can we say about the general case?

Bezout's identity

In the above case we have 9×450+(-92)×44=gcd(450,44). So the greatest common divisor of 450 and 44 can be written as a linear combination of 450 and 44 with integer coefficients. This turns out to be true of any pair of integers. This result is known as "Bezout's Identity" and can be stated as follows:

For any pair of nonzero integers, a and b, there exists integers u and v such that

au+bv=gcd(a,b)

Proof

If a and b are any pair of integers, not both 0, then clearly there exist integers u and v such that au+bv is positive (just match the signs of u and v to those of a and b, respectively, for instance), and for all integer u and v, au+bv is also an integer (because the integers are closed under addition and multiplication). So there is a non-empty set of positive integers consisting of numbers of the form au+bv; call it S. Since S is a non-empty set of positive integers, it must have a smallest element (this is the so called Well-ordering principle). Call this number d. The claim is that $d=gcd(a,b)$. Since d belongs to S, then

(1)$d=ua+vb$

for suitable u and v. Let n be any positive common divisor of a and b. Since n divides the right side of (1), it also divides d. So $d=qn$ for some integer $q\geq 1$. So any common divisor of a and b is less than or equal to d. Therefore, if d is a common divisor of a and b, it is the greatest one. It only remains to show that d is in fact a common divisor.

To prove this, it will be shown that any element of S is divisible by d. This will prove that d is a common divisor of a and b because a and b are both elements of S (because a = 1×a + 0×b and b = 0×a + 1×b). Let t be any element of S. Then, by the division algorithm

$t=qd+r$

for some $0\leq r<d$. If r is not 0, then it is in S. This is because d and t are in S, so

$r=t-qd=(u_{1}a+v_{1}b)-q(u_{2}a+v_{2}b)=(u_{1}-qu_{2})a+(v_{1}-qv_{2})b=u'a+v'b$

But, since $r<d$ and d is the least element of S, this is impossible. The only other possibility is that r=0. Therefore any element, t, of S is divisible by d. Since this includes both a and b, d is a common divisor. Combining this with the previous result establishes Bezout's Identity.

The numbers u and v can either be obtained using the tabular methods or back-substitution in the Euclidean Algorithm.

Proof of the Fundamental Theorem of Arithmetic

One use of Bezout's identity is in a proof of the Fundamental Theorem of Arithmetic. Before this is proven, two other results are needed: Lemma 1: If a prime number, p, divides a product of two integers, $ab$, then it must divide a or b (or both).

Proof: If p divides both a and b, there is nothing to prove. Assume p does not divide a. If it can be proven under that assumption that p does divide b, the lemma will be proven.

Since p does not divide a, then gcd(a,p)=1 (because the only divisors of p are 1 and p, but p is not a common divisor). Therefore, by Bezout's Identity, there exist integers u and v such that

$1=ua+vp$

Multiply this equation by b to obtain:

$b=uab+vbp$

p divides both terms on the right hand side and, therefore, divides the left hand side. Hence, p divides b, as was to be shown.

Lemma 2: If a prime number, p, divides a product of integers, $a_{1}a_{2}...a_{n}$, then it must divide at least one of the factors.

Proof: The proof is by induction on n, the number of factors. The statement is true for n=2, by Lemma 1. Assume the statement is true for n=k and consider a product of k+1 factors. If p divides more than one of the factors, once again there is nothing to prove. Assume that p does not divide any of the factors $a_{1},a_{2},...a_{k}$. It will be shown that p must divide $a_{k+1}$. Since the statement is true for n=k, then since p does not divide any of the factors in $a_{1}a_{2}...a_{k}$, it must not divide the product (by Contrapositive). Let $a_{1}a_{2}...a_{k}=b$. Then $a_{1}a_{2}...a_{k}a_{k+1}=ba_{k+1}$. The conclusion then follows by Lemma 1.

Fundamental Theorem of Arithmetic: Any positive integer, n, can be expressed as a product of primes. This product is unique up to the order in which the terms appear.

Proof: The proof of the first part of the theorem is by induction on n. If n=1, it is the product of 0 primes. Assume all positive integers less than n can be expressed as a product of primes. If n is prime, then it is the product of 1 prime. Assume n is not prime or 1. Then $n=ab$,for some positive integers a and b both less than n. Since a and b are both less than n, they can be written as a product of primes by the induciton hypothesis. Combining these products gives n as a product of primes as required.

Now to prove the second part. Assume there are two prime factorizations of n,

$n=p_{1}p_{2}...p_{k}=q_{1}q_{2}...q_{s}$

$p_{1}$ divides the left side and so must also divide the right side. By Lemma 2, this means that $p_{1}$ must divide one of the $q_{i}$. But these are all prime, so the only way $p_{1}$ can divide $q_{i}$ is if $p_{1}=q_{i}$ for some i. Canceling $p_{1}$ from both sides of the equation forms another equation of the same form. So it can likewise be proven that $p_{2}=q_{i}$ for some other i, and so on until all the factors on the left are exhausted. After this, there must not be any factors remaining on the right side since it must equal 1. This proves that any two prime factorizations consist of the same prime factors, as was to be shown.

Partitioning the Divisors of Products

The Fundamental Theorem of Arithmetic can also be derived from the following lemma:

Lemma: Given integers $a$, $b$, and $c$, if $c$ divides $ab$ (denoted by $c|ab$), then there exist integers $m$ and $n$ such that $c=mn$ and $m|a$ and $n|b$.

In other words, an integer that divides a product can itself be factored into a product where each factor divides the corresponding factor from $ab$. This means that no new primes are "created" when $a$ and $b$ are multiplied together.

This Lemma follows from the Fundamental Theorem of Arithmetic and Bezout's identity, but here a more direct proof will be given.

Proof: If any of $a$, $b$, or $c$ is $0$, then the Lemma is trivial. In addition, if any of $a$, $b$, or $c$ is negative, then if the Lemma holds for the absolute values $|a|$, $|b|$, and $|c|$, then it is trivial to show that the Lemma holds for $a$, $b$, and $c$. It will now be assumed that $a$, $b$, and $c$ are all strictly positive integers.

Form an $a\times b$ array $S$ of integers that has $a$ columns and $b$ rows. $s_{(x,y)}$ will denote the integer at column $x$ and row $y$. Fill the array by sweeping the array row by row starting with row 1, with each row swept starting from column 1. During this "raster" sweep of $S$, assign values to $s_{(x,y)}$ using the following cyclical pattern: $1,2,...,c$. In essence, $s_{(x,y)}$ is the unique integer from the range $\{1,2,\dots ,c\}$ such that $s_{(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$. Since $c|ab$, it is the case that $s_{(1,1)}=1$ and $s_{(a,b)}=c$.

As previously indicated, the "raster sweep" through array $S$ is a cyclical progression through the entries of $S$ where column index $x$ cycles around $1,2,...,a$, and every time $x$ transitions from $a$ to $1$, row index $y$ advances by one step around the cycle $1,2,...,b$.

In the image below, the grid $S$ where $a=14$; $b=15$; and $c=6$ is depicted both explicitly and using a brickwork pattern.

Array $S$ can be endlessly replicated and used to form the infinite array $S_{\infty }$. For arbitrary integers $u$ and $v$, the block of entries in $S_{\infty }$ formed by columns $a(u-1)+1$ to $a(u-1)+a$ and rows $(b(v-1)-(u-1))+1$ to $(b(v-1)-(u-1))+b$ is a copy of $S$. For arbitrary integers $x$ and $y$, the entry $s_{\infty ,(x,y)}$ of $S_{\infty }$ is the unique integer from the range $\{1,2,\dots ,c\}$ such that $s_{\infty ,(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$.

A depiction of array S where a = 14; b = 15; and c = 6. The (1,1) entry is the lower-left corner.

A brickwork pattern depicting array S where a = 14; b = 15; and c = 6. Each "brick" is the sequence 1, 2, 3, 4, 5, 6.

Multiple instances of the brickwork pattern that depicts $S$ can be stitched together to form a continuous wall that depicts $S_{\infty }$.

Given any column $x$ and row $y$, the entry $s_{\infty ,(x,y)}$ of $S_{\infty }$ located at $(x,y)$ is the unique integer from $\{1,2,...,c\}$ such that $s_{\infty ,(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$. Given an arbitrary displacement column displacement $\Delta x$ and row displacement $\Delta y$, the difference $s_{\infty ,(x+\Delta x,y+\Delta y)}-s_{\infty ,(x,y)}$ is separated from $\Delta x+a\Delta y$ by a multiple of $c$. This gives the entries of $S_{\infty }$ the following symmetries:

• Given column displacement $\Delta x$ and columns $x_{1},x_{2}$, and row displacement $\Delta y$ and rows $y_{1},y_{2}$, then $s_{\infty ,(x_{1}+\Delta x,y_{1}+\Delta y)}-s_{\infty ,(x_{1},y_{1})}\equiv s_{\infty ,(x_{2}+\Delta x,y_{2}+\Delta y)}-s_{\infty ,(x_{2},y_{2})}\;\;({\text{mod}}\;c)$. Specifically if $s_{\infty ,(x_{1}+\Delta x,y_{1}+\Delta y)}-s_{\infty ,(x_{1},y_{1})}=0$ then $s_{\infty ,(x_{2}+\Delta x,y_{2}+\Delta y)}-s_{\infty ,(x_{2},y_{2})}=0$ since the difference between any two entries of $S_{\infty }$ is confined to the set $\{-(c-1),-(c-2),...,-1,0,1,...,c-1\}$.
• Given columns $x_{1},x_{2}$, and rows $y_{1},y_{2}$, if $s_{\infty ,(x_{1},y_{1})}=s_{\infty ,(x_{2},y_{2})}$, then shifting $S_{\infty }$ by $x_{2}-x_{1}$ columns and $y_{2}-y_{1}$ rows does not change the entries of $S_{\infty }$.

The columns of $S_{\infty }$ that contain $1$ are spaced evenly due to the aforementioned symmetry. Let $m$ denote the smallest positive integer such that every $m^{\text{th}}$ column contains $1$.

• The entries $s_{\infty ,(1,1)}=1$ and $s_{\infty ,(a+1,b)}=1$ so it must be the case that $a$ is an integer multiple of the period $m$: $m|a$.
• The entries $s_{\infty ,(1,1)}=1$ and $s_{\infty ,(c+1,1)}=1$ so it must be the case that $c$ is an integer multiple of the period $m$: $m|c$.

The rows of $S_{\infty }$ eventually repeat (not allowing any column shifts) with a period of $n$. A row does not appear twice in a single cycle due to the symmetry of $S_{\infty }$. Row $1$ is identical to row $b+1$ so it must be the case that $b$ is an integer multiple of the period $n$: $n|b$.

When a=14; b=15; and c=6, it is the case that m=2 and n=3. Any 2x3 cell will contain all of {1, 2, 3, 4, 5, 6} enabling the depicted tiling.

It will now be proven that $c=mn$ by showing that a sub-block of $S_{\infty }$ that consists of $m$ columns and $n$ rows contains every integer from $\{1,2,...,c\}$ exactly once.

To clarify notation, given the column indices $x_{1},x_{2}$ where $x_{1}\leq x_{2}$, and the row indices $y_{1},y_{2}$ where $y_{1}\leq y_{2}$, then $S_{\infty }([x_{1},x_{2}]\times [y_{1},y_{2}])$ will denote the sub-block of $S_{\infty }$ consisting of columns $x_{1}$ through to $x_{2}$, and rows $y_{1}$ through to $y_{2}$.

Since a row can be uniquely determined from a single cell and the rows only repeat with a period of $n$, any block $S_{\infty }([x,x]\times [y,y+(n-1)])$ will contain exactly $n$ unique entries.

Columns that contain $1$ occur with a period of $m$. Due to the symmetry of $S_{\infty }$, given any integer $s\in \{1,2,...,c\}$, columns that contain $s$ occur with a period of $m$. Any block $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ will contain exactly $mn$ unique entries.

Given any integer $s\in \{1,2,...,c\}$, integer $s$ will occur in every $m^{\text{th}}$ column, and within that column, in every $n^{\text{th}}$ cell. Any block $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ will contain $s$. Any block $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ will contain every integer from $\{1,2,...,c\}$ exactly once. So therefore $c=mn$. $\Box$.

Solving linear modular equations - back to Bezout

Bezout's identity above provides us with the key to solving equations in the form

ax ≡ b (mod m)

Coprime case - gcd(a, m) is 1

Consider the case where

ax ≡ b (mod m)

but with gcd(a, m)=1

Because of Bezout's identity

1 = au+mv

When we calculate u, this number is special.

Say if we have the equation

4x=11 (mod 21)

4 and 21 are coprime since gcd(4,21)=1. Now 1=4*16+(-3)*(21). Our u in this case is 16. Observe now that 4*16=64. 64 (mod 21) = 1. This number u is very special - it is known as the multiplicative inverse. It is the number u on multiplication by a gives 1 mod m. Bezout's identity on calculating gcd(a, m) will always give you the multiplicative inverse of a modulo m. The multiplicative inverse of a is often written a^-1 but note that this does not mean 1/a since we have seen in the first sections that we can not always divide in the integers.

Note that in Z_p there is one number without a multiplicative inverse - 0. It may be useful to exclude 0 when considering modular arithmetic, so instead of having to say Z_p\{0} all the time, we merely write Z_p^*.

Now since we have the magic multiplicative inverse, our problem becomes relatively easy to solve. 4^-1=16 in Z₂₁ and now, on multiplying throughout by 16

x = 11 × 16 (mod 21)

(since 4×16=1 because 16 is 4's multiplicative inverse mod 21). 11×16=176 and using a calculator or using the division theorem we obtain

x = 8 (mod 21)

which is our solution! Verify - 8×4 = 32 = 11 (mod 21).

The general case

Consider the general case where

ax ≡ b (mod m)

with no restrictions on a, b and m.

Firstly we calculate gcd(a, m) again to obtain d. Now d is a divisor since the d in gcd means greatest common divisor. So we can now divide a and m - but what about b? Since we have calculated the gcd of a and m but not b we have no guarantees that d will divide b. This then becomes a condition that the equation has no solution.

Now we have reduced the problem to the previous coprime case because gcd(a/d, m/d)=1 with d as above. However we do not have 1 solution any more - this is true because we have reduced the solution to being x = c (mod m/d) and we must bring the solution back mod m. This will be come clearer in the examples.

Let's work through some examples.

Example 1. Solve 4x ≡ 3 (mod 20). Firstly, gcd(4, 20) = 4. 4 does not divide 3 and we have no solution.

Example 2. Solve 9x ≡ 6 (mod 15). gcd(9, 15) = 3 and 3 does divide 6 and we have 3 solutions.

Now, divide through by 3 to obtain

3x ≡ 2 (mod 5)

gcd(3, 5) = 1 = 3 × 2 + -1 × 5 So the inverse of 3 mod 5 is 2. Now we obtain the solution

x ≡ 4 (mod 5)

Now in Z₁₅ we must obtain the two extra solutions 9 and 14 mod 15 - 9 mod 5 = 4 and 14 mod 5 = 4.

Generally we can say that if we have the solution to the reduced equation x, the general solution is x+(m/d)k for k={0, 1, .., d-1}.

Chinese Remainder Theorem

Very often congruence relations are required to hold simultaneously. Given positive integer bases $m_{1}$ and $m_{2}$ and arbitrary integers $a$ and $b$ where $0\leq a<m_{1}$ and $0\leq b<m_{2}$, a common question is what integers $x$ satisfy the following congruence relations simultaneously:

$\left\{{\begin{array}{c}x\equiv a\;\;({\text{mod}}\;m_{1})\\x\equiv b\;\;({\text{mod}}\;m_{2})\end{array}}\right.$

The Chinese Remainder Theorem dictates that when ${\text{gcd}}(m_{1},m_{2})=1$, for any choice of $a\in \mathbb {Z} _{m_{1}}=\{0,1,...,m_{1}-1\}$ and $b\in \mathbb {Z} _{m_{2}}=\{0,1,...,m_{2}-1\}$ there exists a unique integer $c\in \mathbb {Z} _{m_{1}m_{2}}=\{0,1,...,m_{1}m_{2}-1\}$ such that:

the only integers $x$ that satisfy $\left\{{\begin{array}{c}x\equiv a\;\;({\text{mod}}\;m_{1})\\x\equiv b\;\;({\text{mod}}\;m_{2})\end{array}}\right.$ simultaneously are those that satisfy $x\equiv c\;\;({\text{mod}}\;m_{1}m_{2})$

In essence, when $m_{1}$ and $m_{2}$ are coprime, there is a 1-to-1 correspondence between ordered pairs from $\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ and the set $\mathbb {Z} _{m_{1}m_{2}}$.

Proof 1

Proof: To begin, observe that $|\mathbb {Z} _{m_{1}m_{2}}|=m_{1}m_{2}$ and $|\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}|=|\mathbb {Z} _{m_{1}}||\mathbb {Z} _{m_{2}}|=m_{1}m_{2}$ so it is possible to pair each $c\in \mathbb {Z} _{m_{1}m_{2}}$ with a unique ordered pair $\langle a,b\rangle \in \mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ and vice-versa.

Given any $c\in \mathbb {Z} _{m_{1}m_{2}}$, integer $c$ can be reduced modulo $m_{1}$ to get an integer $a\in \mathbb {Z} _{m_{1}}$, and can be reduced modulo $b$ to get an integer $b\in \mathbb {Z} _{m_{2}}$. Integers $a$ and $b$ satisfy: $\forall x\in \mathbb {Z} :(x\equiv c\;\;({\text{mod}}\;m_{1}m_{2}))\implies ((x\equiv a\;\;({\text{mod}}\;m_{1}))\;{\text{and}}\;(x\equiv b\;\;({\text{mod}}\;m_{2})))$

It is not obvious that for any choice of $\langle a,b\rangle \in \mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ that there exists a unique $c\in \mathbb {Z} _{m_{1}m_{2}}$ such that $\forall x\in \mathbb {Z} :((x\equiv a\;\;({\text{mod}}\;m_{1}))\;{\text{and}}\;(x\equiv b\;\;({\text{mod}}\;m_{2})))\iff (x\equiv c\;\;({\text{mod}}\;m_{1}m_{2}))$

Let $S$ denote an infinite array with two rows indexed by $y=1,2$, and an infinite number of columns indexed by $x\in \mathbb {Z}$. $s_{(x,y)}$ will denote the entry of $S$ at column $x$ and row $y$. $s_{(x,y)}$ is the unique integer from $\mathbb {Z} _{y}=\{0,1,...,m_{y}-1\}$ where $s_{(x,y)}\equiv x\;\;({\text{mod}}\;m_{y})$.

Array $S$ where $m_{1}=6$ and $m_{2}=5$. Columns $x=0$ through to $x=29$ are shown.

Given column indices $x_{1},x_{2}$ where $x_{1}\leq x_{2}$, then $S_{1}[x_{1},x_{2}];S_{2}[x_{1},x_{2}];S_{1,2}[x_{1},x_{2}]$ will respectively denote the sub-blocks formed by columns $x_{1}$ through to $x_{2}$ and row sets $\{1\};\{2\};\{1,2\}$.

Partition $S$ into the series of $m_{1}\times 2$ blocks $...,S_{1,2}[-2m_{1},-m_{1}-1],S_{1,2}[-m_{1},-1],S_{1,2}[0,m_{1}-1],S_{1,2}[m_{1},2m_{1}-1],S_{1,2}[2m_{1},3m_{1}-1],...$ where block $k\in \mathbb {Z}$ is $S_{1,2}[km_{1},(k+1)m_{1}-1]$.

Row 1 of block $k$ will always be the sequence $0,1,...,m_{1}-1$. Row 2 of block $k$ can be uniquely determined by its first entry, $s_{(km_{1},2)}$ since $s_{(km_{1}+r,2)}\equiv s_{(km_{1},2)}+r\;\;({\text{mod}}\;m_{2})$. The blocks only differ by row 2, and row 2 for each block is uniquely determined by its first entry $s_{(km_{1},2)}$.

$s_{(km_{1},2)}\equiv km_{1}\;\;({\text{mod}}\;m_{2})$ and $s_{((k+1)m_{1},2)}\equiv (k+1)m_{1}\;\;({\text{mod}}\;m_{2})$ so $s_{((k+1)m_{1},2)}\equiv s_{(km_{1},2)}+m_{1}\;\;({\text{mod}}\;m_{2})$. This implies that the first entry of row 2 for the next block can be uniquely determined from the first entry of row 2 for the current block.

Since each block is uniquely determined from the previous block, the row 2 pattern for each block will repeat after a regular period of $p$ blocks: $S_{1,2}[km_{1},(k+1)m_{1}-1]=S_{1,2}[(k+p)m_{1},(k+p+1)m_{1}-1]$. Let set $U\subseteq \mathbb {Z} _{m_{2}}$ denote the total range of values attained by $s_{(km_{1},2)}$. It is the case that $p=|U|$. Let $d$ be the minimum positive difference between any two elements from $U$. The cyclical nature of the elements from $U$ makes it easy to show that any element $t\in U$ is congruent to a multiple of $d$ modulo $m_{2}$. In essence: $U=\{t|t\in \mathbb {Z} _{m_{2}}\;{\text{and}}\;\exists u\in \mathbb {Z} :t\equiv ud\;\;({\text{mod}}\;m_{2})\}$. Since $d$ is the minimum positive difference between any two elements of $U$, both $m_{1}$ and $m_{2}$ are multiples of $d$ (in fact, $m_{2}=pd$). Since ${\text{gcd}}(m_{1},m_{2})=1$, it must be the case that $d=1$. This implies that $U=\mathbb {Z} _{m_{2}}$ and that $p=m_{2}$. A total of $m_{2}$ blocks are encountered before any repetition occurs in array $S$, and therefore all $m_{1}m_{2}$ possible columns occur exactly once in a column period of $m_{1}m_{2}$ in array $S$. This establishes the Chinese Remainder Theorem. $\Box$

Proof 2

A second (more intuitive) proof can be derived by constructing a mesh to depict the space $\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$. This mesh is a rectangular array of points with $m_{1}$ columns and $m_{2}$ rows. The columns are indexed from left to right by $0,1,2,...,m_{1}-1$, and the rows are indexed from bottom to top by $0,1,2,...,m_{2}-1$. Most importantly, the mesh will "wrap around" in the horizontal and vertical dimensions. This means that moving to the right from column $m_{1}-1$ will return you to column $0$; moving to the left from column $0$ will send you to column $m_{1}-1$; moving up from row $m_{2}-1$ will return you to row $0$; and moving down from row $0$ will send you to row $m_{2}-1$.

The mesh has $m_{1}m_{2}$ points, and the horizontal and vertical coordinates of each point are the remainders from dividing an integer $x$ by $m_{1}$ and $m_{2}$ respectively. For convenience, given an arbitrary dividend $x$, $x\;{\text{mod}}\;m_{1}$ and $x\;{\text{mod}}\;m_{2}$ will denote the remainders after $x$ is divided by $m_{1}$ and $m_{2}$ respectively. If the dividend $x$ is incremented by $1$, then the coordinate formed by the remainders moves to the right by one step, and up by one step, wrapping around if necessary. $x=0$ corresponds to the coordinate $(0,0)$. Increasing $x$ in steps of $1$ will trace a ray that originates from $(0,0)$ and moves one step to the right and one step up each interation, wrapping around if necessary. The images below give examples of this ray for $m_{1}=6;m_{2}=5$ and for $m_{1}=6;m_{2}=4$. In the images below, a copy of column 0 and row 0 appears at the right and top of the mesh respectively to illustrate the wrap around property. When $m_{1}=6;m_{2}=4$, $m_{1}$ and $m_{2}$ are not coprime and fail to satisfy the conditions of the Chinese remainder theorem.

A mesh that wraps around horizontally every 6 steps and wraps around vertically every 5 steps is shown. This mesh depicts the set of remainder pairs resulting from division by 6 and 5 respectively. The numbers outside the mesh denote the horizontal and vertical coordinates, which are the respective remainders from dividing by 6 and 5. Starting from (0,0), a ray, denoted by the red line, is emitted that repeatedly transitions forward 1 step in both the horizontal and vertical directions. This ray denotes the sequence of remainder pairs as the dividend increases by steps of 1. The numbers on each red stripe index each wrap around of the ray. The ray passes through every point on the mesh, indicating that any pair of remainders is possible, as predicted by the Chinese remainder theorem.

A mesh that wraps around horizontally every 6 steps and wraps around vertically every 4 steps is shown. This mesh depicts the set of remainder pairs resulting from division by 6 and 4 respectively. The numbers outside the mesh denote the horizontal and vertical coordinates, which are the respective remainders from dividing by 6 and 4. Starting from (0,0), a ray, denoted by the red line, is emitted that repeatedly transitions forward 1 step in both the horizontal and vertical directions. This ray denotes the sequence of remainder pairs as the dividend increases by steps of 1. The numbers on each red stripe index each wrap around of the ray. The ray fails to pass through every point on the mesh, as 6 and 4 are not coprime. This is consistent with the Chinese remainder theorem.

The ray forms diagonal "stripes" in the mesh, and if these stripes are all equally spaced by $1$, then the ray passes through every point in the mesh exactly once proving that every remainder pair is possible and hence the Chinese remainder theorem. When $m_{1}=6;m_{2}=4$, $m_{1}$ and $m_{2}$ are not coprime and fail to satisfy the conditions of the Chinese remainder theorem, hence the ray does not hit every mesh point. The wrap around property of the mesh makes the mesh "symmetric" in both the horizontal and vertical dimensions, which means that if the wrap around "seams" were moved to any column and row where the ray passes through the lower left corner, then the ray is completely unchanged. This requires that the stripes be equally spaced. Let $d$ denote this equal spacing, and it will be shown that $d|m_{1}$ and $d|m_{2}$. The ray passes through row $0$ every $d$ steps to the right. The ray passes through $(0,0)$, and the wrap around property implies that moving $m_{1}$ steps to the right returns to this same intersection point. This can only occur if $d|m_{1}$. By a similar argument $d|m_{2}$. If $m_{1}$ and $m_{2}$ are coprime, then $d=1$, the stripes are evenly spaced by $1$, every remainder pair is possible, and the Chinese remainder theorem is therefore true. $\Box$