The properties of prime numbers

The set $\mathbb{P}$ is the set of prime numbers:

$$ \mathbb{P} = \Bigl \{2, 3, 5, 7, 11, 13, ...etc. \Bigr\}$$

We call a prime number, a number $p \in \mathbb{P}$ which has only itself and $1$ as a divisor.

$$ \mathcal{D}(p) = \bigl\{p, 1 \bigr\} $$

Likewise, we will say that two numbers $(a, b) \in \hspace{0.05em} \mathbb{Z}^2$ are coprime if their unique common divisor is $1$.

$$ \mathcal{D}(a, b) = \bigl\{1 \bigr\} \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge b = 1 $$

Two prime numbers are coprime

Two prime numbers are coprime.

$$ \forall (p_1, p_2) \in \hspace{0.05em} \mathbb{P}, $$

$$ (p_1, p_2) \in \hspace{0.05em} \mathbb{P} \Longrightarrow p_1 \wedge p_2 = 1$$

Breakdown in prime factors

All natural number $n \geqslant 2$ uniquely decomposes into a prime factors product.

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \forall i \in \mathbb{N}, \enspace (\forall p_i \in \mathbb{P}, \enspace \exists \alpha_i \in \mathbb{N}), $$

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$

Every number higher than 2 owns at least one prime divisor

All natural number $n \geqslant 2$ has at least one prime divisor.

Every non-prime number higher than 4 owns at least one strict divisor

All non-prime natural number $n \geqslant 4 $ has at least one strict divisor $d_0 $ such as $ d_0 \leqslant \sqrt{n} $.

Coprimity link between a prime number and an integer

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, $$

$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$

Euclid's lemma

