Divisibility properties & prime numbers
This post contains a few definitions, theorems, and methods for divisibility properties and prime numbers. It is a condensed reference for my course in Number Theory.
Divisibility properties
Definition: divisor, trivial divisor, non-trivial divisor, multiple
$d$ is a divisor of $a$ (and $a$ is a multiple of $d$) if there exists an $x$, such that $a = d\cdot x$.
This is denoted with $d\ |\ a$, and the divisor is a non-trivial divisor if $1 \neq d \neq a$, and otherwise it is a trivial divisor.
Theorem: If $d\ |\ a$ and $d\ |\ b$, then $d\ |\ ax+by$.
Proof: Given is that $d\ |\ a$, and $d\ |\ b$, then two natural numbers $p, q$ exists, such that $a = dp$, and $b = dq$. This means that $ax + by = dpx + dqy = d(px + qy)$, which states that $d$ divides $ax + by$. $\blacksquare$
Theorem (division algorithm): Let $a, b \in \mathbb{N}\ (b \neq 0)$ there exists two numbers $q, r \in \mathbb{N}$ such that $a = bq + r$ where $0 \leq r \lt b$.
Proof: With a given $a$ and $b$, choose $q, r$ in the following way:
$$q = \left\lfloor \frac{a}{b} \right\rfloor \qquad r = a - b \cdot \left\lfloor \frac{a}{b} \right\rfloor $$
It is easy to see that $0 \leq x - \lfloor x \rfloor \lt 1$. With the choice of $q, r$ it holds that $a = bq + r$. Left to proof is that $0 \leq r \lt b$. If we multiply $0 \leq \frac{a}{b} - \left\lfloor \frac{a}{b} \right\rfloor \lt 1$ with $b$, we see that $0 \leq a-bq (=r) \lt b$. $\blacksquare$
Prime numbers
Definition: prime number, composite number
A natural number ($ \gt 1$) without any non-trivial divisors is called a prime number. A natural number that is not a prime number, is called composite number.
The first fifteen prime numbers are: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$.
Sieve of Eratosthenes
This is a method to generate a list of prime numbers. Suppose we want to write all the prime numbers up to $n$. First we write down all the numbers from $2$ up to $n$.
Figure 1 - Sieve of Eratosthenes with $n = 100$.
The algorithm then consists of the following steps.
- Take the first number, which is $2$, and cross out all other multiples of $2$, but not $2$ itself.
- Go to the next not crossed out number, which is $3$, and also cross out all multiples of $3$, except $3$ itself.
- Now do this for the next number, which is $5$, and cross out all multiples of $5$, except $5$ itself.
- Repeat this process until you have passed $\sqrt{n}$ (proof in the next section).
- All the numbers that are not crossed out are prime numbers.
Prime test
How can you determine if a number $n$ is prime? A simple, but very inefficient, method is to divide $n$ by $2, 3, 5, ...$. If you cannot find a prime number lower than $\sqrt{n}$ to divide $n$, you can conclude that $n$ is a prime number.
Proof: Suppose that $n$ is a composite number, which means that $n = pq$ where $1 \lt p, q \lt n$. In this case, either $p$ or $q$ must be smaller than $\sqrt{n}$, and the other larger. However, if we never find a smaller divisor, the larger one also doesn't exist. $\blacksquare$
Theorem (prime factorization): Every natural number ($>1$) can be factorized into a product of primes in exactly one way.
Proof: Let $n$ be a natural number ($>1$). Take the set of prime numbers. First divide $n$ as many times as possible by $2$, and then by $3$, and then by $5$, and so on. At some point it is no longer possible to divide $n$. If it is done in this order, it is obvious that there is only one way, except for a different order in notation. $\blacksquare$
Theorem: There are infinitely many prime numbers.
Proof: Euclides has shown how to find a larger prime number, for every prime number. This also proofs that there are infinitely many.
Suppose $P$ is a prime number, if we look at $P!+1$, we get a number that may or may not be prime. However, we can say the following about $P!+1$:
- $P!+1$ is not divisible by $2$, because $P!+1$ is a multiple of $2$ plus $1$.
- $P!+1$ is not divisible by $3$, because $P!+1$ is a multiple of $3$ plus $1$.
- $P!+1$ is not divisible by $5$, because $P!+1$ is a multiple of $5$ plus $1$.
- ...
- $P!+1$ is not divisible by $P$, because $P!+1$ is a multiple of $P$ plus $1$.
This all means that every prime factor of $P!+1$ is greater than $P$, which implicates that we have found a prime number bigger than $P$. $\blacksquare$
Mersenne primes
Natural numbers of the form $M_n = 2^n - 1$ $(n\geq 0)$ are called Mersenne numbers. If such a number is a prime number, we are talking about a Mersenne prime. The first five Mersenne primes are: $M_2 = 3,\ M_3 = 7,\ M_5 = 31,\ M_7 = 127,\ M_{13} = 8191$.
Mersenne primes are interesting because there exists a very fast prime test for these numbers. In total, only $49$ Mersenne primes have been found to date (2016).
Counting primes
The function $\pi(x)$ denotes that number of prime number $\leq x$, and is called the prime counting function. Because there are $25$ prime numbers $\leq 100$, means that $\pi(100) = 25$.
A good approximation, for large values of $x$, is $\dfrac{x}{\ln x}$.
Proof: Solving the limit $$\lim\limits_{x \rightarrow \infty} \dfrac{\pi(x) - \dfrac{x}{\ln x}}{\dfrac{x}{\ln x}} = 0$$ shows that it is correct. See Prime-counting function - Wikipedia.
This formula has been conjectured by Gauss, when he was just 15. Only 100 years later it has been proved!
Unsolved questions about prime numbers
Many questions about prime numbers have thus far been unsolved. These are two of them:
- It is conjectured that every number $(\gt 2)$ can be written as a sum of two prime numbers. This has been conjectured by Goldback in 1742, and so far the conjecture has not been proven or been disproved.
- Another problem is the problem of twin primes, these are prime numbers that differ exactly $2$. The smallest example is $2$, and $5$. It is unknown if there are infinitely many twin prime numbers.