# High School Mathematics Extensions/Print Version

Note: current version of this book can be found at http://en.wikibooks.org/wiki/High_school_extensions"

Remember to click "refresh" to view this version.

Note: this file appears to be too large to be rendered in a "print version". ) to cut the file into two halves if creating an export file for PDF Creation -->

# Primes and modular arithmetic

## Primes

Content HSME Primes Modular Arithmetic Problem Set Project Exercise Solutions Problem Set Solutions Definition Sheet Full Version PDF Version

## Introduction

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

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

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

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

### Geometric meaning of primes

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

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

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

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

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

### Fundamental Theorem of Arithmetic

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

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

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

For example

${\displaystyle 12=2\times 2\times 3\,\!}$

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

A few more examples

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

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

Why?

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

## Factorization

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

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

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

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

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

Example 1

${\displaystyle x=21}$
${\displaystyle {\frac {x}{2}}=10.5}$ not a whole number, so 2 is not a factor of 21
${\displaystyle {\frac {x}{3}}=7}$ hence 3 and 7 are the factors of 21.

Example 2

${\displaystyle x=153}$
${\displaystyle {\frac {x}{2}}=76.5}$ hence 2 is not a factor of 153
${\displaystyle {\frac {x}{3}}=51}$ hence 3 and 51 are factors of 153
${\displaystyle {\frac {51}{3}}=17}$ hence 3 and 17 are factors of 153

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

Example 3

${\displaystyle {\frac {2057}{2}}=1028.5}$
${\displaystyle \cdots }$
${\displaystyle {\frac {2057}{11}}=187}$
${\displaystyle {\frac {187}{11}}=17}$
hence 11, 11 and 17 are the prime factors of 2057.

### Exercise

Factor the following numbers:

1. 13
2. 26
3. 59
4. 82
5. 101
6. 121
7. 2187 Give up if it takes too long. There is a quick way.

### Fun Fact — Is this prime?

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

## 2, 5 and 3

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

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

## Theorem — Divisibility by 3

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

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

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

Is 123456789 divisible by 3?

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

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

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

### info — Recursion

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

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

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

What is 99? It is 9 times 9 8. But, 98 is 9 times 97. Repeating this way is an example of recursion.

### Exercises

1. Factorize
1. 45
2. 4050
3. 2187
2. Show that the divisible-by-3 theorem works for any 3 digits numbers (Hint: Express a 3 digit number as 100a + 10b + c, where 0 ≤ a, b and c ≤ 9)
3. "A number is divisible by 9 if and only if the sum of its digits is divisible by 9." True or false? Determine whether 89, 558, 51858, and 41857 are divisible by 9. Check your answers.

## Finding primes

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

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

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

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

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

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

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

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

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

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

### Exercise

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

## Infinitely many primes

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

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

### Proof of infinitude of primes

Let us first assume that

there are a finite number of primes

therefore

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

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

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

${\displaystyle x=2\times 3\times 5\times \ldots \times n\!}$

Then, let y equal one more than x:

${\displaystyle y=x+1\!}$

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

Fun Fact — Largest known prime

The largest known prime is 243,112,609-1. It has a whopping 12,978,189 digits! Primes of the form 2n-1 are called Mersenne primes named after the French monk/amateur mathematician.

## Useful Off-site Resources

>> Next section: Modular Arithmetic

## Modular arithmetic

Content HSME Primes Modular Arithmetic Problem Set Project Exercise Solutions Problem Set Solutions Definition Sheet Full Version PDF Version

## Modular Arithmetic

### Introduction

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

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

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

${\displaystyle 3+2=5\!}$
${\displaystyle 5+6=11=4\!}$
${\displaystyle 5-6=-1=6\!}$

and

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

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

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

#### Exercise

Find in modulo 11

1.

-1 × -5

2.

3 × 7

3. Compute the first 10 the powers of 2

21, 22, 23, ... , 210

What do you notice?
Using the powers of 2 find

61, 62, 63, ... , 610

What do you notice again?

4.

${\displaystyle {\sqrt {4}}}$

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

5.

${\displaystyle {\sqrt {9}}}$

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

### Inverses

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

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

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

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

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

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

So x = 2 modulo 7 is the required solution.

Definition (Inverse)

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

Inverse is unique

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

Suppose n has two inverses b and c

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

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

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

#### Existence of inverse

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

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

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

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

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

${\displaystyle 3x=15k+1\!}$

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

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

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

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

Theorem

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

Similarly

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

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

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

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

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

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

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

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

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

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

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

#### Exercise

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

2. Find x mod 7 if x exists:

${\displaystyle x=2^{-1}\!}$
${\displaystyle x=3^{-1}\!}$
${\displaystyle x=4^{-1}\!}$
${\displaystyle x=5^{-1}\!}$
${\displaystyle x=6^{-1}\!}$
${\displaystyle x=7^{-1}\!}$

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

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

4. (Trick) Find x

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

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

### Coprime and greatest common divisor

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

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

Example 1:

Find the gcd of 21 and 49.

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

smaller larger
21 49

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

smaller larger
21 49
7 21

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

smaller larger
21 49
7 21
0 7

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

Example 2

Find the gcd of 31 and 101
smaller larger
31 101
8 31
7 8
1 7
0 1

Example 3

Find the gcd of 132 and 200
smaller larger
132 200
68 132
64 68
4 64
0 4

Important to note

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

#### Exercise

1. Determine whether the following sets of numbers are coprimes

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

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

#### info -- Algorithm

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

### Finding Inverses

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

5x = 1 (mod 7)

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

Now let's consider

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

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

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

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

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

We jump into rational maths again

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

We jump once more

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

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

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

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

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

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

Example 1

Find the smallest positive value of a:

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

Choose d = 0, therefore a = 49.

Example 2 Find the smallest positive value of a:

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

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

Example 3 Find the smallest positive value of a:

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

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

Example 4 Find the smallest positive value of a:

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

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

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

ax + by = 1

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

### Diophantine equation

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

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

ax + by = d

where x and y are unknown.

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

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

we can rewrite the above in every day arithmetic

${\displaystyle 216x+811y=1\!}$

which is in the form of a Diophantine equation.

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

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

smaller larger PQ
216 811 3
163

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

811 = 3×216 + 163.

Let's continue:

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

Reading off the table, we can form the following expressions

811 = 3× 216 + 163
216 = 1× 163 + 53
163 = 3× 53 + 4
53 =13× 4 + 1

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

1 = 53 - 13×4
1 = 53 - 13×(163 - 3×53)
1 = 40×53 - 13×163
1 = 40×(216 - 163) - 13×163
1 = 40×216 - 53×163
1 = 40×216 - 53×(811 - 3×216)
1 = 199×216 - 53×811

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

#### Magic Table

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

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

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

 0 1 1 0

Now we write the partial quotient on the first row:

3 1 0 1 1 0

We produce the table according to the following rule:

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

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

3 1 3 0 1 3 1 0 1

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

We shall now produce the whole table without disruption:

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

We can check that

|199×216 - 811×53| = 1

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

#### Exercises

1. Find the smallest positive x:

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

2. Find the smallest positive x:

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

3.

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

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

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

What do you notice?

4.

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

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

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

What do you notice?

### Chinese remainder theorem

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

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

We translate the question into symbolic form:

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

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

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

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

Now we look at the equation modulo 5

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

Substitute into (1) to get the following

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

Now look at the above modulo 7

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

we get

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

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

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

Example 1 Find the smallest x that satisfies:

${\displaystyle x\equiv 1{\pmod {3}}\!}$
${\displaystyle x\equiv 2{\pmod {5}}\!}$
${\displaystyle x\equiv 3{\pmod {7}}\!}$

Solution

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

now substitute back into the first equation, we get

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

we obtain

${\displaystyle b\equiv 3{\pmod {7}}\!}$
${\displaystyle b=3+7c\!}$

again substituting back

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

Therefore 52 is the smallest x that satisfies the congruences.

### Example 2

Find the smallest x that satisfies:

${\displaystyle x\equiv 5{\pmod {11}}\!}$
${\displaystyle x\equiv 3{\pmod {7}}\!}$
${\displaystyle x\equiv 8{\pmod {9}}\!}$

Solution

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

substituting back

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

now solve for b

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

again, substitue back

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

Therefore 269 is the smallest x that satisfies the congruences.

#### Exercises

1. Solve for x

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

2. Solve for x

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

#### *Existence of a solution*

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

x ≡ 5 (mod 15)
x ≡ 10 (mod 21)

a cheekier example is:

x ≡ 1 (mod 2)
x ≡ 0 (mod 2)

but we won't consider silly examples like that.

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

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

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

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

${\displaystyle x\equiv 4{\pmod {15}}\!}$
${\displaystyle x\equiv 7{\pmod {21}}\!}$

we can find a solution

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

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

${\displaystyle 3k\equiv 9\!}$

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

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

${\displaystyle x\equiv a{\pmod {m}}\!}$
${\displaystyle x\equiv b{\pmod {n}}\!}$

we have

${\displaystyle x=a+km\!}$
${\displaystyle x=b+ln\!}$

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

We can approach the problem as follows

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

now suppose m and n have gcd(m,n) = d, and m = dmo, n = dno. We have

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

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

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

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

In summary: for a system of two congruent equations

${\displaystyle x\equiv a{\pmod {m}}\,\!}$
${\displaystyle x\equiv b{\pmod {n}}\,\!}$

there is a solution if and only if

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

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

${\displaystyle x\equiv a_{1}{\pmod {m_{1}}}\,\!}$
${\displaystyle x\equiv a_{2}{\pmod {m_{2}}}\,\!}$
...
${\displaystyle x\equiv a_{n}{\pmod {m_{n}}}\,\!}$

for a solution to exist, we require that if ij

gcd(mi,mj) divides (ai - aj)

#### Exercises

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

1.

x ≡ 7 (mod 25)
x ≡ 22 (mod 45)

2.

x ≡ 7 (mod 23)
x ≡ 3 (mod 11)
x ≡ 3 (mod 13)

3.

x ≡ 7 (mod 25)
x ≡ 22 (mod 45)
x ≡ 7 (mod 11)

4.

x ≡ 4 (mod 28)
x ≡ 28 (mod 52)
x ≡ 24 (mod 32)

## To go further

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

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

## Acknowledgement

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

# Feedback

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

## Problem Set

Content HSME Primes Modular Arithmetic Problem Set Project Exercise Solutions Problem Set Solutions Definition Sheet Full Version PDF Version

## Problem Set

1. Is there a rule to determine whether a 3-digit number is divisible by 11? If so, derive that rule.

2. Show that p, p + 2 and p + 4 cannot all be primes if p is an integer greater than 3.

3. Find x

${\displaystyle {\begin{matrix}x\equiv 1^{7}+2^{7}+3^{7}+4^{7}+5^{7}+6^{7}+7^{7}\ {\pmod {7}}\\\end{matrix}}}$

4. Show that there are no integers x and y such that

${\displaystyle x^{2}-5y^{2}=3\!}$

5. In modular arithmetic, if

${\displaystyle x^{2}\equiv y{\pmod {m}}\!}$

for some m, then we can write

${\displaystyle x\equiv {\sqrt {y}}{\pmod {m}}}$

we say, x is the square root of y mod m.

Note that if x satisfies x2y, then m - x ≡ -x when squared is also equivalent to y. We consider both x and -x to be square roots of y.

Let p be a prime number. Show that

(a)

${\displaystyle (p-1)!\equiv -1\ {\mbox{(mod p)}}}$

where

${\displaystyle n!=1\cdot 2\cdot 3\cdots (n-1)\cdot n}$

E.g. 3! = 1*2*3 = 6

(b)

Hence, show that

${\displaystyle {\sqrt {-1}}\equiv {\frac {p-1}{2}}!{\pmod {p}}}$

for p ≡ 1 (mod 4), i.e., show that the above when squared gives one.

## Square root of minus 1

Content HSME Primes Modular Arithmetic Problem Set Project Exercise Solutions Problem Set Solutions Definition Sheet Full Version PDF Version

## Project -- The Square Root of -1

Notation: In modular arithmetic, if

${\displaystyle x^{2}\equiv y{\pmod {m}}\!}$

for some m, then we can write

${\displaystyle x\equiv {\sqrt {y}}{\pmod {m}}}$

we say, x is the square root of y mod m.

Note that if x satisfies x2y, then m - x ≡ -x when squared is also equivalent to y. We consider both x and -x to be square roots of y.

1. Question 5 of the Problem Set showed that

${\displaystyle x\equiv {\sqrt {-1}}\equiv {\sqrt {p-1}}{\pmod {p}}}$

exists for p ≡ 1 (mod 4) prime. Explain why no square root of -1 exist if p ≡ 3 (mod 4) prime.

2. Show that for p ≡ 1 (mod 4) prime, there are exactly 2 solutions to