$$ \forall p \in \mathbb{P}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p/a) \enspace or \enspace (p/b) \qquad \bigl(Euclid's \enspace lemma \bigr) $$

Euclid's lemma corollary

$$ \forall (p, a, b) \in \hspace{0.05em} \mathbb{P}^3, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p=a) \enspace or \enspace (p=b) \qquad \bigl(Euclid's \enspace lemma \enspace (corollary)\bigr)$$

Demonstrations

Two prime numbers are coprime

Let $(p_1, p_2) \in \hspace{0.05em} \mathbb{P} $ be two prime numbers.

So:

$$ \Biggl \{ \begin{align*} \mathcal{D}(p_1) = \bigl\{1, p_1 \bigr\} \\ \mathcal{D}(p_2) = \bigl\{1, p_2 \bigr\} \end{align*} $$

Their only common divisor is $ 1 $.

Then,

$$ \forall (p_1, p_2) \in \hspace{0.05em} \mathbb{P}, $$

$$ (p_1, p_2) \in \hspace{0.05em} \mathbb{P} \Longrightarrow p_1 \wedge p_2 = 1$$

The reciprocal is not true.

For example: $16 \wedge 35 = 1$

And yet these numbers are not prime.

Breakdown in prime factors

Let $n \in \mathbb{N}$ be a natural number with $n \geqslant 2$.

This number admits a finite number of divisors.

if $ n $ is prime

There is only one factor.

$$ n= p_1^{\alpha_1} \enspace \enspace (with \enspace \alpha_1 = 1) $$

if $ n $ is not prime

We know that $ n $ has at least one prime divisor.

$$ n = n_1 p_1 $$

- if $ n_1 $ is not prime

On recommence :

$$ n_1 = n_2 p_2 $$

$$ n = p_1. n_2 p_2 $$

- if $ n_2 $ is not prime

We carry out this process until the last divisor which will necessary be prime.

We could possibly come across the same prime numbers several times in a row.

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$

And finally,

All natural number $n \geqslant 2$ uniquely decomposes into a prime factors product.

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \forall i \in \mathbb{N}, \enspace (\forall p_i \in \mathbb{P}, \enspace \exists \alpha_i \in \mathbb{N}), $$

$$ n= p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i}$$

Every number higher than 2 owns at least one prime divisor

Let $n \in \mathbb{N}$ be a natural number with $n \geqslant 2$.

Two cases arise:

$ n $ is prime

Then, $ n / n $.

It has at least one prime divisor.

$ n $ is not prime

$ n $ has at least one strict divisor.

$$ \mathcal{D}(a) = \bigl\{1, d_1, d_2, \hspace{0.2em} ... \hspace{0.2em}, n \} $$

Let $ d_1 $ be the smallest stricit divisor of $n $, $d_1 $ is necessarily prime, because if it were not, it would have a divisor lower than itself which would divide $ n $, and $ d_1 $ would not be the smallest divisor of $a $.

And finally,

All natural number $n \geqslant 2$ has at least one prime divisor.

Every non-prime number higher than 4 owns at least one strict divisor

Let $n \in \{ \mathbb{N} \hspace{0.2em} \backslash\ \mathbb{P} \} $ be a non-prime integer with $n \geqslant 4$, and $d_0 \in \mathbb{N}$ a strict divisor of $n$.

So,

$$ \exists d' \geqslant d_0, \enspace n =d_0 d' $$

By multiplying both members by $d_0 $,

$$ d_0^2 \leqslant d_0d' \Longleftrightarrow d_0^2 \leqslant n $$

$$ d_0 \leqslant \sqrt{n} $$

And finally,

All non-prime natural number $n \geqslant 4 $ has at least one strict divisor $d_0 $ such as $ d_0 \leqslant \sqrt{n} $.

Coprimity link between a prime number and an integer

Let $ p \in \mathbb{P} $ be a prime number and $a \in \mathbb{Z} $ an integer.

$$ \mathcal{D}(p) = \bigl\{p, 1 \bigr\} $$

$$ \mathcal{D}(a) = \bigl\{1, \hspace{0.2em} ... \hspace{0.2em}, a \} $$

If $ p \nmid a $ then $ p \not\in \mathcal{D}(a) $. Hence the fact that:

$$ p \nmid a \hspace{0.2em} \Longrightarrow \hspace{0.2em} \mathcal{D}(a) \wedge \mathcal{D}(p) = \bigl\{1 \bigr\} $$

$$ p \nmid a \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \wedge p = 1 $$

Reciprocal

If $a \wedge p = 1$, as $p$ divides only itself and $1$, so $p \nmid a$.

$$ a \wedge p = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p \nmid a $$

And finally,

$$ \forall p \in \mathbb{P}, \enspace \forall a \in \mathbb{Z}, $$

$$ p \nmid a \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \wedge p = 1 $$

Euclid's lemma

Let $ p \in \mathbb{P} $ be a prime number, $ (a, b) \in \hspace{0.1em} \mathbb{Z}^2 $ two integers.

If $ p/ab $, then two cases arise:

$ p $ divides $ a $

Alors, le théorème est vrai

$ p $ does not divide $ a $

So, the coprimity link between a prime number and an integer tells us that as $ p \nmid a$, so $ a \wedge p = 1$.

Now, with Gauss' theorem:

$$ \forall (a, b, c) \in (\mathbb{Z})^3,\enspace a / bc \enspace et \enspace a \wedge b = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$

Which allows us to say that $ p $ divides $ b $.

And finally,

$$ \forall p \in \mathbb{P}, \enspace \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p/a) \enspace or \enspace (p/b) \qquad \bigl(Euclid's \enspace lemma \bigr) $$

Euclid's lemma corollary

Let $ (p, a, b) \in \hspace{0.1em} \mathbb{P}^3 $ be three prime numbers.

If $ p/ab $, we saw above that with Euclid's lemma, we do have this:

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p/a) \enspace or \enspace (p/b) $$

Let see what happens in both cases.

$ p $ divides $ a $

$ a $ is prime so its only divisors are $ 1 $ and $ a $.

But, by hypothesis $ p \neq 1 $ so it is a prime number, so:

$$ p/a \hspace{0.2em} \Longrightarrow \hspace{0.2em} p = a $$

$ p $ divides $ b $

These are the same hypotheses for $ b $, therefore:

$$ p/b \hspace{0.2em} \Longrightarrow \hspace{0.2em} p = b $$

And finally,

$$ \forall (p, a, b) \in \hspace{0.05em} \mathbb{P}^3, $$

$$ p/ab \hspace{0.2em} \Longrightarrow \hspace{0.2em} (p=a) \enspace or \enspace (p=b) \qquad \bigl(Euclid's \enspace lemma \enspace (corollary) \bigr)$$