High School Mathematics Extensions/Print version
This is the print version of High_School_Mathematics_Extensions You won't see this message or any elements not part of the book's content when you print or preview this page. 
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 >
Contents....
Primes and modular arithmetic
Primes
HSME 
Content 

Primes 
Modular Arithmetic 
Problems & Projects 
Problem Set 
Project 
Solutions 
Exercise Solutions 
Problem Set Solutions 
Misc. 
Definition Sheet 
Full Version 
PDF Version 
Introduction
A prime number (or prime for short) is a natural number that has exactly two divisors: itself and the number 1. Since 1 has only one divisor — itself — we do not consider it to be a prime number but a unit. So, 2 is the first prime, 3 is the next prime, but 4 is not a prime because 4 divided by 2 equals 2 without a remainder. We've proved 4 has three divisors: 1, 2, and 4. Numbers with more than two divisors are called composite numbers.
The first 20 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71.
Primes are an endless source of fascination for mathematicians. Some of the problems concerning primes are so difficult that even decades of work by some of the most brilliant mathematicians have failed to solve them. One such problem is Goldbach's conjecture, which proposes that all even numbers greater than 3 can be expressed as the sum of two primes. No one has been able to prove it true or false.
This chapter will introduce some of the elementary properties of primes and their connection to an area of mathematics called modular arithmetic.
Geometric meaning of primes
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
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 nonobvious 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
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
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
 not a whole number, so 2 is not a factor of 21
 hence 3 and 7 are the factors of 21.
Example 2
 hence 2 is not a factor of 153
 hence 3 and 51 are factors of 153
 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
 hence 11, 11 and 17 are the prime factors of 2057.
Exercise
Fun Fact — Is this prime?
Interestingly, there is an efficient way of determining whether a number is prime with 100% accuracy with the help of a computer.
2, 5 and 3
The primes 2, 5, and 3 hold a special place in factorization. Firstly, all even numbers have 2 as one of their prime factors. Secondly, all numbers whose last digit is 0 or 5 can be divided wholly by 5.
The third case, where 3 is a prime factor, is the focus of this section. The underlying question is: is there a simple way to decide whether a number has 3 as one of its prime factors?
Theorem — Divisibility by 3
A number is divisible by 3 if and only if the sum of its digits is divisible by 3
For example, 272 is not divisible by 3, because 2 + 7 + 2 = 11, which is not divisible by 3.
945 is divisible by 3, because 9 + 4 + 5 = 18. And 18 is divisible by 3. In fact 945 / 3 = 315
Is 123456789 divisible by 3?
 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = (1 + 9) × 9 / 2 = 45
 4 + 5 = 9
Nine is divisible by 3, therefore 45 is divisible by 3, therefore 123456789 is divisible by 3!
The beauty of the theorem lies in its recursive nature. A number is divisible by 3 if and only if the sum of its digits is divisible by 3. How do we know whether the sum of its digits is divisible by 3? Apply the theorem again!
info — Recursion
A prominent computer scientist once said "To iterate is human, to recurse, divine." But what does it mean to recurse? Before that, what is to iterate?
"To iterate" simply means doing the same thing over and over again, and computers are very good at that. An example of iteration in mathematics is the exponential operation, e.g. x^{n} means doing x times x times x times x...n times. That is an example of iteration.
Thinking about iteration economically (in terms of mental resources), by defining a problem in terms of itself, is "to recurse". To recursively represent x^{n}, we write:
 if n equals 0.
 if n > 0
What is 9^{9}? It is 9 times 9 ^{8}. But, 9^{8} is 9 times 9^{7}. Repeating this way is an example of recursion.
Exercises
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
Cross out 1, because it's not a prime.
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 ...
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 ...
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
 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?
 Find all primes below 200.
 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 is the largest natural number, you can immediately prove them wrong by telling them that is a larger natural number. You can substitute with any number other natural number 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:
