1.10: Prime Numbers

Last updated
Save as PDF

Page ID: 82292

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Definition $\PageIndex{1}$: Prime & Composite

An integer $p$ is prime if $p\ge 2$ and the only positive divisors of $p$ are $1$ and $p$. An integer $n$ is composite if $n\ge 2$ and $n$ is not prime.

Remark $\PageIndex{1}$

The number $1$ is neither prime nor composite.

Lemma $\PageIndex{1}$

An integer $n\ge 2$ is composite if and only if there are integers $a$ and $b$ such that $n=ab$, $1<a<n$, and $1<b<n$.

Proof: Let $n\ge 2$. If $n$ is composite there is a positive integer $a$ such that $a\ne 1$, $a\ne n$ and $a\mid n$. This means that $n=ab$ for some $b$. Since $n$ and $a$ are positive so is $b$. Hence $1\le a$ and $1\le b$. By Theorem 3.1(10) $a\le n$ and $b\le n$. Since $a\ne 1$ and $a\ne n$ we have $1<a<n$. If $b=1$ then $a=n$, which is not possible, so $b\ne 1$. If $b=n$ then $a=1$, which is also not possible. So $1<b<n$. The converse is obvious.

Lemma $\PageIndex{2}$

If $n>1$, there is a prime $p$ such that $p\mid n$.

Proof: Assume there is some integer $n>1$ which has no prime divisor. Let $S$ denote the set of all such integers. By the Well-Ordering Property there is a smallest such integer, call it $m$. Now $m>1$ and has no prime divisor. So $m$ cannot be prime. Hence $m$ is composite. Therefore by Lemma 10.1 \[m=ab,\quad 1<a<m,\quad 1<b<m.\nonumber\] Since $1<a<m$ then $a$ is not in the set $S$. So $a$ must have a prime divisor, call it $p$. Then $p\mid a$ and $a\mid m$ so by Theorem 3.1, $p\mid m$. This contradicts the fact that $m$ has no prime divisor. So the set $S$ must be empty and this proves the lemma.

Theorem $\PageIndex{1}$: Euclid's Theorem

There are infinitely many prime numbers.

Proof: Assume, by way of contradiction, that there are only a finite number of prime numbers, say: \[p_1,p_2,\dotsc,p_n.\nonumber\] Define \[N=p_1p_2\dotsm p_n+1.\nonumber\] Since $p_1\ge 2$, clearly $N\ge 3$. So by Lemma 10.2 $N$ has a prime divisor $p$. By assumption $p=p_i$ for some $i=1,\dotsc,n$. Let $a=p_1\dotsm p_n$. Note that \[a=p_i\left(p_1p_2\dotsm p_{i-1}p_{i+1}\dotsm p_n\right),\nonumber\] so $p_i\mid a$. Now $N=a+1$ and by assumption $p_i\mid a+1$. So by Exercise 3.2 $p_i\mid (a+1)-a$, that is $p_i\mid 1$. By Basic Axiom 3 in Chapter 1 this implies that $p_i=1$. This contradicts the fact that primes are $>1$. It follows that the assumption that there are only finitely many primes is not true.

Exercise $\PageIndex{1}$

Use the idea of the above proof to show that if $q_1,q_2,\dotsc,q_n$ are primes there is a prime $q\notin\left\{q_1,\dotsc,q_n\right\}$.

Hint: Take $N=q_1\dotsm q_n+1$. By Lemma 10.2 there is a prime $q$ such that $q\mid N$. Prove that $q\notin\left\{q_1,\dotsc,q_n\right\}$.

Exercise $\PageIndex{2}$

Let $p_1=2,p_2=3,p_3=5,\dotsc$ and, in general, $p_i=\text{the }i$-th prime. Prove or disprove that \[p_1p_2\dotsm p_n+1\nonumber\] is prime for all $n\ge 1$.

Answer: If $n=1$ we have $2+1=3$ is prime. If $n=2$ we have $2\cdot 3+1=7$ is prime. If $n=3$ we have $2\cdot 3\cdot 5+1=31$ is prime. Try the next few values of $n$. You may want to use the next theorem to check primality.

Theorem $\PageIndex{2}$

If $n>1$ is composite then $n$ has a prime divisor $p\le\sqrt{n}$.

Proof: Let $n>1$ be composite. Then $n=ab$ where $1<a<n$ and $1<b<n$. I claim that one of $a$ or $b$ is $\le\sqrt{n}$. If not then $a>\sqrt{n}$ and $b>\sqrt{n}$. Hence $n=ab>\sqrt{n}\,\sqrt{n}=n$. This implies $n>n$, a contradiction. So $a\le\sqrt{n}$ or $b\le\sqrt{n}$. Suppose $a\le\sqrt{n}$. Since $1<a$, by Lemma 10.2 there is a prime $p$ such that $p\mid a$. Hence, by Theorem 3.1 since $a\mid n$ we have $p\mid n$. Also by Theorem 3.1 since $p\mid a$ we have $p\le a\le\sqrt{n}$.

Remark $\PageIndex{2}$