${\displaystyle x\equiv {\sqrt {-1}}{\pmod {p}}}$

3. Suppose m and n are integers with gcd(n,m) = 1. Show that for each of the numbers 0, 1, 2, 3, .... , nm - 1 there is a unique pair of numbers a and b such that the smallest number x that satisfies:

x ≡ a (mod m)
x ≡ b (mod n)

is that number. E.g. Suppose m = 2, n = 3, then 4 is uniquely represented by

x ≡ 0 (mod 2)
x ≡ 1 (mod 3)

as the smallest x that satisfies the above two congruencies is 4. In this case the unique pair of numbers are 0 and 1.

4. If p ≡ 1 (mod 4) prime and q ≡ 3 (mod 4) prime. Does

${\displaystyle x\equiv {\sqrt {-1}}{\pmod {pq}}}$

have a solution? Why?

5. If p ≡ 1 (mod 4) prime and q ≡ 1 (mod 4) prime and p ≠ q. Show that

${\displaystyle x\equiv {\sqrt {-1}}{\pmod {pq}}}$

has 4 solutions.

6. Find the 4 solutions to

${\displaystyle x\equiv {\sqrt {-1}}{\pmod {493}}}$

note that 493 = 17 × 29.

7. Take an integer n with more than 2 prime factors. Consider:

${\displaystyle x\equiv {\sqrt {-1}}{\pmod {n}}}$

Under what condition is there a solution? Explain thoroughly.

## Solutions to exercises

Content HSME Primes Modular Arithmetic Problem Set Project Exercise Solutions Problem Set Solutions Definition Sheet Full Version PDF Version

## HSE Primes|Primes and Modular Arithmetic

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.

If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

### Factorisation Exercises

Factorise the following numbers. (note: I know you didn't have to, this is just for those who are curious)

1. 13 is prime
2. ${\displaystyle 26=13\cdot 2}$
3. 59 is prime
4. ${\displaystyle 82=41\cdot 2}$
5. 101 is prime
6. ${\displaystyle 121=11\cdot 11}$
7. ${\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}$

### Recursive Factorisation Exercises

Factorise using recursion.

1. ${\displaystyle 45=3\cdot 3\cdot 5}$
2. ${\displaystyle 4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5}$
3. ${\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}$

### Prime Sieve Exercises

1. Use the above result to quickly work out the numbers that still need to be crossed out in the table below, knowing 5 is the next prime:
${\displaystyle {\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}}$
The next prime number is 5. Because 5 is an unmarked prime number, and 5 * 5 = 25, cross out 25. Also, 7 is an unmarked prime number, and 5 * 7 = 35, so cross off 35. However, 5 * 11 = 55, which is too high, so mark 5 as prime ad move on to 7. The only number low enough to be marked off is 7 * 7, which equals 49. You can go no higher.

2. Find all primes below 200.

The method will not be outlined here, as it is too long. However, all primes below 200 are:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

### Modular Arithmetic Exercises

1. ${\displaystyle (-1)\cdot (-5)\mod {11}=5}$alternatively, -1 = 10, -5 = 6: 10 × 6 = 60 = 5&times 11 + 5 = 5
2. ${\displaystyle 3\cdot 7\mod {11}=21=10}$
3. ${\displaystyle 2^{1}=2,2^{2}=4,2^{3}=8,2^{4}=16=5}$
${\displaystyle 2^{5}=32=10,2^{6}=64=9,2^{7}=128=7}$
${\displaystyle 2^{8}=256=3,2^{9}=512=6,2^{10}=1024=1}$
An easier list: 2, 4, 8, 5, 10, 9, 7, 3, 6, 1
Notice that it is not necessary to actually
compute ${\displaystyle 2^{10}}$ to find ${\displaystyle 2^{10}}$ mod 11.
If you know ${\displaystyle 2^{9}}$ mod 11 = 6.
You can find ${\displaystyle 2^{10}}$ mod 11 = (2*(${\displaystyle 2^{9}}$ mod 11)) mod 11 = 2*6 mod 11 = 12 mod 11 = 1.
We can note that 29 = 6 and 210 = 1, we can calculate 62 easily: 62 = 218 = 2^8 = 3. OR by the above method
${\displaystyle 6^{1}=6,6^{2}=36=3,6^{3}=6*3=18=7,}$
${\displaystyle 6^{4}=6*7=42=9,6^{5}=6*9=54=10,6^{6}=6*10=60=5,}$
${\displaystyle 6^{7}=6*5=30=8,6^{8}=6*8=48=4,6^{9}=6*4=24=2,6^{10}=6*2=12=1.}$
An easier list: 6, 3, 7, 9, 10, 5, 8, 4, 2, 1.
4. 02 = 0, 12 = 1, 22 = 4, 32 = 9,
42 = 16 = 5, 52 = 25 = 5, 62 = 36 = 3, 72 = 49 = 3,
82 = 64 = 9, 92 = 81 = 4, 102 = 100 = 1
An easier list: 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1
Thus${\displaystyle {\sqrt {4}}=2{\mbox{ and }}{\sqrt {4}}=9}$
5. x2 = -2 = 9
Just look at the list above and you'll see that${\displaystyle {\sqrt {-2}}=8{\mbox{ and }}{\sqrt {-2}}=3}$

### Division and Inverses Exercises

1.

${\displaystyle x=2^{-1}=4}$
${\displaystyle x=3^{-1}=5}$
${\displaystyle x=4^{-1}=2}$
${\displaystyle x=5^{-1}=3}$
${\displaystyle x=6^{-1}=6}$
${\displaystyle x=7^{-1}=0^{-1}}$ therefore the inverse does not exist

2. ${\displaystyle x={\frac {28}{7}}=4\ \ {\mbox{(mod 29)}}}$

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

3.

${\displaystyle x=5^{99}\times (40+{\frac {1}{3}})\ \ {\mbox{(mod 11)}}}$
${\displaystyle x=5^{99}\times (40+4)\ \ {\mbox{(mod 11)}}}$
${\displaystyle x=5^{99}\times 0\ \ {\mbox{(mod 11)}}}$
${\displaystyle x=0\ \ {\mbox{(mod 11)}}}$

4.

 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 mod 2 1 2 mod 3 1 3 mod 4 1 3 2 4 mod 5 1 5 mod 6 1 4 5 2 3 6 mod 7 1 3 5 7 mod 8 1 5 7 2 4 8 mod 9 1 7 3 9 mod 10 1 6 4 3 9 2 8 7 5 10 mod 11 1 5 7 11 mod 12 1 7 9 10 8 11 2 5 3 4 6 12 mod 13 1 5 3 11 9 13 mod 14 1 8 4 13 2 11 7 14 mod 15 1 11 13 7 9 3 5 15 mod 16 1 9 6 13 7 3 5 15 2 12 14 10 4 11 8 16 mod 17 1 11 13 5 7 17 mod 18 1 10 13 5 4 16 11 12 17 2 7 8 3 15 14 6 9 18 mod 19

### Coprime and greatest common divisor Exercises

1.

1.
smaller larger
5050 5051
1 5050
0 1
5050 and 5051 are coprime
2.
smaller larger
59 78
19 59
2 19
1 2
0 1
59 and 79 are coprime
3.
smaller larger
111 369
36 111
3 36
0 3
111 and 369 are not coprime
4.
smaller larger
2021 4032
2011 2021
10 2011
1 10
0 1
2021 and 4032 are coprime

2.We first calculate the gcd for all combinations

smaller larger
15 510
0 15
smaller larger
15 375
0 15
smaller larger
375 510
135 375
105 135
30 105
15 30
0 15
The gcd for any combination of the numbers is 15 so the gcd is 15 for the three numbers.

### Diophantine equation Exercises

1.

${\displaystyle {\begin{matrix}216x&=&1+816b\\216c&=&1+168b\\48c&=&1+168d\\48e&=&1+24d\\24e&=&1+24f\\\end{matrix}}}$
There is no solution, because can never become an integer.

2.

${\displaystyle {\begin{matrix}42x&=&7+217b\\42c&=&7+7b\\7c&=&0+7d\\\end{matrix}}}$
We choose d=1, then x=26.

3.

(a)
smaller larger PQ
33 101 3
2 33 16
1 2 2
0 1
 3 16 2 0 1 3 49 101 1 0 1 16 33

4.

(a)
smaller larger PQ
17 317 18
11 17 1
6 11 1
5 6 1
1 5 5
0 1
 18 1 1 1 5 0 1 18 19 37 56 317 1 0 1 1 2 3 17

### Chinese remainder theorem exercises

1.

${\displaystyle {\begin{matrix}3x&\equiv &5{\pmod {14}}\\x&\equiv &11{\pmod {14}}\\x&=&11+14a\\2x&=&2(11+14a)&\equiv &-3{\pmod {17}}\\&&22+28a&\equiv &-3{\pmod {17}}\\&&11a&\equiv &-8{\pmod {17}}\\&&a&=&7+17b\\x&=&11+14(7+17b)&\equiv &6{\pmod {15}}\\&=&109+238b&\equiv &6{\pmod {15}}\\&=&4+13b&\equiv &6{\pmod {15}}\\&=&13b&\equiv &2{\pmod {15}}\\&&b&\equiv &14{\pmod {15}}\\&&b&=&14+15c\\x&=&109+238(14+15c)\\x&=&3441+3570c\end{matrix}}}$

### Question 1

Show that the divisible-by-3 theorem works for any 3 digits numbers (Hint: Express a 3 digit number as 100a + 10b + c, where a, b and c are ≥ 0 and < 10)

Solution 1 Any 3 digits integer x can be expressed as follows

x = 100a + 10b + c

where a, b and c are positive integer between 0 and 9 inclusive. Now

${\displaystyle x\equiv 100a+10b+c\equiv a+b+c{\pmod {3}}}$
${\displaystyle x\equiv 0{\pmod {3}}}$

if and only if a + b + c = 3k for some k. But a, b and c are the digits of x.

### Question 2

"A number is divisible by 9 if and only if the sum of its digits is divisible by 9." True or false? Determine whether 89, 558, 51858, and 41857 are divisible by 9. Check your answers.

Solution 2 The statement is true and can be proven as in question 1.

### Question 4

The prime sieve has been applied to the table of numbers above. Notice that every number situated directly below 2 and 5 are crossed out. Construct a rectangular grid of numbers running from 1 to 60 so that after the prime sieve has been performed on it, all numbers situated directly below 3 and 5 are crossed out. What is the width of the grid?

Solution 4 The width of the grid should be 15 or a multiple of it.

### Question 6

Show that n - 1 has itself as an inverse modulo n.

Solution 6

(n - 1)2 = n2 - 2n + 1 = 1 (mod n)

Alternatively

(n - 1)2 = (-1)2 = 1 (mod n)

### Question 7

Show that 10 does not have an inverse modulo 15.

Solution 7 Suppose 10 does have an inverse x mod 15,

10x = 1 (mod 15)
2×5x = 1 (mod 15)
5x = 8 (mod 15)
5x = 8 + 15k

for some integer k

x = 1.6 + 3k

but now x is not an integer, therefore 10 does not have an inverse

## Problem set solutions

Content HSME Primes Modular Arithmetic Problem Set Project Exercise Solutions Problem Set Solutions Definition Sheet Full Version PDF Version

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.

If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

### Question 1

Is there a rule to determine whether a 3-digit number is divisible by 11? If yes, derive that rule.

Solution

Let x be a 3-digit number We have

${\displaystyle x=100a+10b+c\!}$

now

${\displaystyle x\equiv a+10b+c\equiv a-b+c{\pmod {11}}\!}$

We can conclude a 3-digit number is divisible by 11 if and only if the sum of first and last digit minus the second is divisible by 11.

### Question 2

Show that p, p + 2 and p + 4 cannot all be primes. (p a positive integer and is great than 3)

Solution

We look at the arithmetic mod 3, then p slotted into one of three categories

1st category
${\displaystyle p\equiv 0{\pmod {3}}\!}$
we deduce p is not prime, as it's a multiple of 3
2nd category
${\displaystyle p\equiv 1{\pmod {3}}\!}$
${\displaystyle p+2\equiv 0{\pmod {3}}\!}$
so p + 2 is not prime
3rd category
${\displaystyle p\equiv 2{\pmod {3}}\!}$
${\displaystyle p+4\equiv 0{\pmod {3}}\!}$
therefore p + 4 is not prime

Therefore p, p + 2 and p + 4 cannot all be primes.

### Question 3

Find x

${\displaystyle {\begin{matrix}x\equiv 1^{7}+2^{7}+3^{7}+4^{7}+5^{7}+6^{7}+7^{7}\ {\pmod {7}}\\\end{matrix}}}$

Solution

Notice that

${\displaystyle -a\equiv 7-a{\pmod {7}}\!}$.

Then

${\displaystyle 1^{7}\equiv (7-6)^{7}\equiv (-6)^{7}\equiv -(6^{7}){\pmod {7}}\!}$.

Likewise,

${\displaystyle 2^{7}\equiv -5^{7}{\pmod {7}}\!}$

and

${\displaystyle 3^{7}\equiv -4^{7}{\pmod {7}}\!}$.

Then

 ${\displaystyle x\!}$ ${\displaystyle \equiv 1^{7}+2^{7}+3^{7}+4^{7}+5^{7}+6^{7}+7^{7}\!}$ ${\displaystyle \equiv 1^{7}+2^{7}+3^{7}-3^{7}-2^{7}-1^{7}+7^{7}\!}$ ${\displaystyle \equiv 0{\pmod {7}}\!}$

### Question 4

9. Show that there are no integers x and y such that

${\displaystyle x^{2}-5y^{2}=3\!}$

Solution

Look at the equation mod 5, we have

${\displaystyle x^{2}=3{\pmod {5}}\!}$

but

 ${\displaystyle 1^{2}\equiv 1\!}$ ${\displaystyle 2^{2}\equiv 4\!}$ ${\displaystyle 3^{2}\equiv 4\!}$ ${\displaystyle 4^{2}\equiv 1\!}$

therefore there does not exist a x such that

${\displaystyle x^{2}\equiv 3{\pmod {5}}\!}$

### Question 5

Let p be a prime number. Show that

(a)

${\displaystyle (p-1)!\equiv -1\ {\pmod {p}}}$

where

${\displaystyle n!=1\cdot 2\cdot 3\cdots (n-1)\cdot n}$

E.g. 3! = 1×2×3 = 6

(b) Hence, show that

${\displaystyle {\sqrt {-1}}\equiv {\frac {p-1}{2}}!{\pmod {p}}}$

for p ≡ 1 (mod 4)

Solution

a) If p = 2, then it's obvious. So we suppose p is an odd prime. Since p is prime, some deep thought will reveal that every distinct element multiplied by some other element will give 1. Since