Then, let y equal one more than x:
One may now conclude that y is not divisible by any of the primes up to n, since y differs from a multiple of each such prime by exactly 1. Since y is not divisible by any prime number, y must either be prime, or its prime factors must all be greater than n, a contradiction of the original assumption that n is the largest prime! Therefore, one must declare the original assumption incorrect, and that there exists an infinite number of primes.
Fun Fact — Largest known prime
The largest known prime is 2^{82,589,933}1. It has a whopping 24,862,048 digits! Primes of the form 2^{n}1 are called Mersenne primes named after the French monk/amateur mathematician.
Useful Offsite Resources
>> Next section: Modular Arithmetic
Modular arithmetic
HSME 
Content 

Primes 
Modular Arithmetic 
Problems & Projects 
Problem Set 
Project 
Solutions 
Exercise Solutions 
Problem Set Solutions 
Misc. 
Definition Sheet 
Full Version 
PDF Version 
Modular Arithmetic
Introduction
Modular arithmetic connects with primes in an interesting way.
Modular arithmetic is a system in which all numbers up to some positive integer, n say, are used. So if you were to start counting you would go 0, 1, 2, 3, ... , n  1 but instead of counting n you would start over at 0. And what would have been n + 1 would be 1 and what would have been n + 2 would be 2. Once 2n has been reached the number is reset to 0 again, and so on. Modular arithmetic is also called clockarithmetic 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 clockarithmetic.
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
and
We have done some calculation with negative numbers. Consider 5 × 6. Since 6 does not lie in the range 0 to 6, we need to add 7 to it until it does. And 6 + 7 = 1. So in modular 7 arithmetic, 6 = 1. In the above example we showed that 5 × 6 = 30 = 5, but 5 × 1 = 5. So we didn't do ourselves any harm by using 6 instead of 1. Why?
Note  Negatives: The preferred representation of 3 is 4, as 3 + 7 = 4, but using either 3 and 4 in a calculation will give us the same answer as long as we convert the final answer to a number between 0 and 6 (inclusive).
Exercise
Find in modulo 11
1.
 1 × 5
2.
 3 × 7
3. Compute the first 10 the powers of 2
 2^{1}, 2^{2}, 2^{3}, ... , 2^{10}
What do you notice?
Using the powers of 2 find
 6^{1}, 6^{2}, 6^{3}, ... , 6^{10}
What do you notice again?
4.
i.e. find, by trial and error (or otherwise), all numbers x such that x^{2} = 4 (mod 11). There are two solutions, find both .
5.
i.e. find all numbers x such that x^{2} = 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
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
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
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
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
We make the jump from modular arithemetic into rational number arithmetic. If 3x = 1 in modulo 15 arithmetic, then
for some integer k. Now we divide both sides by 3, we get
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
the conventional way to calculate the above would be to find the inverse of 3 (being 5). So
We write the inverse of 3 as 1/3, so we think of multiplying 3^{1} as dividing by 3, we get
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
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:
3. Calculate x in two ways, finding inverse and division
4. (Trick) Find x
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 twocolumn table where the larger of the two numbers is on the right hand side as follows
smaller  larger 

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

21  49 
7  21 
Perform the same action on the second row to produce the third row.
smaller  larger 

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

31  101 
8  31 
7  8 
1  7 
0  1 
Example 3
 Find the gcd of 132 and 200
smaller  larger 

132  200 
68  132 
64  68 
4  64 
0  4 
Important to note
 The gcd need not be a prime number.
 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
 5050 5051
 59 78
 111 369
 2021 4032
