The properties of prime numbers

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

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

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

Two prime numbers are coprime

Two prime numbers are coprime.

$$ (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.

$$ 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

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

Euclid's lemma

$$ 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

$$ 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,

$$ (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.

1. if \( n \) is prime

There is only one factor.

$$ n= p_1^{\alpha_1} \enspace \enspace (with \enspace \alpha_1 = 1) $$
2. if \( n \) is not prime

We know that \( n \) has at least one prime divisor.

$$ n = n_1 p_1 $$
1. - if \( n_1 \) is not prime

On recommence :

$$ n_1 = n_2 p_2 $$
$$ n = p_1. n_2 p_2 $$
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.

$$ 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:

1. \( n \) is prime

Then, \( n / n \).

It has at least one prime divisor.

2. \( 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,

By multiplying both members by \(d_0 \),

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.

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

Reciprocal

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

And finally,

$$ 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:

1. \( p \) divides \( a \)

Alors, le théorème est vrai

2. \( 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,

$$ 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:

Let see what happens in both cases.

1. \( 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 $$
2. \( p \) divides \( b \)

These are the same hypotheses for \( b \), therefore:

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

And finally,

$$ 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)$$