${\displaystyle (p-1)!=(p-1)(p-2)(p-3)\cdots 2\!}$

we can pair up the inverses (two numbers that multiply to give one), and (p - 1) has itself as an inverse, therefore it's the only element not "eliminated"

 ${\displaystyle (p-1)!\equiv (p-1)\equiv -1\!}$

as required.

b) From part a)

${\displaystyle -1\equiv (p-1)!\!}$

since p = 4k + 1 for some positive integer k, (p - 1)! has 4k terms

${\displaystyle -1=1\times 2\times 3\times \cdots 2k\times (-2k)\cdots \times (-3)\times (-2)\times (-1)}$

there are an even number of minuses on the right hand side, so

${\displaystyle -1=(1\times 2\times 3\times \cdots 2k)^{2}}$

it follows

${\displaystyle {\sqrt {-1}}=1\times 2\times 3\times ...2k}$

and finally we note that p = 4k + 1, we can conclude

${\displaystyle {\sqrt {-1}}={\frac {p-1}{2}}!}$

# Logic

## Introduction

Logic is the study of the way we reason. In this chapter, we focus on the methods of logical reasoning, i.e. digital logic, predicate calculus, application to proofs and the (insanely) fun logical puzzles.

## Boolean algebra

In the black and white world of ideals, there is absolute truth. That is to say everything is either true or false. With this philosophical backdrop, we consider the following examples:

"One plus one equals two." True or false?

That is (without a doubt) true!

"1 + 1 = 2 AND 2 + 2 = 4." True or false?

That is also true.

"1 + 1 = 3 OR Sydney is in Australia" True or false?

It is true! Although 1 + 1 = 3 is not true, the OR in the statement made it so that if either part of the statement is true then the whole statement is true.

Now let's consider a more puzzling example

"2 + 2 = 4 OR 1 + 1 = 3 AND 1 - 3 = -1" True or false?

The truth or falsity of the statements depends on the order in which you evaluate the statement. If you evaluate "2 + 2 = 4 OR 1 + 1 = 3" first, the statement is false, and otherwise true. As in ordinary algebra, it is necessary that we define some rules to govern the order of evaluation, so we don't have to deal with ambiguity.

Before we decide which order to evaluate the statements in, we do what most mathematician love to do -- replace sentences with symbols.
Let x represent the truth or falsity of the statement 2 + 2 = 4.
Let y represent the truth or falsity of the statement 1 + 1 = 3.
Let z represent the truth or falsity of the statement 1 - 3 = -1.

Then the above example can be rewritten in a more compact way:

x OR y AND z

To go one step further, mathematicians also replace OR by + and AND by ×, the statement becomes:

${\displaystyle x+y\times z}$

Now that the order of precedence is clear. We evaluate (y AND z) first and then OR it with x. The statement "x + yz" is true, or symbolically

x + yz = 1

where the number 1 represents "true".

There is a good reason why we choose the multiplicative sign for the AND operation. As we shall see later, we can draw some parallels between the AND operation and multiplication.

The Boolean algebra we are about to investigate is named after the British mathematician George Boole. Boolean algebra is about two things -- "true" or "false" which are often represented by the numbers 1 and 0 respectively. Alternative, T and F are also used.

Boolean algebra has operations (AND and OR) analogous to the ordinary algebra that we know and love.

### Basic Truth tables

We have all had to memorize the 9 by 9 multiplication table and now we know it all by heart. In Boolean algebra, the idea of a truth table is somewhat similar.

Let's consider the AND operation which is analogous to the multiplication. We want to consider:

x AND y

where and x and y each represent a true or false statement (e.g. It is raining today). It is true if and only if both x and y are true, in table form:

The AND function
x y x AND y
F F
F
F T
F
T F
F
T T
T

We shall use 1 instead of T and 0 instead of F from now on.

The AND function
x y x AND y
0 0
0
0 1
0
1 0
0
1 1
1

Now you should be able to see why we say AND is analogous to multiplication, we shall replace the AND by ×, so x AND y becomes x×y (or just xy). From the AND truth table, we have:

0 × 0 = 0
0 × 1 = 0
1 × 0 = 0
1 × 1 = 1

To the OR operation. x OR y is FALSE if and only if both x and y are false. In table form:

The OR function
x y x OR y
0 0
0
0 1
1
1 0
1
1 1
1

We say OR is almost analoguous to addition. We shall illustrate this by replacing OR with +:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1 (like 1 OR 1 is 1)

The NOT operation is not a binary operation like AND and OR, but a unary operation, meaning it works with one argument. NOT x is true if x is false and false if x is true. In table form:

The NOT function
x NOT x
0
1
1
0

In symbolic form, NOT x is denoted x' or ~x (or by a bar over the top of x).

Alternative notations:

${\displaystyle x\times y=x\wedge y}$

and

${\displaystyle x+y=x\vee y}$

### Compound truth tables

The three truth tables presented above are the most basic of truth tables and they serve as the building blocks for more complex ones. Suppose we want to construct a truth table for xy + z (i.e. x AND y OR z). Notice this table involves three variables (x, y and z), so we would expect it to be bigger than the previous ones.

To construct a truth table, firstly we write down all the possible combinations of the three variables:

x y z
0 0
0
0 0
1
0 1
0
0 1
1
1 0
0
1 0
1
1 1
0
1 1
1

There is a pattern to the way the combinations are written down. We always start with 000 and end with 111. As to the middle part, it is up to the reader to figure out.

We then complete the table by hand computing what value each combination is going to produce using the expression xy + z. For example:

000
x = 0, y = 0 and z = 0
xy + z = 0
001
x = 0, y = 0 and z = 1
xy + z = 1

We continue in this way until we fill up the whole table

x y z xyORz
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

The procedure we follow to produce truth tables are now clear. Here are a few more examples of truth tables.

Example 1 -- x + y + z

x y z x+y+z
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Example 2 -- (x + yz)'

When an expression is hard to compute, we can first compute intermediate results and then the final result.

x y z x+yz (x+yz)'
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 1 0
1 0 1 1 0
1 1 0 1 0
1 1 1 1 0