We can use Theorem 10.2 to help decide whether or not an integer is prime: To check whether or not $n>1$ is prime we need only try to divide it by all primes $p\le\sqrt{n}$. If none of these primes divides $n$ then $n$ must be prime.

Example $\PageIndex{1}$

Consider the number $97$. Note that $\sqrt{97}<\sqrt{100}=10$. The primes $\le 10$ are $2$, $3$, $5$, and $7$. One easily checks that $97\bmod 2=1$, $97\bmod 3=1$, $97\bmod 5=2$, $97\bmod 7=6$. So none of the primes $2$, $3$, $5$, $7$ divide $97$ and $97$ is prime by Theorem 10.2.

Exercise $\PageIndex{3}$

By using Theorem 10.2, as in the above example, determine the primality$^{1}$ of the following integers: \[143,\quad 221,\quad 199,\quad 223,\quad 3521.\nonumber\]

Definition $\PageIndex{2}$

Let $x\in\mathbb{R}$, $x>0$. $\pi(x)$ denotes the number of primes $p$ such that $p\le x$.

For example, since the only primes $p\le 10$ are 2, 3, 5, and 7 we have $\pi(10) = 4$.

Here is a table of values of $\pi(10^i)$ for $i=2, \dots, 10$. I also include known approximations to $\pi(x)$. Note that the formulas for the approximations do not give integer values, but for the table I have rounded each to the nearest integer. The values in the table were computed using Maple. \[\left | \begin {array}{rrrrr} x& \pi(x)& \frac x{ln(x)}&\frac x{ln(x)-1}& \int_2^x\frac{1}{ln(t)}dt \\ & & & & \\ 10^2&25&22&28&29\\ 10^3&168&145&169&177\\ 10^4&1229&1086&1218&1245\\ 10^5&9592&8686&9512&9629\\ 10^6&78498&72382&78030&78627\\ 10^7&664579&620421&661459&664917\\ 10^8&5761455&5428681&5740304&5762208\\ 10^9&50847534&48254942&50701542&50849234\\ 10^{10}&455052511&434294482&454011971&455055614 \end {array} \right|\nonumber\] You may judge for yourself which approximations appear to be the best. This table has been continued up to $10^{21}$, but people are still working on finding the value of $\pi(10^{22})$. Of course, the approximations are easy to compute with Maple but the exact value of $\pi(10^{22})$ is difficult to find.

The above approximations are based on the so-called Prime Number Theorem first conjectured by Gauss in $1793$ but not proved till over 100 years later by Hadamard and Vallée Poussin.

Theorem $\PageIndex{3}$: The Prime Number Theorem

\[\label{eq:1}\pi(x)\sim\frac x{\ln(x)} \quad \mbox{ for all $x>0$}. \]

Remark $\PageIndex{3}$

$\eqref{eq:1}$ means that \[\lim_{x\to\infty}\frac{\pi(x)}{\frac x{\ln(x)}}=1.\nonumber\]

Although there are infinitely many primes there are long stretches of consecutive integers containing no primes.

Theorem $\PageIndex{4}$

For any positive integer $n$ there is an integer $a$ such that the $n$ consecutive integers \[a,a+1,a+2,\dotsc,a+(n-1)\nonumber\] are all composite.

Proof: Given $n\ge 1$ let $a=(n+1)!+2$. We claim that all the numbers \[a+i,\quad 0\le i\le n-1\nonumber\] are composite. Since $(n+1)\ge 2$ clearly $2\mid (n+1)!$ and $2\mid 2$. Hence $2\mid (n+1)!+2$. Since $(n+1)!+2>2$, $(n+1)!+2$ is composite. Consider \[a+i=(n+1)!+i+2\nonumber\] where $0\le i\le n-1$ so $2\le i+2\le n+1$. Thus $i+2\mid (n+1)!$ and $i+2\mid i+2.$ Therefore $i+2\mid a+i$. Now $a+i>i+2>1$, so $a+i$ is composite.

Exercise $\PageIndex{4}$

Use the Prime Number Theorem and a calculator to approximate the number of primes $\le 10^8$. Note $\ln (10^8 )=8 \ln (10)$.

Exercise $\PageIndex{5}$

Find $10$ consecutive composite numbers.

Exercise $\PageIndex{6}$

Prove that $2$ is the only even prime number. (Joke: Hence it is said that 2 is the "oddest" prime.)

Exercise $\PageIndex{7}$

Prove that if $a$ and $n$ are positive integers such that $n \ge 2$ and $a^n-1$ is prime then $a$ must be $2$.

Hint: Exercise 2.4 \[1+x+x^2+\dotsb+x^{n-1}=\frac{\left(x^n-1\right)}{x-1}\nonumber\] that is, \[x^n-1=(x-1)\left(1+x+x^2+\dotsb+x^{n-1}\right)\nonumber\] if $x\ne 1$ and $n\ge 1$.

Exercise $\PageIndex{8}$

Is $2^n-1$ always prime if $n\ge 2$? Explain.
Is $2^n-1$ always prime if $n$ is prime? Explain.

Exercise $\PageIndex{9}$

Show that if $p$ and $q$ are primes and $p\mid q$, then $p=q$.

Footnotes

[1] This means determine whether or not each number is prime.