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.
$$ \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$$
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 $$
$$ \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) $$
$$ \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)$$
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.
Let \(n \in \mathbb{N}\) be a natural number with \(n \geqslant 2\).
This number admits a finite number of divisors.
There is only one factor.
$$ n= p_1^{\alpha_1} \enspace \enspace (with \enspace \alpha_1 = 1) $$
We know that \( n \) has at least one prime divisor.
$$ n = n_1 p_1 $$
On recommence :
$$ n_1 = n_2 p_2 $$
$$ n = p_1. n_2 p_2 $$
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}$$
Let \(n \in \mathbb{N}\) be a natural number with \(n \geqslant 2\).
Two cases arise:
Then, \( n / n \).
It has at least one prime divisor.
\( 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.
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} \).
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 $$
ReciprocalIf \(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 $$
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:
Alors, le théorème est vrai
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) $$
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.
\( 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 $$
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)$$