Dec 8th 2010, 18:49:41
Prime Numbers
Prime numbers form a subset of the integers that have the special property that they have no divisors other than 1 and the prime numbers themselves. Thus, 11 is a prime number because the only numbers that divide exactly into 11 are 1 and 11. Similarly, 12 is not a prime number because it is divisible by 2, 3, 4, and 6, as well as 1 and 12.
There are various theorems that apply to the prime numbers. Perhaps the most important of these is the Fundamental Theorem of Arithmetic. This states that:
Each integer n > 1 can be expressed as a unique product of prime numbers.
As an example, let us consider the integer 144. We can reduce this to a product of primes as follows:
144 = 72 × 2 = 36 × 2 × 2 = 6 × 6 × 2 × 2 = 3 × 3 ×2 × 2 × 2 × 2
This product of primes is unique – we can not find any other combination of prime numbers that multiply up to give 144 (other than re-ordering the primes on the right-hand side).
Two interesting conjectures about prime numbers are as follows. The first is the so-called Goldbach Conjecture. This states that every even integer greater than 2 can be written as the sum of two primes. Thus, for example, 24 = 19 + 5. The second conjecture is that there an infinite number of “twin primes”. Twin primes are primes that differ by two, for example 11 and 13, or 29 and 31.
It is a curiosity of mathematics that neither of these conjectures has been formally proved to be correct.
Infinite Number of Primes
In this section, our aim is to prove that there are an infinite number of prime numbers, using proof by contradiction. (This theorem can be proved in a number of ways that don’t rely on proof by contradiction – however, the aim is to illustrate how proof by contradiction works, so that is how we will undertake the proof in this section!)
To undertake the proof by contradiction, we formulate the statement that we wish to prove. This statement can be written as
S = There is an infinite number of prime numbers
Now, we formulate the converse to this statement, which is:
T = There is a finite number of prime numbers
Either statement S or statement T is true. To show that statement S is true, we assume instead that statement T is true, and we see if it leads to a contradiction. So, let us assume that statement T is true, and see where it takes us.
If statement T is true, then there are a finite number of prime numbers. This means that there must be a highest prime number, which we will call p. The sequence of prime numbers (which is finite) is then as follows:
1, 2, 3, 5, 7, 11, … , p
Now, let us define a new number N as follows:
N = 1 × 2 × 3 × 5 × 7 × 11 × … × p + 1
That is, we multiply up all the prime number in the finite set, and add one. Now, adding one to the product of prime numbers has an important consequence – it means that the number N is not exactly divisible by any of the prime numbers in our finite set of primes.
If N is not divisible by any member of our finite set of primes, there are two possibilities:
1. N is itself a prime number.
2. N is divisible by a prime number greater than p.
If the first option is true, then since N is clearly greater than p, we have found a prime number that is greater than the “largest” prime p in our finite set of primes.
The second option follows from the Fundamental Theorem of Arithmetic, which states that any integer can be expressed as a product of primes. Since N is not divisible by any prime less than p (we deliberately defined N such that this was the case), it must be divisible by a prime that is greater than p.
So, we have found a contradiction – we find that if we assume that there is a finite number of primes, then we can always find a larger prime than the largest one in our finite set!
This is the contradiction that we seek. It shows that statement T above is false, and hence statement S is true. There are an infinite number of prime numbers.
Another Prime Number Proof
While we’re in the mood, let us prove another theorem of prime numbers, again by proof by contradiction. The statement we want to prove is as follows:
S = Every prime number > 3 can be written in the form 6n ± 1, where n is an integer.
As with the proof of an infinite number of primes, we need to determine the converse to this statement. We can write this statement as follows:
T = There is at least one prime number > 3 that cannot be written in the form 6n ± 1.
In the spirit of proof by contradiction, let us see where statement T takes us.
Let one of the primes not of the form 6n ± 1 be p. Prime number p therefore has the following properties:
p > 3
p ≠ 6n ± 1
Now, if p is not of the form 6n ± 1, it must take one of the following forms:
1. p = 6n
2. p = 6n ± 2
3. p = 6n ± 3
Now, if expression 1 holds, then p is divisible by 6, and is not a prime number. If expression 2 holds, then p is divisible by 2, and hence is not a prime number. Similarly, if p is of the form in expression 3, it is divisible by 3, and hence is not a prime number.
We have the contradiction we seek. If the prime number p is not of the form 6n ± 1, then it cannot be a prime number. Thus statement T above is false, and hence statement S is true. All prime numbers > 3 can be written in the form 6n ± 1, where n is an integer.
<[FBI]ZEN> Which is funny...because I am Spanish and Native American mixed....which means I am a Mexican....
<Galandy>move to canada ZEN everyone else does
<[FBI]ZEN> And breed with a Quebecian
<[FBI]ZEN> To make the ultimate snob/migrant worker
EE Patron