The properties of prime numbers

Two prime numbers are coprime

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

So:

Their only common divisor is \( 1 \).

Then,

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 (\text{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.

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

   It has at least one prime divisor.

2. \( n \) is not prime

   \( n \) has at least one strict divisor.

   $$ \mathcal{D}(n) = \bigl \{1, d_1, d_2, \ ... \, 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 \(n \).

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:

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

And finally,

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 \mid 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 \mid bc) \text{ and } (a \wedge b = 1) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c $$

   Which allows us to say that \( p \) divides \( b \).

And finally,

Euclid's lemma corollary

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

If \( p \mid 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 \mid a \hspace{0.2em} \Longrightarrow \hspace{0.2em} p = a $$

2. \( p \) divides \( b \)

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

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

And finally,

Recap table of the prime numbers properties