## Prime Series 1: Introduction to Prime Numbers

We have learned from elementary school mathematics that a prime number has only two factors, 1 and itself. For example, 2, 3, 5 and 7 are prime numbers, while 8 is not prime because it has four factors — 1, 2, 4, and 8. Numbers that are not prime are called composite numbers.

Geometric Interpretation of Prime and Composite Numbers

Mathematicians during the ancient times, particularly the Greeks, always make  use of geometric interpretations of numbers. Square numbers, for example, are represented with pebbles arranged with the same number of rows and columns.  The first five square numbers are 1, 4, 9, 16 and 25.

Rectangular numbers are also popular. For instance, the number 12 can be interpreted pebbles arranged in rectangles with the following dimensions: 3 by 4, 2 by 6 and 12 by 1. If we are going to use squares instead of pebbles, the geometric representations of these arrangements are shown in Figure 1.

Figure 1 – Different rectangular arrangements of 12 pebbles represented by squares.

Numbers that cannot be arranged as more than one rectangle are prime numbers. In our example above, 12 has three possible arrangements, while the numbers 3, 5 and 7 can only be arranged in a single row.

Figure 2 – Rectangular arrangements of 3, 5 and 7 pebbles represented by squares.

As we can see, this is the geometric interpretation of the definition that the factors of primes are only 1 and itself.

Sieve of Eratosthenes

The Greek philosopher and mathematician Eratosthenes was the first to be credited in identifying primes in a finite list by brute force.  The strategy is to list a finite set of counting numbers in increasing order, then starting with 2 eliminate all its multiples. This eliminates all even numbers except 2. Then we follow the same pattern: we eliminate multiples of 3 greater than 3, eliminate all multiples of 5 greater than 5 and so on, until all the numbers left are not multiples of any number smaller than it. The remaining numbers after all elimination are prime numbers.

The primes numbers less than 100 are shown in white cells in the table below. The numbers in the yellow cells are composite numbers.  Mathematicians agreed not to include 1 in the set of prime numbers or the set of composite numbers.

Figure 3 - The sieve of Eratosthenes shows primes less than 100 in white table cells..

If we look at the table above, we could not probably see a pattern about the number of primes in a given interval; however, if we investigate further, as the intervals increase, the number of primes is getting fewer and fewer. For example, there are 168 primes between 1 and 1000, 135 primes between 1000 and 2000, 127 primes between 2000 and 3000, and 120 primes between 3000 and 4000. With this observation, we want to ask the following question:

Is there a particular prime number, that after such number, we could no longer find primes?

or equivalently,

Are prime numbers finite?

We will answer this in the continuation of this article titled  “Infinitude of Primes.” The formal proof of this conjecture is also discussed in the third part.

## Problem Set 2

PROBLEMS

1.) Find a linear function $f(x)$ such that $f(1) = 42$ and $f(2) = 47$.

2.) Solve for $x$: $4^{x+1} + 4^{x+2} +4^{x+3} +4^{x+4} = 170.$

3.) Prove that the product of $3$ consecutive numbers is always divisible by $6$.

4.) Prove that if $p$ is prime, $a$ and $b$ are integers, and $a \equiv b\mod p$, then $a^p \equiv b^p \mod p$.

SOLUTIONS AND PROOFS

Post Date: October 20, 2009

1. Solution: This is just the same as saying, find the equation of the line passing through $(1,42)$ and $(2,1337)$. So, by point slope formula, we have, $y - y_1 = \displaystyle\frac{y_2 - y_1}{x_2 - x_1}(x - x_1)\Rightarrow y - 42 = \displaystyle\frac{1337 - 42}{2 - 1}(x - 1). \Rightarrow y = f(x) = -18x + 92.$

2.) Solution:$4^{x+1} + 4^{x+2} +4^{x+3} +4^{x+4} = 4^x(1 + 4 +4^2 +4^3) = 170 \Rightarrow 4^x(85) = 170\Rightarrow 4^x = 2 \Rightarrow 2^{2x}=2^1 \Rightarrow x = \displaystyle\frac{1}{2}.$

3.) Proof: A number is divisible by $6$ if it is divisible by $2$ and $3$. A product of $3$ consecutive numbers is divisible by $2$ because at least one of them is even, so it remains to show it is divisible by $3$.

If a number is divided by $3$, its possible remainders are $0, 1,$ and $2$.  Assume $n, n +1$ and $n+2$ be the three consecutive numbers, and $r$ be the remainder if $n$ is divided by $3$.

Case 1: If $r=0$, we are done.

Case 2: If $r = 1$, then $n + 2 \Rightarrow r=0$

Case 3: If $r = 2$, then $n + 1 \Rightarrow r = 0$.

Since the product of the three consecutive numbers is even, and for each case of $r$, one of the consecutive numbers is divisible by $3$, the product of three consecutive numbers is divisible by $6. \blacksquare$

4.) Proof: From definition, $a^p \equiv b^p \mod p \Leftrightarrow b = a + kp$ for some $k \in \mathbb{Z}.$

Raising both sides of the equation to $p$, we have $b^p = (a + kp)^p.$ By the binomial theorem,  $b^p = (a + kp)^p = a^p + \displaystyle {p \choose 1}a^{p-1}kp + \displaystyle{p \choose 2}a^{p-2}k^2p^2 + \ldots + k^pp^p$.

Notice that every term aside from $a^p$ is divisible by $p^2$. (Why?). Therefore,  $a^p \equiv 0 \mod p^2 .$

Hence, then $a^p \equiv b^p \mod p.$ $\blacksquare$

1 2 3 4