Discrete Mathematics/Number theory

From Wikibooks, open books for an open world
< Discrete Mathematics
Jump to: navigation, search

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

Introduction[edit]

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[edit]

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[edit]

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

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


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[edit]

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 Zn. 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 "≡"

xy 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 Zn.

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 Zn - 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 Zn and use equals signs throughout. Familiarize yourself with the three ways of writing modular equations and expressions.

Number Bases[edit]

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 (100), there is a 0. In the tens place (101), there is a 1. In the hundreds place (102), there is a 2. In the thousands place (103), there is a 3.

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

3×103 + 2×102 + 1×101 + 0×100 = 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 (60), there is a 2. In the sixths place (61) there is a 5. In the thirty-sixths place (62), there is a 4. In the 216th place (63), there is a 3.

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

3×63 + 4×62 + 5×61 + 2×60 = 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[edit]

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 divsors 1, 2, 3, 6 divide 6. Also, note that 1 is not a prime since 1 has only one divisor.

Some prime numbers[edit]

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[edit]

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:

p1, p2, ... , pn

Now consider the number M defined as follows:

M = 1 + p1 * p2 * ... * pn

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

  1. It cannot be prime because pn is the biggest prime (by our initial assumption), and M is clearly bigger than pn. Thus, there must be some prime p that divides M.
  2. It is not divisible by any of the numbers p1, p2, ..., pn. Consider what would happen if you tried to divide M by any of the primes in the list p1, p2, ... , pn. 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 p1, ..., pn.

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 pn. 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 p1=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[edit]

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[edit]

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[edit]

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[edit]

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 nN
n=p1p2p3...
where the pi are all prime numbers, and can be repeated.

Here are some examples.

4 = 2 × 2 = 22
12 = 2 × 2 × 3 = 22 × 3
11 = 11.

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

LCM and GCD[edit]

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[edit]

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=22 53 11
450=2 3 2 52

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=22 53 11 = 22 30 53 111
450=2 32 52 = 21 32 52 110

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)=22 32 53 111 = 49500.

GCD[edit]

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=22 53 11
450=2 3 2 52

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=22 53 11 = 22 30 53 111
450=2 32 52 = 21 32 52 110

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)=21 30 52 110 = 50.

Properties[edit]

  • 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[edit]

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[edit]

We will see how this works by calculating gcd(11,17)

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[edit]

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[edit]

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

ui = ui-2-ui-1qi
vi = vi-2-vi-1qi

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 ui and vi such that aui + bvi = ri, 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):

aui-1 + bvi-1 = ri-1
ri-2 = qiri-1 + ri
aui + bvi = ri

The trick is to then appropriately express ri-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[edit]

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, respectivly, 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 andb = 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_1a+v_1b)-q(u_2a+v_2b)=(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 backsubstitution in the Euclidean Algorithm.

Proof of the Fundamental Theorem of Arithmetic[edit]

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_1a_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_1a_2...a_k, it must not divive the product (by Contrapositive). Let a_1a_2...a_k=b. Then a_1a_2...a_ka_{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_1p_2...p_k=q_1q_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.

Solving linear modular equations - back to Bezout[edit]

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

axb (mod m)

Coprime case - gcd(a, m) is 1[edit]

Consider the case where

axb (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 Zp 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 Zp\{0} all the time, we merely write Zp*.

Now since we have the magic multiplicative inverse, our problem becomes relatively easy to solve. 4-1=16 in Z21 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[edit]

Consider the general case where

axb (mod m)

with no restrictions on a, b and m.

Firstly we calculate

gcd[edit]

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 Z15 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}.