2. Find the gcd of the numbers 15, 510 and 375
info  Algorithm
An algorithm is a stepbystep 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 surefire 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
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:
We jump into rational maths again
We jump once more
Now the pattern is clear, we shall start from the beginning so that the process is not broken:
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:
Choose d = 0, therefore a = 49.
Example 2 Find the smallest positive value of a:
Choose e = 0, therefore a = 152 = 669
Example 3 Find the smallest positive value of a:
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:
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
we can rewrite the above in every day arithmetic
which is in the form of a Diophantine equation.
Now we are going to do the inelegant method of solving the above problem, and then the elegant method (using Magic Tables).
Both methods mentioned above uses the Euclid's algorithm for finding the gcd of two numbers. In fact, the gcd is closely related to the idea of an inverse. Let's apply the Euclid's algorithm on the two numbers 216 and 811. This time, however, we should store more details; more specifically, we want to set up an additional column called PQ which stands for partial quotient. The partial quotient is just a technical term for "how many n goes into m" e.g. The partial quotient of 3 and 19 is 6, the partial quotient of 4 and 21 is 5 and one last example the partial quotient of 7 and 49 is 7.
smaller  larger  PQ 

216  811  3 
163 
The tables says three 216s goes into 811 with remainder 163, or symbollically:
 811 = 3×216 + 163.
Let's continue:
smaller  larger  PQ 

216  811  3 
163  216  1 
53  163  3 
4  53  13 
1  4  4 
0  1 
Reading off the table, we can form the following expressions
 811 = 3× 216 + 163
 216 = 1× 163 + 53
 163 = 3× 53 + 4
 53 =13× 4 + 1
Now that we can work out the inverse of 216 by working the results backwards
 1 = 53  13×4
 1 = 53  13×(163  3×53)
 1 = 40×53  13×163
 1 = 40×(216  163)  13×163
 1 = 40×216  53×163
 1 = 40×216  53×(811  3×216)
 1 = 199×216  53×811
Now look at the equation mod 811, we will see the inverse of 216 is 199.
Magic Table
The Magic Table is a more elegant way to do the above calculations, let us use the table we form from Euclid's algorithm
smaller  larger  PQ 

216  811  3 
163  216  1 
53  163  3 
4  53  13 
1  4  4 
0  1 
Now we set up the socalled "magic table" which looks like this initially
0  1 
1  0 
Now we write the partial quotient on the first row:
3  1  3  13  4  

0  1  
1  0 
We produce the table according to the following rule:
 Multiply a partial quotient one space to the left of it in a different row, add the product to the number two space to the left on the same row and put the sum in the corresponding row.
It sounds more complicated then it should. Let's illustrate by producing a column:
3  1  3  13  4  

0  1  3  
1  0  1 
We put a 3 in the second row because 3 = 3×1 + 0. We put a 1 in the third row because 1 = 3×0 + 1.
We shall now produce the whole table without disruption:
3  1  3  13  4  

0  1  3  4  15  199  811 
1  0  1  1  4  53  216 
We can check that
 199×216  811×53 = 1
In fact, if the magic table is contructed properly, and we cross multiplied and subtracted the last two column correctly, then we will always get 1 or 1, provided the two numbers we started with were coprimes. The magic table is just a cleaner way of doing the mathematics.
Exercises
1. Find the smallest positive x:
2. Find the smallest positive x:
3.
(a) Produce the magic table for 33a = 1 (mod 101)
(b) Evaluate and express in the form p/q
What do you notice?
4.
(a) Produce the magic table for 17a = 1 (mod 317)
(b) Evaluate and express in the form p/q
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:
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
Now we look at the equation modulo 5
Substitute into (1) to get the following
Now look at the above modulo 7
we get
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:
Solution
now substitute back into the first equation, we get
we obtain
again substituting back
Therefore 52 is the smallest x that satisfies the congruences.
Example 2
Find the smallest x that satisfies:
Solution
substituting back
now solve for b
again, substitue back
Therefore 269 is the smallest x that satisfies the congruences.
Exercises
1. Solve for x
2. Solve for x
*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:
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:
we can find a solution
we now multiply both sides by the inverse of 5 (which is 17), we obtain
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:
we have
essentially, the problem asks us to find k and l such that the above equations are satisfied.
We can approach the problem as follows
now suppose m and n have gcd(m,n) = d, and m = dm_{o}, n = dn_{o}. We have
if (a  b)/d is an integer then we can read the equation mod m_{o}, we have:
Again, the above only makes sense if (a  b)/d is integeral. Also if (a  b)/d is an integer, then there is a solution, as m_{o} and n_{o} are coprimes!
In summary: for a system of two congruent equations
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:
 ...
