The price

An integer \(p > 1\) is prime if it has no positive divisors other than \(1\) and itself.

No even number, except \(2\), is prime. Because 2

additional information

There are infinitely many primes

Credit: Euler.

Proof:

Assume to the contrary that there are finitely many primes. \(p_1, …, p_{n}\). We desire to make a new prime to reach contradiction.

Consider:

\begin{equation} N = p_1 \times \dots \times p_{n} + 1 \end{equation}

Note that \(p_1 \times … \times p_{n}\) is divisible by each of the \(p_{j}\). If some \(p_i |N\), \(p_{i}|1\), which is impossible as \(1\) is not divisible by anything. So, no \(p_{i}\) divides \(N\).

“very prime has a succinct certificate”

\begin{equation} \text{PRIMES} : \qty {A \mid A\text{ is prime}} \end{equation}

The certificate?

\begin{equation} A \text{ prime} \Leftrightarrow \exists 1 < b < A : B, B^{2}, \dots, B^{A*2} \not \cong \ \text{mod}\ A \end{equation}

So \(\text{PRIMES} \in \text{NP}\)

But actually PRIMES is in \(P\)

The principle of induction is a technique used to prove the relationship between a smaller subset

The following three statements are equivalent.

standard induction

Suppose \(S \subset \mathbb{N}\), which is non-empty. If \(S\) is a non-empty subset such that \(0 \in S\), and for all \(n \in \mathbb{N}\), \(n \in S \implies n+1 \in S\). Then, \(S = \mathbb{N}\).

strong induction

Suppose \(S \subset \mathbb{N}\), which is non-empty. If \(S\) is a non-empty subset such that \(0 \in S\), and for all \(n \in \mathbb{N}\), \(\{0, \dots, n\} \in S \implies n+1 \in S\). Then, \(S = \mathbb{N}\).