Houjun Liu

prime

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\).

If \(N\) is now prime, we are done as it is not in the list of \(p_{j}\). If not, pick any prime divisor \(p\) of \(N\). We will note that given no \(p_{j}\) divides \(N\), therefore any prime divisor is a new prime.

Having made a new prime, we reach contradiction. \(\blacksquare\)

coprime

Two integers \(a, b\) is considered coprime if \(\gcd (a,b) = 1\). Therefore, because greatest common divisor is a linear combination