for a solution to exist, we require that if i ≠ j
 gcd(m_{i},m_{j}) divides (a_{i}  a_{j})
Exercises
Decide whether a solution exists for each of the congruences. Explain why.
1.
 x ≡ 7 (mod 25)
 x ≡ 22 (mod 45)
2.
 x ≡ 7 (mod 23)
 x ≡ 3 (mod 11)
 x ≡ 3 (mod 13)
3.
 x ≡ 7 (mod 25)
 x ≡ 22 (mod 45)
 x ≡ 7 (mod 11)
4.
 x ≡ 4 (mod 28)
 x ≡ 28 (mod 52)
 x ≡ 24 (mod 32)
To go further
This chapter has been a gentle introduction to number theory, a profoundly beautiful branch of mathematics. It is gentle in the sense that it is mathematically light and overall quite easy. If you enjoyed the material in this chapter, you would also enjoy Further Modular Arithmetic, which is a harder and more rigorous treatment of the subject.
Also, if you feel like a challenge you may like to try out the Problem Set we have prepared for you. On the other hand, the project asks you to take a more investigative approach to work through some of the finer implications of the Chinese Remainder Theorem.
Acknowledgement
Acknowledgement: This chapter of the textbook owes much of its inspiration to Terry Gagen, Emeritus Associate Professor of Mathematics at the University of Sydney, and his lecture notes on "Number Theory and Algebra". Terry is a much loved figure among his students and is renowned for his entertaining style of teaching.
Reference
1. The Largest Known PrimesA Summary
Feedback
What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.
Problem Set
HSME 
Content 

Primes 
Modular Arithmetic 
Problems & Projects 
Problem Set 
Project 
Solutions 
Exercise Solutions 
Problem Set Solutions 
Misc. 
Definition Sheet 
Full Version 
PDF Version 
Problem Set
1. Is there a rule to determine whether a 3digit 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
4. Show that there are no integers x and y such that
5. In modular arithmetic, if
for some m, then we can write
we say, x is the square root of y mod m.
Note that if x satisfies x^{2} ≡ y, 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)
where
E.g. 3! = 1*2*3 = 6
(b)
Hence, show that
for p ≡ 1 (mod 4), i.e., show that the above when squared gives one.
Square root of minus 1
HSME 
Content 

Primes 
Modular Arithmetic 
Problems & Projects 
Problem Set 
Project 
Solutions 
Exercise Solutions 
Problem Set Solutions 
Misc. 
Definition Sheet 
Full Version 
PDF Version 
Project  The Square Root of 1
Notation: In modular arithmetic, if
for some m, then we can write
we say, x is the square root of y mod m.
Note that if x satisfies x^{2} ≡ y, 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
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
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
have a solution? Why?
5. If p ≡ 1 (mod 4) prime and q ≡ 1 (mod 4) prime and p ≠ q. Show that
has 4 solutions.
6. Find the 4 solutions to
note that 493 = 17 × 29.
7. Take an integer n with more than 2 prime factors. Consider:
Under what condition is there a solution? Explain thoroughly.
Solutions to exercises
HSME 
Content 

Primes 
Modular Arithmetic 
Problems & Projects 
Problem Set 
Project 
Solutions 
Exercise Solutions 
Problem Set Solutions 
Misc. 
Definition Sheet 
Full Version 
PDF Version 
HSE PrimesPrimes 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)
 13 is prime
 59 is prime
 101 is prime
Recursive Factorisation Exercises
Factorise using recursion.
Prime Sieve Exercises
 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:
 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
 alternatively, 1 = 10, 5 = 6: 10 × 6 = 60 = 5× 11 + 5 = 5