Example 3 -- (x + yz')w

x y z w (x+yz')w
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1

#### Exercise

Produce the truth tables for the following operations:

1. NAND: x NAND y = NOT (x AND y)
2. NOR: x NOR y = NOT (x OR y)
3. XOR: x XOR y is true if and ONLY if one of x or y is true.

Produce truth tables for:

1. xyz
2. x'y'z'
3. xyz + xy'z
4. xz
5. (x + y)'
6. x'y'
7. (xy)'
8. x' + y'

### Laws of Boolean algebra

In ordinary algebra, two expressions may be equivalent to each other, e.g. xz + yz = (x + y)z. The same can be said of Boolean algebra. Let's construct truth tables for:

xz + yz
(x + y)z

xz + yz

x y z xz+yz
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

(x + y)z

x y z (x+y)z
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

By comparing the two tables, you will have noticed that the outputs (i.e. the last column) of the two tables are the same!

Definition

We say two Boolean expressions are equivalent if the output of their truth tables are the same.

We list a few expressions that are equivalent to each other

x + 0 = x
x × 1 = x
xz + yz = (x + y)z
x + x' = 1
x × x' = 0
x × x = x
x + yz = (x + y)(x + z)

Take a few moments to think about why each of those laws might be true.

The last law is not obvious but we can prove that it's true using the other laws:

${\displaystyle {\begin{matrix}(x+y)(x+z)&=&x(x+z)+y(x+z)\\&=&xx+xz+xy+yz\\&=&x+xz+xy+yz\\&=&x(1+z+y)+yz\\&=&x+yz\end{matrix}}}$

It has been said: "the only thing to remember in mathematics is that there is nothing to remember. Remember that!". You should not try to commit to memory the laws as they are stated, because some of them are so deadly obvious once you are familiar with the AND, OR and NOT operations. You should only try to remember those things that are most basic, once a high level of familiarity is developed, you will agree there really isn't anything to remember.

#### Simplification

Once we have those laws, we will want to simplify Boolean expressions just like we do in ordinary algebra. We can all simplify the following example with ease:

${\displaystyle {\begin{matrix}xyzw'+xyzw&=&xyz(w+w')\\&=&xyz\end{matrix}}}$

the same can be said about:

${\displaystyle {\begin{matrix}(x+y)(x'+y')&=&x(x'+y')+y(x'+y')\\&=&xx'+xy'+yx'+yy'\\&=&0+xy'+yx'+0\\&=&xy'+yx'\end{matrix}}}$

From those two examples we can see that complex-looking expressions can be reduced very significantly. Of particular interest are expressions of the form of a sum-of-product, for example:

xyz + xyz' + xy'z + x'yz + x'y'z' + x'y'z

We can factorise and simplify the expression as follows

${\displaystyle xyz+xyz'+xy'z+x'yz+x'y'z'+x'y'z}$
${\displaystyle =\ xy(z+z')+xy'z+x'yz+x'y'(z'+z)}$
${\displaystyle =\ xy+xy'z+x'yz+x'y'}$
${\displaystyle =\ x(y+y'z)+x'(yz+y')}$

It is only hard to go any further, although we can. We use the identity:

x + yz = (x + y)(x + z)

If the next step is unclear, try constructing truth tables as an aid to understanding.

${\displaystyle {\begin{matrix}&=&\ x(y+z)+x'(z+y')\\&=&\ xy+xz+x'z+x'y'\\&=&\ xy+(x+x')z+x'y'\\&=&\ xy+z+x'y'\\\end{matrix}}}$

And this is as far as we can go using the algebraic approach (or any other approach). The algebraic approach to simplification relies on the principle of elimination. Consider, in ordinary algebra:

x + y - x

We simplify by rearranging the expression as follows

(x - x) + y = y

Although we only go through the process in our head, the idea is clear: we bring together terms that cancel themselves out and so the expression is simplified.

#### De Morgan's theorems

So far we have only dealt with expressions in the form of a sum of products e.g. xyz + x'z + y'z'. De Morgan's theorems help us to deal with another type of Boolean expressions. We revisit the AND and OR truth tables:

x y x × y x + y
0 0
0
0
0 1
0
1
1 0
0
1
1 1
1
1

You would be correct to suspect that the two operations are connected somehow due to the similarities between the two tables. In fact, if you invert the AND operation, i.e. you perform the NOT operations on x AND y. The outputs of the two operations are almost the same:

x y (x × y)' x + y
0 0
1
0
0 1
1
1
1 0
1
1
1 1
0
1

The connection between AND, OR and NOT is revealed by reversing the output of x + y by replacing it with x' + y'.

x y (x × y)' x' + y'
0 0
1
1
0 1
1
1
1 0
1
1
1 1
0
0

Now the two outputs match and so we can equate them:

(xy)' = x' + y'

this is one of de Morgan's laws. The other which can be derived using a similar process is:

(x + y)' = x'y'

We can apply those two laws to simplify equations:

Example 1
Express x in sum of product form

${\displaystyle {\begin{matrix}x&=&(ab'+c)'\\&=&(ab')'c'\\&=&(a'+b)c'\\&=&a'c'+bc'\end{matrix}}}$

Example 2
Express x in sum of product form

${\displaystyle {\begin{matrix}x&=&(a+b+c)'\\&=&(a+b)'c'\\&=&a'b'c'\\\end{matrix}}}$This points to a possible extension of De Morgan's laws to 3 or more variables.

Example 3
Express x in sum of product form

${\displaystyle {\begin{matrix}x&=&[(a'+c)\cdot (b+d')]'\\&=&(a'+c)'+(b+d')'\\&=&ac'+b'd\\\end{matrix}}}$

Example 4
Express x in sum of product form

${\displaystyle {\begin{matrix}x&=&[(a+bc)\cdot (d+ef)]'\\&=&(a+bc)'+(d+ef)'\\&=&a'(bc)'+d'(ef)'\\&=&a'(b'+c')+d'(e'+f')\\&=&a'b'+a'c'+d'e'+d'f'\\\end{matrix}}}$

Another thing of interest we learnt is that we can reverse the truth table of any expression by replacing each of its variables by their opposites, i.e. replace x by x' and y' by y etc. This result shouldn't have been a surprise at all, try a few examples yourself.

De Morgan's laws

${\displaystyle (x+y)'=x'y'}$
${\displaystyle (xy)'=x'+y'}$

#### Exercise

1. Express in simplified sum-of-product form:
1. z = ab'c' + ab'c + abc
2. z = ab(c + d)
3. z = (a + b)(c + d + f)
4. z = a'c(a'bd)' + a'bc'd' + ab'c
5. z = (a' + b)(a + b + d)d'
2. Show that x + yz is equivalent to (x + y)(x + z)

## Propositions

We have been dealing with propositions since the start of this chapter, although we are not told they are propositions. A proposition is simply a statement (or sentence) that is either TRUE or FALSE. Hence, we can use Boolean algebra to handle propositions.

There are two special types of propositions -- tautology and contradiction. A tautology is a proposition that is always TRUE, e.g. "1 + 1 = 2". A contradiction is the opposite of a tautology, it is a proposition that is always FALSE, e.g. 1 + 1 = 3. As usual, we use 1 to represent TRUE and 0 to represent FALSE. Please note that opinions are not propositions, e.g. "42 is an awesome number" is just an opinion, its truth or falsity is not universal, meaning some think it's true, some do not.

### Examples

• "It is raining today" is a proposition.
• "Sydney is in Australia" is a proposition.
• "1 + 2 + 3 + 4 + 5 = 16" is a proposition.
• "Earth is a perfect sphere" is a proposition.
• "How do you do?" is not a proposition - it's a question.
• "Go clean your room!" is not a proposition - it's a command.
• "Martians exist" is a proposition.

Since each proposition can only take two values (TRUE or FALSE), we can represent each by a variable and decide whether compound propositions are true by using Boolean algebra, just like we have been doing. For example "It is always hot in Antarctica OR 1 + 1 = 2" will be evaluated as true.

### Implications

Propositions of the type if something something then something something are called implications. The logic of implications are widely applicable in mathematics, computer science and general everyday common sense reasoning! Let's start with a simple example

"If 1 + 1 = 2 then 2 - 1 = 1"

is an example of implication, it simply says that 2 - 1 = 1 is a consequence of 1 + 1 = 2. It's like a cause and effect relationship. Consider this example:

John says: "If I become a millionaire, then I will donate $500,000 to the Red Cross." There are four situations: 1. John becomes a millionaire and donates$500,000 to the Red Cross
2. John becomes a millionaire and does not donate $500,000 to the Red Cross 3. John does not become a millionaire and donates$500,000 to the Red Cross
4. John does not become a millionaire and does not donate \$500,000 to the Red Cross

In which of the four situations did John NOT fulfill his promise? Clearly, if and only if the second situation occurred. So, we say the proposition is FALSE if and only if John becomes a millionaire and does not donate. If John did not become a millionaire then he can't break his promise, because his promise is now claiming nothing, therefore it must be evaluated TRUE.

If x and y are two propositions, x implies y (if x then y), or symbolically

${\displaystyle x\Rightarrow y}$

has the following truth table:

x y ${\displaystyle x\Rightarrow y}$
0 0
1
0 1
1
1 0
0
1 1
1

For emphasis, ${\displaystyle x\Rightarrow y}$ is FALSE if and only if x is true and y false. If x is FALSE, it does not matter what value y takes, the proposition is automatically TRUE. On a side note, the two propositions x and y need not have anything to do with each other, e.g. "1 + 1 = 2 implies Australia is in the southern hemisphere" evaluates to TRUE!

If

${\displaystyle (x\Rightarrow y)\ {\mbox{AND}}\ (y\Rightarrow x)}$

then we express it symbolically as

${\displaystyle x\Leftrightarrow y}$.

It is a two way implication which translates to x is TRUE if and only if y is true. The if and only if operation has the following truth table:

x y ${\displaystyle x\Leftrightarrow y}$
0 0
1
0 1
0
1 0
0
1 1
1

The two new operations we have introduced are not really new, they are just combinations of AND, OR and NOT. For example:

${\displaystyle x\Rightarrow y=x'+y}$

Check it with a truth table. Because we can express the implication operations in terms of AND, OR and NOT, we have open them to manipulation by Boolean algebra and de Morgan's laws.

Example 1
Is the following proposition a tautology (a proposition that's always true)

${\displaystyle [(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)}$

Solution 1

${\displaystyle =\ [(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)}$
${\displaystyle =\ [(x'+y)(y'+z)]'+(x'+z)}$
${\displaystyle =\ (x'+y)'+(y'+z)'+x'+z}$
${\displaystyle =\ xy'+yz'+x'+z}$
${\displaystyle =\ y'+y+x'+z}$
${\displaystyle =\ 1}$

Therefore it's a tautology.

Solution 2
A somewhat easier solution is to draw up a truth table of the proposition, and note that the output column are all 1s. Therefore the proposition is a tautology, because the output is 1 regardless of the inputs (i.e. x, y and z).

Example 2
Show that the proposition z is a contradiction (a proposition that is always false):

z = xy(x + y)'

Solution

${\displaystyle {\begin{matrix}z&=&xy(x+y)'\\&=&xy(x'y')\\&=&0\\\end{matrix}}}$

Back to Example 1, :${\displaystyle [(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)}$. This isn't just a slab of symbols, you should be able translate it into everyday language and understand intuitively why it's true.

#### Exercises

1. Decide whether the following propositions are true or false:
1. If 1 + 2 = 3, then 2 + 2 = 5
2. If 1 + 1 = 3, then boys don't like mud
2. Show that the following pair of propositions are equivalent
1. ${\displaystyle x\Rightarrow y}$ : ${\displaystyle y'\Rightarrow x'}$

## Logic Puzzles

Puzzle is an all-encompassing word, it refers to anything trivial that requires solving. Here is a collection of logic puzzles that we can solve using Boolean algebra.

Example 1

We have two type of people -- knights or knaves. A knight always tell the truth but the knaves always lie.

Two people, Alex and Barbara, are chatting. Alex says :"We are both knaves"

Who is who?

We can probably work out that Alex is a knave in our heads, but the algebraic approach to determine Alex 's identity is as follows:

Let A be TRUE if Alex is a knight
Let B be TRUE if Barbara is a knight
There are two situations, either:
Alex is a knight and what he says is TRUE, OR
he is NOT a knight and what he says is FALSE.
There we have it, we only need to translate it into symbols:
A(A'B') + A'[(A'B')'] = 1

we simplify:

(AA')B' + A'[A + B] = 1
A'A + A'B = 1
A'B = 1

Therefore A is FALSE and B is TRUE. Therefore Alex is a knave and Barbara a knight.

Example 2

There are three businessmen, conveniently named Archie, Billy and Charley, who order martinis together every weekend according to the following rules:

1. If A orders a martini, so does B.
2. Either B or C always order a martini, but never at the same lunch.
3. Either A or C always order a martini (or both)
4. If C orders a martini, so does A.
1. ${\displaystyle A\Rightarrow B}$ or ${\displaystyle A'+B=1}$ (simplified from: ${\displaystyle AB+A'B'+A'B=1}$
2. ${\displaystyle B'C+BC'=1}$
3. ${\displaystyle A+C=1}$
4. ${\displaystyle C\Rightarrow A}$ or ${\displaystyle C'+A=1}$ (simplified from: ${\displaystyle CA+C'A'+C'A=1}$

Putting all these into one formula and simplifying:

${\displaystyle {\begin{matrix}1&=&(A'+B)(B'C+BC')(A+C)(C'+A)\\&=&(A'+B)(B'C+BC')(AC'+AA+CC'+AC)\\&=&(A'+B)(B'C+BC')(AC'+A+0+AC)\\&=&(A'+B)(B'C+BC')(AC'+A+AC)\\&=&(A'+B)(B'C+BC')(C'+1+C)A\\&=&(A'+B)(B'C+BC')(1)A\\&=&(A'+B)(B'C+BC')A\\&&{\mbox{Now that we know that }}A=1{\mbox{ we can substitute that in:}}\\&=&(0+B)(B'C+BC')1\\&=&(B)(B'C+BC')\\&&{\mbox{Now that we know that }}B=1{\mbox{ we can substitute that in:}}\\&=&(1)(0C+1C')\\&=&C'\\&&{\mbox{If }}1=C'{\mbox{ then }}C=0\\&&ABC'=1\end{matrix}}}$

## Problem Set

1. Decide whether the following propositions are equivalent:

${\displaystyle x'\Rightarrow y'}$
${\displaystyle y\Rightarrow x}$

2. Express in simplest sum-of-product form the following proposition:

${\displaystyle (x\Leftrightarrow y)\Rightarrow z}$

3. Translate the following sentences into symbolic form and decide if it's true:

a. For all x, if x2 = 9 then x2 - 6x - 3 = 0
b. We can find a x, such that x2 = 9 and x2 - 6x - 3 = 0 are both true.

4. NAND is a binary operation:

x NAND y = (xy)'

Find a proposition that consists of only NAND operators, equivalent to:

(x + y)w + z

5. Do the same with NOR operators. Recall that x NOR y = (x + y)'

# Feedback

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

# Mathematical proofs

"It is by logic that we prove, but by intuition that we discover."

## Introduction

Mathematicians have been, for the past five hundred years or so, obsessed with proofs. They want to prove everything, and in the process proved that they can't prove everything (see this). This chapter will introduce the axiomatic approach to mathematics, and several types of proofs.

## Direct proof

The direct proof is relatively simple — by logically applying previous knowledge, we directly prove what is required.

Example 1

Prove that the sum of any two even integers ${\displaystyle x}$ and ${\displaystyle y}$ is even.

Solution 1

We know that since ${\displaystyle x}$ and ${\displaystyle y}$ are even, they must have 2 as a factor. Then, we can write the following:

Let ${\displaystyle x=2a}$ , ${\displaystyle y=2b}$ , for some integers ${\displaystyle a,b}$

Then:

${\displaystyle {\begin{matrix}x+y&=&2a+2b\\&=&2(a+b)\end{matrix}}}$

by the distributive property of integers

The number ${\displaystyle 2(a+b)}$ clearly has 2 as a factor, which implies it is even. Therefore, ${\displaystyle x+y}$ is even.

Example 2

Prove the following statement for non-zero integers ${\displaystyle a,b,c}$:

If ${\displaystyle a}$ divides ${\displaystyle b}$ and ${\displaystyle b}$ divides ${\displaystyle c}$ , then ${\displaystyle a}$ divides ${\displaystyle c}$ .

Solution 2

If an integer ${\displaystyle x}$ divides an integer ${\displaystyle y}$ , then we can write ${\displaystyle y=qx}$ , for some non-zero integer ${\displaystyle q}$ . So let's say that ${\displaystyle b=qa}$ and ${\displaystyle c=rb}$ , for some non-zero integers ${\displaystyle q}$ and ${\displaystyle r}$ . Then:

${\displaystyle {\begin{matrix}c&=&rb\\&=&r(qa)\\&=&(rq)a\end{matrix}}}$

by the associative property of integer multiplication.

But since ${\displaystyle q}$ and ${\displaystyle r}$ are integers, their product ${\displaystyle qr}$ must also be an integer. Therefore, ${\displaystyle c}$ is the product of some integer multiplied by ${\displaystyle a}$ , so we get that ${\displaystyle a}$ divides ${\displaystyle c}$ .

## Mathematical induction

Deductive reasoning is the process of reaching a conclusion that is guaranteed to follow. For example, if we know

• All ravens are black birds, and
• For every action, there is an equal and opposite reaction

then we can conclude:

• This bird is a raven, therefore it is black.
• This billiard ball will move when struck with a cue.

Induction is the opposite of deduction. To induce, we observe how things behave in specific cases and from that we draw conclusions as to how things behave in the general case.

Suppose we want to show that a statement (let us call it ${\displaystyle S}$ for easier notation) is true for all natural numbers. This is how induction a proof by induction works:

1. First, we show that ${\displaystyle S}$ is true for the natural number 1. This is usually called the basis or the base case.
2. Then, we show that ${\displaystyle S}$ is true for natural number ${\displaystyle n+1}$ whenever it is true for natural number ${\displaystyle n}$ .
3. By mathematical induction, ${\displaystyle S}$ is true for all natural numbers.

To understand how the last step works, notice the following

• ${\displaystyle S}$ is true for 1 (due to step 1)
• ${\displaystyle S}$ is true for 2 because it is true for 1 (due to step 2)
• ${\displaystyle S}$ is true for 3 because it is true for 2 (due to previous)
• ${\displaystyle S}$ is true for 4 because it is true for 3 (due to previous)
• ${\displaystyle S}$ is true for 5 because it is true for 4 (due to previous)
• and so on...

Example 1 Show that the identity

${\displaystyle 1+2+\dots +n={\frac {n(n+1)}{2}}}$

holds for all positive integers.

Solution Firstly, we show that it holds for 1

${\displaystyle 1={\frac {(1+1)1}{2}}={\frac {2}{2}}=1}$

Suppose the identity holds for some natural number k:

${\displaystyle 1+2+3+...+k={\frac {1}{2}}(k+1)k}$

This supposition is known as the induction hypothesis. We assume it is true, and aim to show that,

${\displaystyle 1+2+3+...+k+(k+1)={\frac {1}{2}}(k+2)(k+1)}$

is also true.

We proceed

${\displaystyle {\begin{matrix}1+2+3+...+k&&=&{\frac {1}{2}}(k+1)k\\\\1+2+3+...+k&+(k+1)&=&{\frac {1}{2}}(k+1)k+(k+1)\\\\&&=&(k+1)({\frac {k}{2}}+1)\\\\&&=&{\frac {1}{2}}(k+1)(k+2)\end{matrix}}}$

which is what we have set out to show. Since the identity holds for 3, it also holds for 4, and since it holds for 4 it also holds for 5, and 6, and 7, and so on.

There are two types of mathematical induction: strong and weak. In weak induction, you assume the identity holds for certain value k, and prove it for k+1. In strong induction, the identity must be true for any value lesser or equal to k, and then prove it for k+1.

Example 2 Show that n! > 2n for n ≥ 4.

Solution The claim is true for n = 4. As 4! > 24, i.e. 24 > 16. Now suppose it's true for n = k, k ≥ 4, i.e.

k! > 2k

it follows that

(k+1)k! > (k+1)2k > 2k+1
(k+1)! > 2k+1

We have shown that if for n = k then it's also true for n = k + 1. Since it's true for n = 4, it's true for n = 5, 6, 7, 8 and so on for all n.

Example 3 Show that

${\displaystyle 1^{3}+2^{3}+...+n^{3}={\frac {(n+1)^{2}n^{2}}{4}}}$

Solution Suppose it's true for n = k, i.e.

${\displaystyle 1^{3}+2^{3}+...+k^{3}={\frac {(k+1)^{2}k^{2}}{4}}}$

it follows that

${\displaystyle {\begin{matrix}1^{3}+2^{3}+...+k^{3}+(k+1)^{3}&=&{\frac {(k+1)^{2}k^{2}}{4}}+(k+1)^{3}\\&=&(k+1)^{2}({\frac {k^{2}}{4}}+(k+1))\\&=&{\frac {1}{4}}(k+1)^{2}(k^{2}+4k+4)\\&=&{\frac {1}{4}}(k+1)^{2}(k+2)^{2}\end{matrix}}}$

We have shown that if it's true for n = k then it's also true for n = k + 1. Now it's true for n = 1 (clear). Therefore it's true for all integers.

### Exercises

1. Prove that ${\displaystyle 1^{2}+2^{2}+...+n^{2}={\frac {n(2n^{2}+3n+1)}{6}}}$

2. Prove that for n ≥ 1,

${\displaystyle (1+{\sqrt {5}})^{n}=x_{n}+y_{n}{\sqrt {5}}}$

where xn and yn are integers.

3. Note that

${\displaystyle \sum _{i=1}^{n}[i^{k}-(i-1)^{k}]=n^{k}}$

Prove that there exists an explicit formula for

${\displaystyle \sum _{i=1}^{n}i^{m}}$ for all integer m. E.g.

${\displaystyle 1^{3}+2^{3}+...+n^{3}={\frac {n^{2}(n+1)^{2}}{4}}}$

4. The sum of all of the interior angles of a triangle is ${\displaystyle 180^{\circ }}$; the sum of all the angles of a rectangle is ${\displaystyle 360^{\circ }}$. Prove that the sum of all the angles of a polygon with n sides, is ${\displaystyle (n-2)\cdot 180^{\circ }}$.

"When you have eliminated the impossible, what ever remains, however improbable must be the truth." Sir Arthur Conan Doyle

The idea of a proof by contradiction is to:

1. First, we assume that the opposite of what we wish to prove is true.
2. Then, we show that the logical consequences of the assumption include a contradiction.
3. Finally, we conclude that the assumption must have been false.

### √2 is irrational

As an example, we shall prove that ${\displaystyle {\sqrt {2}}}$ is not a rational number. Recall that a rational number is a number which can be expressed in the form of p/q, where p and q are integers and q does not equal 0 (see the 'categorizing numbers' section here).

First, assume that ${\displaystyle {\sqrt {2}}}$ is rational:

${\displaystyle {\sqrt {2}}={\frac {a}{b}}}$

where a and b are coprime (i.e. integers with no common factors, with greatest common divisor 1). If a and b are not coprime, we remove all common factors. In other words, a/b is in simplest form. Now, continuing:

${\displaystyle {\begin{matrix}{\sqrt {2}}&=&a/b\\2&=&a^{2}/b^{2}\\2b^{2}&=&a^{2}\end{matrix}}}$

We have now found that a2 is some integer multiplied by 2. Therefore, a2 must be divisible by two. If a2 is even, then a must also be even, for an odd number squared yields an odd number. Therefore we can write a = 2c, where c is another integer.

${\displaystyle {\begin{matrix}2b^{2}&=&a^{2}\\2b^{2}&=&(2c)^{2}\\2b^{2}&=&4c^{2}\\b^{2}&=&2c^{2}\end{matrix}}}$

We have discovered that b2 is also an integer multiplied by two. It follows that b must be even. We have a contradiction! Both a and b are even integers. In other words, both have the common factor of 2. But we already said that a/b is in simplest form, with no common factors. Since such a contradiction has been established, we must conclude that our original assumption was false. Therefore, √2 is irrational.

### Contrapositive

Some propositions that take the form of if xxx then yyy can be hard to prove. It is sometimes useful to consider the contrapositive of the statement. Before I explain what contrapositive is let us see an example

"If x2 is odd then x is also odd"

is harder to prove than

"if x is even then x2 is also even"

although they mean the same thing. So instead of proving the first proposition directly, we prove the second proposition instead.

If A and B are two propositions, and we aim to prove

If A is true then B is true

we may prove the equivalent statement

If B is false then A is false

instead. This technique is called proof by contrapositive.

To see why those two statements are equivalent, we show the following boolean algebra expressions is true (see Logic)

${\displaystyle p\Rightarrow q\equiv q'\Rightarrow p'\!}$

(to be done by the reader).

### Exercises

1. Prove that there is no perfect square number for 11,111,1111,11111......

2. Prove that there are infinitely number of k's such that, 4k + 3, is prime. (Hint: consider N = p1p2...pm + 3)

This is some basic information to help with reading other higher mathematical literature. ... to be expanded

### Quantifiers

Sometimes we need propositions that involve some description of rough quantity, e.g. "For all odd integers x, x2 is also odd". The word all is a description of quantity. The word "some" is also used to describe quantity.

Two special symbols are used to describe the quanties "all" and "some"

${\displaystyle \forall }$ means "for all" or "for any"
${\displaystyle \exists }$ means "there are some" or "there exists"

Example 1
The proposition:

For all even integers x, x2 is also even.

can be expressed symbolically as:

${\displaystyle (\forall x)(x{\mbox{ is even}}\Rightarrow x^{2}{\mbox{ is even}})}$

Example 2
The proposition:

There are some odd integers x, such that x2 is even.

can be expressed symbolically as:

${\displaystyle (\exists x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is even}})}$

This proposition is false.

Example 3
Consider the proposition concerning (z = x'y' + xy):

For any value of x, there exist a value for y, such that z = 1.

can be expressed symbolically as:

${\displaystyle (\forall x)(\exists y)(z=1)}$

This proposition is true. Note that the order of the quantifiers is important. While the above statement is true, the statement

${\displaystyle (\exists y)(\forall x)(z=1)}$

is false. It asserts that there is one value of y which is the same for all x for which z=1. The first statement only asserts that there is a y for each x, but different values of x may have different values of y.

#### Negation

Negation is just a fancy word for the opposite, e.g. The negation of "All named Britney can sing" is "Some named Britney can't sing". What this says is that to disprove that all people named Britney can sing, we only need to find one named Britney who can't sing. To express symbolically:

Let p represent a person named Britney
${\displaystyle [(\forall p)(p{\mbox{ can sing}})]'=(\exists p)(p{\mbox{ cannot sing}})}$

Similarly, to disprove

${\displaystyle (\forall x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is even}})}$

we only need to find one odd number that doesn't satisfy the condition. Three is odd, but 3×3 = 9 is also odd, therefore the proposition is FALSE and

${\displaystyle (\exists x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is odd}})}$

is TRUE

In summary, to obtain the negation of a proposition involving a quantifier, you replace the quantifier by its opposite (e.g. ${\displaystyle \forall }$ with ${\displaystyle \exists }$) and the quantified proposition (e.g. "x is even") by its negation (e.g. "x is odd").

Example 1

${\displaystyle (\forall x)(\exists y)(x(x+1)(x+2)(x+3)+1=y^{2})}$

is a true statement. Its negation is

${\displaystyle (\exists x)(\forall y)(x(x+1)(x+2)(x+3)+1\neq y^{2})}$

## Axioms and Inference

If today's mathematicians were to describe the greatest achievement in mathematics in the 20th century in one word, that word will be abstraction. True to its name, abstraction is a very abstract concept (see Abstraction).

In this chapter we shall discuss the essence of some of the number systems we are familiar with. For example, the real numbers and the rational numbers. We look at the most fundamental properties that, in some sense, define those number systems.

We begin our discussion by looking at some of the more obscure results we were told to be true

• 0 times any number gives you 0
• a negative number multiplied by a negative number gives you a positive number

Most people simply accept that they are true (and they are), but the two results above are simple consequences of what we believe to be true in a number system like the real numbers!

To understand this we introduce the idea of axiomatic mathematics (mathematics with simple assumptions). An axiom is a statement about a number system that we assume to be true. Each number system has a few axioms, from these axioms we can draw conclusions (inferences).

Let's consider the Real numbers, it has axioms Let a, b and c be real numbers

For a, b, and c taken from the real numbers
A1: a+b is a real number also (closure)
A2: There exist 0, such that 0 + a = a for all a (existence of zero - an identity)
A3: For every a, there exist b (written -a), such that a + b = 0 (existence of an additive inverse)
A4: (a + b) + c = a + (b + c) (associativity of addition)
A5: a + b = b + a (commutativity of addition)
For a, b, and c taken from the real numbers excluding zero
M1: ab is a real number also (closure)
M2: There exist an element, 1, such that 1a = a for all a (existence of one - an identity)
M3: For every a there exists a b such that ab = 1
M4: (ab)c = a(bc) (associativity of multiplication)
M5: ab = ba (commutativity of multiplication)
D1: a(b + c) = ab + ac (distributivity)

These are the minimums we assume to be true in this system. These are minimum in the sense that everything else that is true about this number system can be derived from those axioms!

Let's consider the following true identity

(x + y)z = xz + yz

which is not included in the axioms, but we can prove it using the axioms. We proceed:

${\displaystyle {\begin{matrix}(x+y)z&=&z(x+y)\ {\mbox{by M5}}\\&=&zx+zy\ {\mbox{by D1}}\\&=&xz+yz\ {\mbox{by M5}}\\\end{matrix}}}$

Before we proceed any further, you will have notice that the real numbers are not the only numbers that satisfies those axioms! For example the rational numbers also satisfy all the axioms. This leads to the abstract concept of a field. In simple terms, a field is a number system that satisfies all those axiom. Let's define a field more carefully:

A number system, F, is a field if it supports + and × operations such that:

For a, b, and c taken from F
A1: a + b is in F also (closure)
A2: There exist 0, such that 0 + a = a for all a (existence of zero - an identity)
A3: For every a, there exist b (written -a), such that a + b = 0 (existence of an additive inverse)
A4: (a + b) + c = a + (b + c) (associativity of addition)
A5: a + b = b + a (commutativity of addition)
For a, b, and c taken from F with the zero removed (sometimes written F*)
M1: ab is in F (closure)
M2: There exist an element, 1, such that 1a = a for all a (existence of one - the identity)
M3: For every a there exists a b such that ab = 1 (inverses)
M4: (ab)c = a(bc) (associativity of multiplication)
M5: ab = ba (commutativity of multiplication)
D1: a(b + c) = ab + ac (distributivity)

Now, for M3, we do not let b be zero, since 1/0 has no meaning. However for the M axioms, we have excluded zero anyway.

For interested students, the requirements of closure, identity, having inverses and associativity on an operation and a set are known as a group. If F is a group with addition and F* is a group with multiplication, plus the distributivity requirement, F is a field. The above axioms merely state this fact in full.

Note that the natural numbers are not a field, as M3 is generally not satisfied, i.e. not every natural number has an inverse that is also a natural number.

Please note also that (-a) denotes the additive inverse of a, it doesn't say that (-a) = (-1)(a), although we can prove that they are equivalent.

Example 1

Prove using only the axioms that 0 = -0, where -0 is the additive inverse of 0.

Solution 1

0 = 0 + (-0) by A3: existence of inverse
0 = (-0) by A2: 0 + a = a

Example 2

Let F be a field and a an element of F. Prove using nothing more than the axioms that 0a = 0 for all a.

Solution

0 = 0a + (-0a) by A3 existence of inverse
0 = (0 + 0)a + (-0a) by Example 1
0 = (0a + 0a) + (-0a) by distributivity and commutativity of multiplication
0 = 0a + (0a + (-0a)) by associativity of addition
0 = 0a + 0 by A3
0 = 0a by A2.

Example 3

Prove that (-a) = (-1)a.

Solution 3

(-a) = (-a) + 0
(-a) = (-a) + 0a by Example 2
(-a) = (-a) + (1 + (-1))a
(-a) = (-a) + (1a + (-1)a)
(-a) = (-a) + (a + (-1)a)
(-a) = ((-a) + a) + (-1)a
(-a) = 0 + (-1)a
(-a) = (-1)a

One wonders why we need to prove such obvious things (obvious since primary school). But the idea is not to prove that they are true, but to practise inferencing, how to logically join up arguments to prove a point. That is a vital skill in mathematics.

### Exercises

1. Describe a field in which 1 = 0

2. Prove using only the axioms if u + v = u + w then v = w (subtracting u from both sides is not accepted as a solution)

3. Prove that if xy = 0 then either x = 0 or y = 0

4. In F-, the operation + is defined to be the difference of two numbers and the × operation is defined to be the ratio of two numbers. E.g. 1 + 2 = -1, 5 + 3 = 2 and 9×3 = 3, 5×2; = 2.5. Is F- a field?

5. Explain why Z6 (modular arithmetic modular 6) is not a field.

## Problem Set

1. Prove

${\displaystyle {\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+...+{\frac {1}{\sqrt {n}}}\geq {\sqrt {n}}}$

for ${\displaystyle n\geq 1}$

2. Prove by induction that ${\displaystyle 2n^{3}-3n^{2}+n+31\geq 0}$

3. Prove by induction

${\displaystyle {n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}}$

where

${\displaystyle {n \choose m}={\frac {n!}{m!(n-m)!}}}$ and ${\displaystyle n!=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 2\cdot 1}$
and 0! = 1 by definition.

4. Prove by induction ${\displaystyle {n \choose 0}+2{n \choose 1}+2^{2}{n \choose 2}+...+2^{n}{n \choose n}=3^{n}}$

5. Prove that if x and y are integers and n an odd integer then ${\displaystyle {\frac {x^{n}+y^{n}}{x+y}}}$ is an integer.

6. Prove that (n~m) = n!/((n-m)!m!) is an integer. Where n! = n(n-1)(n-2)...1. E.g. 3! = 3×2×1 = 6, and (5~3) = (5!/3!)/2! = 10.

Many questions in other chapters require you to prove things. Be sure to try the techniques discussed in this chapter.

# Feedback

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

# =Exercises

## Mathematical proofs

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.

If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

### Mathematical induction exercises

1.

Prove that 12 + 22 + ... + n2 = n(n+1)(2n+1)/6
When n=1,
L.H.S. = 12 = 1
R.H.S. = 1*2*3/6 = 6/6 = 1
Therefore L.H.S. = R.H.S.
Therefore this is true when n=1.
Assume that this is true for some positive integer k,
i.e. 12 + 22 + ... + k2 = k(k+1)(2k+1)/6
${\displaystyle {\begin{matrix}1^{2}+2^{2}+3^{2}+...+k^{2}&=&{\frac {k(k+1)(2k+1)}{6}}\\1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}&=&{\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}\\\ &=&{\frac {1}{6}}(k+1)\left[k(2k+1)+6(k+1)\right]\\\ &=&{\frac {1}{6}}(k+1)\left[2k^{2}+7k+6\right]\\\ &=&{\frac {(k+1)(k+2)(2k+3)}{6}}\end{matrix}}}$
Therefore this is also true for k+1.
Therefore, by the principle of mathematical induction, this holds for all positive integer n.

2.

Prove that for n ≥ 1,
${\displaystyle (1+{\sqrt {5}})^{n}=x_{n}+y_{n}{\sqrt {5}}}$
where xn and yn are integers.
When n=1,
${\displaystyle 1+{\sqrt {5}}=x_{1}+y_{1}{\sqrt {5}}}$
Therefore x1=1 and y1=1, which are both integers.
Therefore this is true when n=1.
Assume that this is true for some positive integer k,
i.e. ${\displaystyle (1+{\sqrt {5}})^{k}=x_{k}+y_{k}{\sqrt {5}}}$ where xk and yk are integers.
${\displaystyle {\begin{matrix}(1+{\sqrt {5}})^{k}&=&x_{k}+y_{k}{\sqrt {5}}\\(1+{\sqrt {5}})^{k+1}&=&(x_{k}+y_{k}{\sqrt {5}})(1+{\sqrt {5}})\\\ &=&x_{k}+y_{k}{\sqrt {5}}+x_{k}{\sqrt {5}}+5y_{k}\\\ &=&(x_{k}+5y_{k})+(x_{k}+y_{k}){\sqrt {5}}\end{matrix}}}$
Because xk and yk are both integers, therefore xk + 5yk and xk + yk are integers also.
Therefore this is true for k+1 also.
Therefore, by the principle of mathematical induction, this holds for all positive integer n.

3. (The solution assume knowledge in binomial expansion and summation notation)

Note that
${\displaystyle \sum _{i=1}^{n}[i^{k}-(i-1)^{k}]=n^{k}}$
Prove that there exists an explicit formula for
${\displaystyle \sum _{i=1}^{n}i^{m}}$ for all integer m. E.g.
${\displaystyle 1^{3}+2^{3}+...+n^{3}={\frac {n^{2}(n+1)^{2}}{4}}}$
It's clear that 11 + 21 + ... = (n+1)n/2. So the proposition is true for m=1.
Suppose that
${\displaystyle \sum _{i=1}^{n}i^{j}}$
has an explicit formula in terms of n for all j < k (**), we aim to prove that
${\displaystyle \sum _{i=1}^{n}i^{k}}$
also has an explicit formula.
Starting from the property given, i.e.
${\displaystyle \sum _{i=1}^{n}[i^{k+1}-(i-1)^{k+1}]=n^{k+1}}$
${\displaystyle \sum _{i=1}^{n}[i^{k+1}-\sum _{j=0}^{k+1}{k+1 \choose j}i^{j}]=n^{k+1}}$
${\displaystyle \sum _{i=1}^{n}[i^{k+1}-{k+1 \choose k+1}i^{k+1}-\sum _{j=0}^{k}{k+1 \choose j}i^{j}]=n^{k+1}}$
${\displaystyle \sum _{i=1}^{n}[\sum _{j=0}^{k}{k+1 \choose j}i^{j}]=n^{k+1}}$
${\displaystyle \sum _{j=0}^{k}[\sum _{i=1}^{n}{k+1 \choose j}i^{j}]=n^{k+1}}$
${\displaystyle \sum _{j=0}^{k}[{k+1 \choose j}\sum _{i=1}^{n}i^{j}]=n^{k+1}}$
Since we know the formula for power sum of any power less then k (**), we can solve the above equation and find out the formula for the k-th power directly.
Hence, by the principle of strong mathematical induction, this proposition is true.

#### Additional info for question 3

The method employed in question 3 to find out the general formula for power sum is called the method of difference, as shown by that we consider the sum of all difference of adjacant terms.

Aside from the method above, which lead to a recursive solution for finding the general formula, there're also other methods, such as that of using generating function. Refer to the last question in the generating function project page for detail.

## Mathematical Proofs Problem Set

1.

For all
${\displaystyle {\begin{matrix}a&>&0\\n+a&>&n\\n&>&n-a\\{\sqrt {n}}&>&{\sqrt {n-a}}\\1&>&{\frac {\sqrt {n-a}}{\sqrt {n}}}\\{\frac {1}{\sqrt {n-a}}}&>&{\frac {1}{\sqrt {n}}}\end{matrix}}}$
Therefore ${\displaystyle {\frac {1}{\sqrt {1}}}}$ , ${\displaystyle {\frac {1}{\sqrt {2}}}}$ , ${\displaystyle {\frac {1}{\sqrt {3}}}}$... ${\displaystyle >{\frac {1}{\sqrt {n}}}}$
When a>b and c>d, a+c>b+d ( See also Replace it if you find a better one).
Therefore we have:
${\displaystyle {\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>n\times {\frac {1}{\sqrt {n}}}}$
${\displaystyle {\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>{\frac {n}{\sqrt {n}}}\times {\frac {\sqrt {n}}{\sqrt {n}}}}$
${\displaystyle {\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>{\frac {n{\sqrt {n}}}{n}}}$
${\displaystyle {\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}......+{\frac {1}{\sqrt {n}}}>{\sqrt {n}}}$

3.

Let us call the proposition
${\displaystyle {n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}}$ be P(n)
Assume this is true for some n, then
${\displaystyle {n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}}$
${\displaystyle 2\times \left\{{n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose 2}\right\}=2^{n+1}}$
${\displaystyle \left\{{n \choose 0}+{n \choose n}\right\}+\left\{{n \choose 0}+2{n \choose 1}+2{n \choose 2}+...+2{n \choose n-1}+{n \choose n}\right\}=2^{n+1}}$
${\displaystyle \left\{{n \choose 0}+{n \choose n}\right\}+\left\{{n \choose 0}+{n \choose 1}\right\}+\left\{{n \choose 1}+{n \choose 2}\right\}+\left\{{n \choose 2}+{n \choose 3}\right\}+...+\left\{{n \choose n-1}+{n \choose n}\right\}=2^{n+1}}$
Now using the identities of this function:${\displaystyle {n \choose a}+{n \choose a+1}={n+1 \choose a+1}}$(Note:If anyone find wikibooks ever mentioned this,include a link here!),we have:
${\displaystyle \left\{{n \choose 0}+{n \choose n}\right\}+{n+1 \choose 1}+{n+1 \choose 2}+{n+1 \choose 3}+...+{n+1 \choose n}=2^{n+1}}$
Since ${\displaystyle {n \choose 0}={n \choose n}=1}$ for all n,
${\displaystyle {n+1 \choose 0}+{n+1 \choose n+1}+{n+1 \choose 1}+{n+1 \choose 2}+{n+1 \choose 3}+...+{n+1 \choose n}=2^{n+1}}$
${\displaystyle {n+1 \choose 0}+{n+1 \choose 1}+{n+1 \choose 2}+{n+1 \choose 3}+...+{n+1 \choose n}+{n+1 \choose n+1}=2^{n+1}}$
Therefore P(n) implies P(n+1), and by simple substitution P(0) is true.
Therefore by the principal of mathematical induction, P(n) is true for all n.

Alternate solution
Notice that

${\displaystyle (a+b)^{n}={n \choose 0}a^{n}+{n \choose 1}a^{n-1}b+\cdots +{n \choose n}b^{n}}$

letting a = b = 1, we get

${\displaystyle (1+1)^{n}=2^{n}={n \choose 0}+{n \choose 1}+\cdots +{n \choose n}}$

as required.

5.

Let ${\displaystyle P(x)=x^{n}+y^{n}\,}$ be a polynomial with x as the variable, y and n as constants.
${\displaystyle {\begin{matrix}P(-y)&=&(-y)^{n}+y^{n}\\\ &=&-y^{n}+y^{n}({\mbox{When n is an odd integer}})\\\ &=&0\end{matrix}}}$
Therefore by factor theorem(link here please), (x-(-y))=(x+y) is a factor of P(x).
Since the other factor, which is also a polynomial, has integer value for all integer x,y and n (I've skipped the part about making sure all coeifficients are of integer value for this moment), it's now obvious that
${\displaystyle {\frac {x^{n}+y^{n}}{x+y}}}$ is an integer for all integer value of x,y and n when n is odd.

# Infinity and infinite processes

## Introduction

As soon as a child first learns about numbers, they become interested in big ones, a million, a billion, a trillion. They even make up their own, a zillion etc. One of the first mathematical questions a child asks is "what is the largest number?" This will often lead to a short explanation that there are infinitely many numbers.

But there are many different types of infinity - in fact, there are infinite types of infinity! This chapter will try to explain what some of these types mean and the differences between them.

## Finite and Infinite Sets

There was once a mathematician called Georg Cantor who created a new branch of mathematics called set theory in the late 19th century. Set theory involves collections of numbers or objects. Here's a set:

${\displaystyle \{1,2,3,4,5\}}$

This set consists of five elements, namely the first five natural numbers. Now consider the set:

${\displaystyle \{6,7,8,9,10\}}$

Are these sets of the same size? Yes, they are. This is because they both have five elements. As we will see later, this method of comparing sizes does not work for all sets. An alternate method for comparing set sizes is to match elements of sets in a one-one fashion.

Think of a small child who wants to compare the number of marbles she has with her brother's collection. Let's say she doesn't know how to count beyond ten. She can still compare the sizes of their collections of marbles by lining up their marbles in two parallel lines. The line on the left contains her marbles while the one on the right contains her brother's. If each marble on the left is aligned with exactly one marble on the right, then they both have the same number of marbles.

We can use the same idea to compare infinite sets. If we can find a way to pair up one member of set A with one member of set B, and if there are no members of A without a partner in B and vice versa then we can say that set A and set B have the same number of members. Formally, two sets ${\displaystyle A}$ and ${\displaystyle B}$ are of the same size if there is a function ${\displaystyle f}$ such that for every ${\displaystyle a}$ in ${\displaystyle A}$, we have ${\displaystyle f(a)}$ in ${\displaystyle B}$ and moreover, for every ${\displaystyle b}$ in ${\displaystyle B}$, there exists an ${\displaystyle a}$ in ${\displaystyle A}$ such that ${\displaystyle f(a)=b}$.

#### Example

Consider our previous example. We want to know if the sets ${\displaystyle \{1,2,3,4,5\}}$ and ${\displaystyle \{6,7,8,9,10\}}$ have the same size. We can create the following matching.

 1 6 2 7 3 8 4 9 5 10

#### Example

Let Set N be all counting numbers. N is called the set of natural numbers. 1,2,3,4,5,6,... and so on. Let Set B be the negative numbers -1,-2,-3, ... and so on. Can the members of N and B be paired up? The formal way of saying this is "Can A and B be put into a one to one correspondence"?

Obviously the answer is yes. 1 in set N corresponds with -1 in B. Likewise:

N   B
1   -1
2   -2
3   -3

and so on. Here, the one-one function that maps from A to B is ${\displaystyle f(x)=-x}$.

So useful is the set of counting numbers that any set that can be put into a one to one correspondence with it is said to be countably infinite.

#### Example

The set of integers is the set containing all elements from the set N, the set B and the element 0. That is

{... -3,-2,-1, 0, 1, 2, 3, ...}

The set of integers is usually denoted by Z. Note that N the set of natural numbers is a subset of Z. All members of N are in Z, but not all members of Z are in N.

Is the set of integers countably infinite? In other words, can the set of integers be put in one-one correspondence with the set of all natural numbers?

Since the set N is contained in the set Z, we may be tempted to declare that these two sets are not of the same size. However, we can

Z   N
0   1
-1   2
1   3
-2   4

and so on. We can write this one-one correspondence as a function

${\displaystyle f(x)=\left\{{\begin{array}{cl}{\frac {x-1}{2}}&x{\text{ is odd}}\\{\frac {-x}{2}}&x{\text{ is even}}\end{array}}\right.}$

We can verify that this function generates all the integers in Z from the natural numbers in N.

Strange indeed! A subset of Z (namely the natural numbers) has the same size as Z itself! Infinite sets are not like ordinary finite sets. In fact this is sometimes used as a definition of an infinite set. An infinite set is any set which can be put into a one to one correspondence with at least one of its subsets. Rather than saying "The number of members" of a set, people sometimes use the word cardinality or cardinal value. Z and N are said to have the same cardinality.

#### Exercises

1. Is the number of even numbers the same as the natural numbers?
2. What about the number of square numbers?
3. Is the cardinality of positive even numbers less than 100 equal to the cardinality of natural numbers less than 100? Which set is bigger? How do you know? In what ways do finite sets differ from infinite ones?

### Is the set of rational numbers bigger than N?

In this section we will look to see if we can find a set that is bigger than the countable infinity we have looked at so far. To illustrate the idea we can imagine a story.

There was once a criminal who went to prison. The prison was not a nice place so the poor criminal went to the prison master and pleaded to be let out. She replied:

"Oh all right - I'm thinking of a number, every day you can have a go at guessing it. If you get it correct, you can leave."

Now the question is - can the criminal get himself out of jail? (Think about if for a while before you read on)

Obviously it depends on the number. If the prison master chooses a natural number, then the criminal guesses 1, the first day, 2,the second day and so on until he reaches the correct number. Likewise for the integers 0 on the first day, -1 on the second day. 1 on the third day and so on. If the number is very large then it may take a long time to get out of prison but get out he will.

What the prison master needs to do is choose a set that is not countable in this way. Think of a number line. The integers are widely spaced out. There are plenty of numbers in between the integers 0 and 1 for example. So we need to look at denser sets. The first set that springs to most peoples mind are the fractions. There are an infinite number of fractions between 0 and 1 so surely there are more fractions than integers? Is it possible to count fractions? Let's think about that possibility for a while. If we try to use the approach of counting all the fractions between 0 & 1 then go on to 1 - 2 and so on we will come unstuck because we will never finish counting the ones up to 1 ( there are an infinite number of them). But does this mean that they are uncountable ? Think of the situation with the integers. Ordering them ...-2, -1, 0, 1, 2, ... renders them impossible to count, but reordering them 0, -1, 1, -2, 2, ... allows them to be counted.

There is in fact a way of ordering fractions to allow them to be counted. Before we go on to it let's revert to the normal mathematical language. Mathematicians use the term rational number to define what we have been calling fractions. A rational number is any number that can be written in the form p/q where p and q are integers. So 3/4 is rational, as is -1/2. The set of all rational numbers is usually called Q. Note that Z is a subset of Q because any integer can be divided by 1 to make it into a rational. E.g. the number 3 can be written in the form p/q as 3/1.

Now as all the numbers in Q are defined by two numbers p and q it makes sense to write Q out in the form of a table.

${\displaystyle {\begin{matrix}{\frac {1}{1}}&{\frac {1}{2}}&{\frac {1}{3}}&\cdots \\&&\\{\frac {2}{1}}&{\frac {2}{2}}&{\frac {2}{3}}&\cdots \\&&\\{\frac {3}{1}}&{\frac {3}{2}}&{\frac {3}{3}}&\cdots \\\vdots &\vdots &\vdots &\ddots \end{matrix}}}$

Note that this table isn't an exact representation of Q. It only has the positive members of Q and has a number of multiple entries.( e.g. 1/1 and 2/2 are the same number) We shall call this set Q'. It is simple enough to see that if Q' is countable then so is Q.

So how do we go about counting Q'? If we try counting the first row then the second and so on we will fail because the rows are infinite in length. Likewise if we try to count columns. But look at the diagonals. In one direction they are infinite ( e.g. 1/1, 2/2, 3/3, ...) but in the other direction they are finite. So this set is countable. We count them along the finite diagonals, 1/1, 1/2, 2/1, 1/3, 2/2, 3/1....

#### Exercises

1. Adapt the method of counting the set Q' to show that the set Q is also countable. How will you include 0 and the negative rationals? How will you solve the problem of multiple entries representing the same number ?
2. Show that ${\displaystyle \infty \times \infty =\infty }$ (provided that the infinites are both countable)

### Can we find any sets that are bigger than N?

So far we have looked at N, Z, and Q and found them all to be the same size, even though N is a subset of Z which is a subset of Q. You might be beginning to think "Is that it? Are all infinities the same size?" In this section we will look at a set that is bigger than N. A set that cannot be put into a one to one correspondence with N, no matter how it is arranged.

The set in question is R: the real numbers. A real number is any number on the number line. Remember that the set Q contains all the numbers that can be written in the form p/q with p and q integers, q different from 0. Most real numbers can never be put in this form and they are named "irrational numbers". Examples of irrational numbers include ${\displaystyle \pi }$, ${\displaystyle e,}$ and ${\displaystyle {\sqrt {2}}}$.

The set R is huge! Much bigger than Q. To get a feel for the different sizes of these two infinite sets consider the decimal expansions of a real number and a rational number. Rational numbers always either terminate:

• 1/8 = 0.125

or repeat:

• 1/9 = 0.1111111......

Imagine measuring an object such as a book. If you use a ruler you might get 10cm. If you take a bit more care to and read the mm you might get 10.2cm. You'd then have to go on to more accurate measuring devices such as vernier micrometers and find that you get 10.235cm. Going onto a travelling microscope you may find its 10.235823cm and so on. In general the decimal expansion of any real measurement will be a list of digits that look completely random.

Now imagine you measure a book and found it to be 10.101010101010cm. You'd be pretty surprised wouldn't you? But this is exactly the sort of result you would need to get if the book's length were rational. Rational numbers are dense (you find them all over the number line), infinite, yet much much rarer than real numbers.

### How we can prove that R is bigger than Q

It's good to get a feel for the size of infinities as in the previous section. But to be really sure we have to come up with some form of proof. In order to prove that R is bigger than Q we use a classic method. We assume that R is the same size as Q and come up with a contradiction. For the sake of clarity we will restrict our proof to the real numbers between 0 and 1.We will call this set R'. Clearly if we can prove that R' is bigger than Q then R must be bigger than Q also.

If R' was the same size as Q it would mean that it is countable. This means that we would be able to write out some form of list of all the members of R' (This is what countable means, so far we have managed to write out all our infinite sets in the form of an infinitely long list). Let's consider this list.

R1
R2
R3
R4
.
.
.

Where R1 is the first number in our list, R2 is the second, and so on. Note that we haven't said what order the list is to be written. For this proof we don't need to say what the order of the list needs to be, only that the members of R are listable (hence countable).

Now lets write out the decimal expansion of each of the numbers in the list.

0.r11r12r13r14...
0.r21r22r23r24...
0.r31r32r33r44...
0.r41r42r43r44...
.
.
.

Here r11 means the first digit after the decimal point of the first number in the list. So if our first number happened to be 0.36921... r11 would be 3, r12 would be 6 and so on. Remember that this list is meant to be complete. By that we mean that it contains every member of R'. What we are going to do in order to prove that R is not countable is to construct a number in R' that is not already on the list. Since the list is supposed to contain every member of R', this will cause a contradiction and therefore show that R' is unlistable.

In order to construct this unlisted number we choose a decimal representation:

0.a1a2a3a4...

Where a1 is the first digit after the point etc.

We let a1 take any value from 0 - 9 inclusive except the digit r11. So if r11 = 3 then a1 can be 0, 1, 2, 4, 5, 6, 7, 8, or 9. Then we let a2 be any digit except r22 (the second digit of the second number on the list). Then a3 be any digit except r33 and so on.

Now if this number, that we have just constructed were on the list somewhere then it would have to be equal to Rsomething. Let's see what Rsomething it might be equal to. It can't be equal to R1 because it has a different first digit (r11 and a1. Nor can it be equal to R2 because it has a different second digit, and so on. In fact it can't be equal to any number on the list because it differs by at least one digit from all of them.

We have done what we set out to do. We have constructed a number that is in R' but is not on the list of all members of R'. This contradiction means that R' is bigger than any list. It is not listable. It is not countable. It is a bigger infinity than Q.

### Are there even bigger infinities?

There are but they are difficult to describe. The set of all the possible combinations of any number of real numbers is a bigger infinity than R. However trying to imagine such a set is mind boggling. Let's look instead at a set that looks like it should be bigger than R but turns out not to be.

Remember R', which we defined earlier on as the set of all numbers on the number line between 0 and 1. Let us now consider the set of all numbers in the plane from [0,0] to [1,1]. At first sight it would seem obvious that there must be more points on the whole plane than there are in a line. But in transfinite mathematics the "obvious" is not always true and proof is the only way to go. Cantor spent three years trying to prove it true but failed. His reason for failure was the best possible. It's false.

Each point in this plane is specified by two numbers, the x coordinate and the y coordinate; x and y both belong to R. Lets consider one point in the line. 0.a1a2a3a4.... Can you think of a way of using this one number to specify a point in the plane ? Likewise can you think of a way of combining the two numbers x= 0.x1x2x3x4.... and y= 0.y1y2y3y4.... to specify a point on the line? (think about it before you read on)

One way is to do it is to take

a1 = x1
a2 = y1
a3 = x2
a4 = y2
.
.
.

This defines a one to one correspondence between the points in the plane and the points in the line. (Actually, for the sharp amongst you, not quite one to one. Can you spot the problem and how to cure it?)

#### Exercises

1. Prove that the number of points in a cube is the same as the number of points on one of its sides.

### Continuum hypothesis

We shall end the section on infinite sets by looking at the Continuum hypothesis. This hypothesis states that there are no infinities between the natural numbers and the real numbers. Cantor came up with a number system for transfinite numbers. He called the smallest infinity ${\displaystyle \aleph _{0}}$ with the next biggest one ${\displaystyle \aleph _{1}}$ and so on. It is easy to prove that the cardinality of N is ${\displaystyle \aleph _{0}}$ (Write any smaller infinity out as a list. Either the list terminates, in which case it's finite, or it goes on forever, in which case it's the same size as N) but is the cardinality of the reals = ${\displaystyle \aleph _{1}}$?

To put it another way, the hypotheses states that:

There are no infinite sets larger than the set of natural numbers but smaller than the set of real numbers.

The hypothesis is interesting because it has been proved that "It is not possible to prove the hypothesis true or false, using the normal axioms of set theory"

If you want to learn more about set theory or infinite sets try one of the many interesting pages on our sister project en:wikipedia.

## Limits Infinity got rid of

The theory of infinite sets seems weird to us in the 21st century, but in Cantor's day it was downright unpalatable for most mathematicians. In those days the idea of infinity was too troublesome, they tried to avoid it wherever possible.

Unfortunately the mathematical topic called analysis was found to be highly useful in mathematics, physics, engineering. It was far too useful a field to simply drop yet analysis relies on infinity or at least infinite processes. To get around this problem the idea of a limit was invented.

Consider the series

${\displaystyle {\frac {1}{1}},{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}},\cdots ,{\frac {1}{n}}\cdots }$

This series is called the harmonic series.

Note that the terms of the series get smaller and smaller as you go further and further along the series. What happens if we let n become infinite? The term would become ${\displaystyle {\frac {1}{\infty }}}$

But this doesn't make sense. (Mathematicians consider it sloppy to divide by infinity. Infinity is not a real number, you can't divide by it). A better way to think about it (The way you probably already do think about it, if you've ever considered the matter) is to take this approach: Infinity is very big, bigger than any number you care to think about. So let's let n become bigger and bigger and see if 1/n approaches some fixed number. In this case as n gets bigger and bigger 1/n gets smaller and smaller. So it is reasonable to say that the limit is 0.

In mathematics we write this as

${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}=0}$

the limit of 1/n as n approaches infinity is zero

Note that we are not dividing 1 by infinity and getting the answer 0. We are letting the number n get bigger and bigger and so the reciprocal gets closer and closer to zero. Those 18th Century mathematicians loved this idea because it got rid of the pesky idea of dividing by infinity. At all times n remains finite. Of course, no matter how huge n is, 1/n will not be exactly equal to zero, there is always a small difference. This difference (or error) is usually denoted by ε (epsilon).

### info -- infinitely small

When we talk about infinity, we think of it as something big. But there is also the infinitely small, denoted by ε (epsilon). This animal is closer to zero than any other number. Mathematicians also use the character ε to represent anything small. For example, the famous Hungarian mathematician Paul Erdos used to refer to small children as epsilons.

### Examples

Lets look at the function

${\displaystyle {\frac {x^{2}+x}{x^{2}}}}$

What is the limit as x approaches infinity ?

This is where the idea of limits really come into its own. Just replacing x with infinity gives us very little:

${\displaystyle \ {\frac {\infty ^{2}+\infty }{\infty ^{2}}}=?}$

But by using limits we can solve it

${\displaystyle \lim _{x\to \infty }{\frac {x^{2}+x}{x^{2}}}=1+\lim _{x\to \infty }{\frac {1}{x}}=1}$

For our second example consider this limit as x approaches infinity of ${\displaystyle x^{3}-x^{2}}$

Again lets look at the wrong way to do it. Substituting ${\displaystyle x=\infty }$ into the expression gives ${\displaystyle \infty ^{3}-\infty ^{2}}$. Note that you cannot say that these two infinities just cancel out to give the answer zero.

Now lets look at doing it the correct way, using limits

${\displaystyle \lim _{x\to \infty }x^{3}-x^{2}=\lim _{x\to \infty }x^{2}(x-1)=\infty }$

The last expression is two functions multiplied together. Both of these functions approach infinity as x approaches infinity, so the product is infinity also. This means that the limit does not exist, i.e. there is no finite number that the function approaches as x gets bigger and bigger.

One more just to get you really familiar with how it works. Calculate:

${\displaystyle \lim _{x\to \infty }{\frac {\sin x}{x}}}$

To make things very clear we shall rewrite it as

${\displaystyle \lim _{x\to \infty }{\frac {1}{x}}(\sin x)}$

Now to calculate this limit we need to look at the properties of sin(x). Sin(x)is a function that you should already be familiar with (or you soon will be) its value oscillates between 1 and -1 depending on x. This means that the absolute value of sin(x) (the value ignoring the plus or minus sign) is always less than or equal to 1:

${\displaystyle |\sin x|\leq 1}$

So we have 1/x which we already know goes to zero as x goes to infinity multiplied by sin(x) which always remains finite no matter how big x gets. This gives us

${\displaystyle \lim _{x\to \infty }{\frac {1}{x}}(\sin x)=0}$

### Exercises

Evaluate the following limits;

1. ${\displaystyle \lim _{x\to \infty }{\frac {3x^{2}-4}{2x^{2}+x}}}$
2. ${\displaystyle \lim _{x\to \infty }{\frac {x^{2}-1}{2x^{3}+3}}}$
3. ${\displaystyle \lim _{x\to \infty }{\frac {cosx}{x^{2}}}}$
4. ${\displaystyle \lim _{x\to \infty }(2x^{2}-x^{4})}$

## Infinite series

Consider the infinite sum 1/1 + 1/2 + 1/4 + 1/8 + 1/16 + .... Do you think that this sum will equal infinity once all the terms have been added ? Let's sum the first few terms.

${\displaystyle {\begin{matrix}S_{1}&=&{\frac {1}{1}}&=&1\\S_{2}&=&{\frac {1}{1}}+{\frac {1}{2}}&=&1.5\\S_{3}&=&{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{4}}&=&1.75\\S_{4}&=&{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}&=&1.8750\\\end{matrix}}}$

Can you guess what ${\displaystyle S_{\infty }}$ is ?

Here is another way of looking at it. Imagine a point on a number line moving along as the sum progresses. In the first term the point jumps to the position 1. This is half way from 0 to 2. In the second stage the point jumps to position 1.5 - half way from 1 to 2. At each stage in the process (shown in a different colour on the diagram) the distance to 2 is halved. The point can get as close to the point 2 as you like. You just need to do the appropriate number of jumps, but the point will never actually reach 2 in a finite number of steps. We say that in the limit as n approaches infinity, Sn approaches 2.

The ancient Greeks had a big problem with summing infinite series. A famous paradox from the philosopher Zeno is as follows:

In the paradox of Achilles and the tortoise, we imagine the Greek hero Achilles in a footrace with the plodding reptile. Because he is so fast a runner, Achilles graciously allows the tortoise a head start of a hundred feet. If we suppose that each racer starts running at some constant speed (one very fast and one very slow), then after some finite time, Achilles will have run a hundred feet, bringing him to the tortoise's starting point.

During this time, the tortoise has "run" a (much shorter) distance, say one foot. It will then take Achilles some further period of time to run that distance, during which the tortoise will advance farther; and then another period of time to reach this third point, while the tortoise moves ahead. Thus, whenever Achilles reaches somewhere the tortoise has been, he still has farther to go. Therefore, Zeno says, swift Achilles can never overtake the tortoise.

# Feedback

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

## Set Theory and Infinite Processes

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.

If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

These solutions were not written by the author of the rest of the book. They are simply the answers I thought were correct while doing the exercises. I hope these answers are useful for someone and that people will correct my work if I made some mistakes

### How big is infinity? exercises

1. The number of even numbers is the same as the number of natural numbers because both are countably infinite. You can clearly see the one to one correspondence. (E means even numbers and is not an official set like N)
E   N
2   1
4   2
6   3
8   4

2. The number of square numbers is also equal to the number of natural numbers. They are both countably infinite and can be put in one to one correspondence. (S means square numbers and is not an official set like N)

S   N
1   1
4   2
9   3
16   4

3. The cardinality of even numbers less than 100 is not equal to the cardinality of natural numbers less than 100. You can simply write out both of them and count the numbers. Then you will see that cardinality of even numbers less than 100 is 49 and the cardinality of natural numbers less than 100 is 99. Thus the set of natural numbers less than 100 is bigger than the set of even numbers less than 100. The big difference between infinite and finite sets thus is that a finite set can not be put into one to one correspondence with any of its subsets, while an infinite set can be put into one to one correspondence with at least one of its subsets.
4. Each part of the sum is answered below

infinity + 1 = infinity
You can prove this by taking a set with a cardinality of 1, for example a set consisting only of the number 0. You simply add this set in front of the countably infinite set to put the infinite set and the inifinite+1 set into one to one correspondence.
N   N+1
1   0
2   1
3   2
4   3
infinity + A = infinity (where A is a finite set)
You simply add the finite set in front of the infinite set like above, only the finite set doesn't need to have a cardinality of one anymore.
infinity + C = infinity (where C is a countably infinite set)
You take one item of each set (infinity or C) in turns, this will make the new list also countably infinite.

### Is the set of rational numbers bigger than N? exercises

1. To change the matrix from Q' to Q the first step you need to take is to remove the multiple entries for the same number. You can do this by leaving an empty space in the table when gcd(topnr,bottomnr)≠1 because when the gcd isn't 1 the fraction can be simplified by dividing the top and bottom number by the gcd. This will leave you with the following table.

${\displaystyle {\begin{matrix}{\frac {1}{1}}&{\frac {1}{2}}&{\frac {1}{3}}&\cdots \\&&\\{\frac {2}{1}}&&{\frac {2}{3}}&\cdots \\&&\\{\frac {3}{1}}&{\frac {3}{2}}&&\cdots \\\vdots &\vdots &\vdots &\ddots \end{matrix}}}$

Now we only need to add zero to the matrix and we're finished. So we add a vertical row for zero and only write the topmost element in it (0/1) (taking gcd doesn't work here because gcd(0,a)=a) This leaves us with the following table where we have to count all fractions in the diagonal rows to see that Q is countably infinite.

${\displaystyle {\begin{matrix}{\frac {0}{1}}&{\frac {1}{1}}&{\frac {1}{2}}&{\frac {1}{3}}&\cdots \\&&\\&{\frac {2}{1}}&&{\frac {2}{3}}&\cdots \\&&\\&{\frac {3}{1}}&{\frac {3}{2}}&&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{matrix}}}$

2. To show that ${\displaystyle \infty \times \infty =\infty }$ you have to make a table where you put one infinity in the horizontal row and one infinity in the vertical row. Now you can start counting the number of place in the table diagonally just like Q' was counted. This works because a table of size AxB contains A*B places.

### Are there even bigger infinities? exercises

1. You have to use a method to map the coordinates in a plain onto a point on the line and the other way around, like the one described in the text. This method shows you that for every number on the line there is a place on the plain and for every place on the plain there is a place on the line. Thus the number of points on the line and the plain are the same.

## Problem set

HSE PS Infinity and infinite processes

# Counting and Generating functions

Before we begin: This chapter assumes knowledge of

1. Ordered selection (permutation) and unordered selection (combination) covered in Basic counting,
2. Method of Partial Fractions and,
3. Competence in manipulating Summation Signs

..more to come

## Generating functions

..some motivation to be written

To understand this section you need to see why this is true:

${\displaystyle \lim _{x\to \infty }{\frac {x^{2}+x}{x^{2}}}=1+\lim _{x\to \infty }{\frac {1}{x}}=1}$