Pascalís Triangle and Prime Numbers
Back to Contents
Ultimately we want to devise an algorithm that will enable us to calculate all of the prime numbers and only the prime numbers. To that end we must gather together all of the patterns that we can find in the prime numbers. One such pattern appears in Pascalís triangle, which comes to us via the binomial theorem.
The binomial theorem tells us how to calculate the polynomial that corresponds to (x+y)n for any value of n. The coefficients in that polynomial form a set, with each coefficient given by
for all integer values of p from 0 to n. for n=4, for example, we have (1,4,6,4,1). Writing all of the sets for subsequent values of n in a symmetrical array gives us Pascalís triangle,
Each element in that triangle equals the sum of the two elements immediately above it on the left and right.
If n represents a prime number, then every element in its row, except the first and last (p=0 and p=n), is evenly divisible by it. If n=7, for example, the row is (1,7,21,35,35,21,7,1), all evenly divisible by 7, except the first and last elements. But if n=9, the row is (1,9,36,84,126,126,84,36,9,1) and 84 is not evenly divisible by 9. Analysis of Equation 1 tells us why this is so.
The combinatorial coefficient that we calculate through Equation 1 is always an integer. The division of n! by (n-p)! removes the first p factors from the product and subsequent division of the quotient by p! ablates the composite factors in it. If n is a prime number, the second division canít ablate it, so it must remain unchanged as a factor in the combinatorial coefficient. Thus, every combinatorial coefficient greater than 1 in the n-th row of Pascalís triangle must be evenly divisible by n if n is prime.
That fact plus the statement that each element in Pascalís triangle is the sum of the two elements above it on the left and right lead to one other minor fact. Let m(n) represent an integer multiple of n. Each element of the (n-1)-th row has the form m(n)Ī1 if n is prime. The plus and minus signs must alternate as we pass along the row so that we have an element of the n-th row as
Thus we have one more tiny clue toward the algorithm that we want to obtain.
But we already have extensive lists of prime numbers. Why do we want an algorithm that will give us what we already know?
The lists are empirical-inductive structures. The entries on them were obtained by testing numbers for primality, a process that gets longer and more tedious as the numbers get bigger. But mathematicians want their discipline to be purely axiomatic-deductive. They want a rational procedure that will calculate all of the primes and only the primes, because the pattern underlying that procedure will enable them to prove and verify propositions involving prime numbers. In that way a large chunk of mathematics will become perfectly rigid. Thatís why we want the algorithm.
Back to Contents