An easier list: 2, 4, 8, 5, 10, 9, 7, 3, 6, 1
Notice that it is not necessary to actually
compute to find mod 11.
If you know mod 11 = 6.
You can find mod 11 = (2*( mod 11)) mod 11 = 2*6 mod 11 = 12 mod 11 = 1.
We can note that 2^{9} = 6 and 2^{10} = 1, we can calculate 6^{2} easily: 6^{2} = 2^{18} = 2^8 = 3. OR by the above method
An easier list: 6, 3, 7, 9, 10, 5, 8, 4, 2, 1. 0^{2} = 0, 1^{2} = 1, 2^{2} = 4, 3^{2} = 9,
4^{2} = 16 = 5, 5^{2} = 25 = 5, 6^{2} = 36 = 3, 7^{2} = 49 = 3,
8^{2} = 64 = 9, 9^{2} = 81 = 4, 10^{2} = 100 = 1
An easier list: 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1
Thus  x^{2} = 2 = 9
Just look at the list above and you'll see that
Division and Inverses Exercises
1.
 therefore the inverse does not exist
2.
3.
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.
 There is no solution, because can never become an integer.
2.
 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 
 (b) To be added
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 
 (b) To be added
Chinese remainder theorem exercises
1.
Question 1
Show that the divisibleby3 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
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} = n^{2}  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
HSME 
Content 

Primes 
Modular Arithmetic 
Problems & Projects 
Problem Set 
Project 
Solutions 
Exercise Solutions 
Problem Set Solutions 
Misc. 
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 3digit number is divisible by 11? If yes, derive that rule.
Solution
Let x be a 3digit number We have
now
We can conclude a 3digit 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
 we deduce p is not prime, as it's a multiple of 3
 2nd category
 so p + 2 is not prime
 3rd category
 therefore p + 4 is not prime
Therefore p, p + 2 and p + 4 cannot all be primes.
Question 3
Find x
Solution
Notice that
 .
Then
 .
Likewise,
and
 .
Then
Question 4
9. Show that there are no integers x and y such that
Solution
Look at the equation mod 5, we have
but
therefore there does not exist a x such that
Question 5
Let p be a prime number. Show that
(a)
where
E.g. 3! = 1×2×3 = 6
(b) Hence, show that
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
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"
as required.
b) From part a)
since p = 4k + 1 for some positive integer k, (p  1)! has 4k terms
there are an even number of minuses on the right hand side, so
it follows
and finally we note that p = 4k + 1, we can conclude
Definitions
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.
But what about:
 "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 the whole statement to be true if at least one of the statements 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:
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
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 analogous 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:
and
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:
 NAND: x NAND y = NOT (x AND y)
 NOR: x NOR y = NOT (x OR y)
 XOR: x XOR y is true if and ONLY if one of x or y is true.
Produce truth tables for:
 xyz
 x'y'z'
 xyz + xy'z
 xz
 (x + y)'
 x'y'
 (xy)'
 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:
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:
the same can be said about:
From those two examples we can see that complexlooking expressions can be reduced very significantly. Of particular interest are expressions of the form of a sumofproduct, for example:
 xyz + xyz' + xy'z + x'yz + x'y'z' + x'y'z
We can factorise and simplify the expression as follows
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.
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:
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:
The connection between AND, OR and NOT is revealed by reversing the output of x + y by replacing it with x' + y'.
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
Example 2
Express x in sum of product form
 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
Example 4
Express x in sum of product form
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
Exercise
 Express in simplified sumofproduct form:
 z = ab'c' + ab'c + abc
 z = ab(c + d)
 z = (a + b)(c + d + f)
 z = a'c(a'bd)' + a'bc'd' + ab'c
 z = (a' + b)(a + b + d)d'
 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:
 John becomes a millionaire and donates $500,000 to the Red Cross
 John becomes a millionaire and does not donate $500,000 to the Red Cross
 John does not become a millionaire and donates $500,000 to the Red Cross
 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
has the following truth table:
x  y  

0  0  1

0  1  1

1  0  0

1  1  1

For emphasis, 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
then we express it symbolically as
 .
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  

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:
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)
Solution 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
Therefore it's a contradiction.
Back to Example 1, :. 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
 Decide whether the following propositions are true or false:
 If 1 + 2 = 3, then 2 + 2 = 5
 If 1 + 1 = 3, then boys don't like mud
 Show that the following pair of propositions are equivalent
 :
Logic Puzzles
Puzzle is an allencompassing 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:
 If A orders a martini, so does B.
 Either B or C always order a martini, but never at the same lunch.
 Either A or C always order a martini (or both)
 If C orders a martini, so does A.
 or (simplified from:
 or (simplified from:
Putting all these into one formula and simplifying:
Exercises
Please go to Puzzles/Logic puzzles.
Problem Set
1. Decide whether the following propositions are equivalent:
2. Express in simplest sumofproduct form the following proposition:
3. Translate the following sentences into symbolic form and decide if it's true:
 a. For all x, if x^{2} = 9 then x^{2}  6x  3 = 0
 b. We can find a x, such that x^{2} = 9 and x^{2}  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 and is even.
Solution 1
We know that since and are even, they must have 2 as a factor. Then, we can write the following:
 Let , , for some integers
Then:
by the distributive property of integers
The number clearly has 2 as a factor, which implies it is even. Therefore, is even.
Example 2
Prove the following statement for nonzero integers :
If divides and divides , then divides .
Solution 2
If an integer divides an integer , then we can write , for some nonzero integer . So let's say that and , for some nonzero integers and . Then:
by the associative property of integer multiplication.
But since and are integers, their product must also be an integer. Therefore, is the product of some integer multiplied by , so we get that divides .
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 for easier notation) is true for all natural numbers. This is how induction a proof by induction works:
 First, we show that is true for the natural number 1. This is usually called the basis or the base case.
 Then, we show that is true for natural number whenever it is true for natural number .
 By mathematical induction, is true for all natural numbers.
To understand how the last step works, notice the following
 is true for 1 (due to step 1)
 is true for 2 because it is true for 1 (due to step 2)
 is true for 3 because it is true for 2 (due to previous)
 is true for 4 because it is true for 3 (due to previous)
 is true for 5 because it is true for 4 (due to previous)
 and so on...
Example 1 Show that the identity
holds for all positive integers.
Solution Firstly, we show that it holds for 1
Suppose the identity holds for some natural number k:
This supposition is known as the induction hypothesis. We assume it is true, and aim to show that,
is also true.
We proceed
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! > 2^{n} for n ≥ 4.
Solution The claim is true for n = 4. As 4! > 2^{4}, i.e. 24 > 16. Now suppose it's true for n = k, k ≥ 4, i.e.
 k! > 2^{k}
it follows that
 (k+1)k! > (k+1)2^{k} > 2^{k+1}
 (k+1)! > 2^{k+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
Solution Suppose it's true for n = k, i.e.
it follows that
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
2. Prove that for n ≥ 1,
where x_{n} and y_{n} are integers.
3. Note that
Prove that there exists an explicit formula for
 for all integer m. E.g.
4. The sum of all of the interior angles of a triangle is ; the sum of all the angles of a rectangle is . Prove that the sum of all the angles of a polygon with n sides, is .
Proof by contradiction
 "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:
 First, we assume that the opposite of what we wish to prove is true.
 Then, we show that the logical consequences of the assumption include a contradiction.
 Finally, we conclude that the assumption must have been false.
√2 is irrational
As an example, we shall prove that 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 is rational:
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:
We have now found that a^{2} is some integer multiplied by 2. Therefore, a^{2} must be divisible by two. If a^{2} 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.
We have discovered that b^{2} 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 x^{2} is odd then x is also odd"
is harder to prove than
 "if x is even then x^{2} 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)
(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 = p_{1}p_{2}...p_{m} + 3)
Reading higher mathematics
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, x^{2} 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"
 means "for all" or "for any"
 means "there are some" or "there exists"
Example 1
The proposition:
 For all even integers x, x^{2} is also even.
can be expressed symbolically as:
Example 2
The proposition:
 There are some odd integers x, such that x^{2} is even.
can be expressed symbolically as:
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:
This proposition is true. Note that the order of the quantifiers is important. While the above statement is true, the statement
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
Similarly, to disprove
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
is TRUE
In summary, to obtain the negation of a proposition involving a quantifier, you replace the quantifier by its opposite (e.g. with ) and the quantified proposition (e.g. "x is even") by its negation (e.g. "x is odd").
Example 1
is a true statement. Its negation is
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:
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 Z_{6} (modular arithmetic modular 6) is not a field.
Problem Set
1. Prove
for
2. Prove by induction that
3. Prove by induction
where
 and
 and 0! = 1 by definition.
4. Prove by induction
5. Prove that if x and y are integers and n an odd integer then is an integer.
6. Prove that (n~m) = n!/((nm)!m!) is an integer. Where n! = n(n1)(n2)...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 1^{2} + 2^{2} + ... + n^{2} = n(n+1)(2n+1)/6
 When n=1,
 L.H.S. = 1^{2} = 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. 1^{2} + 2^{2} + ... + k^{2} = k(k+1)(2k+1)/6
 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,
 where x_{n} and y_{n} are integers.
 When n=1,
 Therefore x_{1}=1 and y_{1}=1, which are both integers.
 Therefore this is true when n=1.
 Assume that this is true for some positive integer k,
 i.e. where x_{k} and y_{k} are integers.
 Because x_{k} and y_{k} are both integers, therefore x_{k} + 5y_{k} and x_{k} + y_{k} 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
 Prove that there exists an explicit formula for
 for all integer m. E.g.

 It's clear that 1^{1} + 2^{1} + ... = (n+1)n/2. So the proposition is true for m=1.
 Suppose that
 has an explicit formula in terms of n for all j < k (**), we aim to prove that
 also has an explicit formula.
 Starting from the property given, i.e.
 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 kth 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.
Problem set
Mathematical Proofs Problem Set
1.
 For all
 Therefore , , ...
 When a>b and c>d, a+c>b+d ( See also Replace it if you find a better one).
 Therefore we have:
3.
 Let us call the proposition
 be P(n)
 Assume this is true for some n, then
 Now using the identities of this function:(Note:If anyone find wikibooks ever mentioned this, include a link here!),we have:
 Since for all n,
 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
letting a = b = 1, we get
as required.
5.
 Let be a polynomial with x as the variable, y and n as constants.
 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
 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:
This set consists of five elements, namely the first five natural numbers. Now consider the set:
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 oneone 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 and are of the same size if there is a function such that for every in , we have in and moreover, for every in , there exists an in such that .
Example
Consider our previous example. We want to know if the sets and 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 oneone function that maps from A to B is .
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 oneone 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 oneone correspondence as a function
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
 Is the number of even numbers the same as the natural numbers?
 What about the number of square numbers?
 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.
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
 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 ?
 Show that (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 , and .
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.
 R_{1}
 R_{2}
 R_{3}
 R_{4}
 .
 .
 .
Where R_{1} is the first number in our list, R_{2} 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.r_{11}r_{12}r_{13}r_{14}...
 0.r_{21}r_{22}r_{23}r_{24}...
 0.r_{31}r_{32}r_{33}r_{44}...
 0.r_{41}r_{42}r_{43}r_{44}...
 .
 .
 .
Here r_{11} 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... r_{11} would be 3, r_{12} 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.a_{1}a_{2}a_{3}a_{4}...
Where a_{1} is the first digit after the point etc.
We let a_{1} take any value from 0  9 inclusive except the digit r_{11}. So if r_{11} = 3 then a_{1} can be 0, 1, 2, 4, 5, 6, 7, 8, or 9. Then we let a_{2} be any digit except r_{22} (the second digit of the second number on the list). Then a_{3} be any digit except r_{33} 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 R_{something}. Let's see what R_{something} it might be equal to. It can't be equal to R_{1} because it has a different first digit (r_{11} and a_{1}. Nor can it be equal to R_{2} 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 s