A. Nombres premiers entre eux

1) Définition et propriétés

Soient $a$ et $b$ deux entiers relatifs non nuls. On dit que $a$ et $b$ sont premiers entre eux si leur PGCD est égal à 1.

Les seuls diviseurs communs de $a$ et $b$ sont alors $1$ et $- 1$.

Exemples
• On a : $PGCD\left( {4;17} \right) = 1$, donc 4 et 17 sont premiers entre eux.
• 60 et 135 sont tous les deux divisibles par 3 ; donc ils ne sont pas premiers entre eux.

Remarque
Soient $a$ et $b$ deux entiers relatifs non nuls et $d$ un diviseur commun à $a$ et $b$.
On a : $\left\{ \begin{array}{l}a = da'\\b = db'\end{array} \right.$ et $PGCD\left( {a;b} \right) =$ $b \times PGCD\left( {a';b'} \right)$.
$d$ est le PGCD de $a$ et $b$ si et seulement si $a’$ et $b’$ sont premiers entre eux.

a) Théorème de Bézout
Soient $a$, $b$ des entiers. Il existe des entiers $u$, $v$ $\in$ $\mathbb{Z}$ tels que $au + bv =$ $PGDC\left( {a,b} \right)$
La preuve découle de l’algorithme d’Euclide. Les entiers $u$, $v$ ne sont pas uniques. Les entiers $u$, $v$ sont des coefficients de Bézout. Ils s’obtiennent en « remontant » l’algorithme d’Euclide.

Corollaires du théorème de Bézout

Corollaire 1.
Si $d|a$ et $d|b$ alors $d|PGCD(a,b)$.

Corollaire 2.
Soient $a$, $b$ deux entiers. $a$, $b$ sont premiers entre eux si et seulement si il existe $u$, $v$ $\in$ $\mathbb{Z}$ tels que : $au + bv = 1$

Exemples
On : $49 \times 54 +$ $115 \times \left( { - 23} \right) = 1$; donc : $PGCD\left( {49,115} \right)$ $= 1$.
Deux entiers consécutifs non nuls $n$ et $n + 1$ sont premiers entre eux.
En effet, on a: $n \times \left( { - 1} \right) +$ $\left( {n + 1} \right) \times \left( 1 \right) = 1$.

b) Théorème de Gauss
Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.
Si $a$ divise $bc$ et si a et b sont premiers entre eux, alors $a$ divise $c$.

Démonstration
Il existe trois entiers relatifs $k.u$ et tels que : $bc = ka$ et $au + bv = 1$.
On a $auc + bvc = c$ $\Rightarrow a\left( {uc + kv} \right)$.
On en déduit que $a$ divise $c$.

Conséquence
Soit $a$, $b$ et $c$ trois entiers relatifs non nuls.
• Si $a$ et $b$ sont premiers entre eux et si $a$ et $c$ sont premiers entre eux, alors $a$ et $bc$ sont premiers entre eux.
• Si $a$ et $b$ divisent $c$ et si $a$ et $b$ sont premiers entre eux, $ab$ divise $c$ ;
• Si $a$ et $b$ sont premiers entre eux, alors : $PPCM\left( {a;b} \right)$ $= ab$.

Propriété
Soit $n$ un entier naturel non nul et $a$, $b$, $c$ trois entiers relatifs ($a \ne 0$).
Si $a$ et premier avec $n$ et si $ab \equiv ac\left[ n \right]$, alors $b \equiv c\left[ n \right]$.

c) Théorème de Fermat
Soit $a$ un nombre entier non nul, et $p$ un nombre premier. Si $p$ ne divise pas $a$, alors il s’en suit la congruence suivante : ${a^{p - 1}} \equiv 1\left[ p \right]$

2) Relation entre le PGCD et le PPCM de deux entiers naturels

Soit $a$ et $b$ deux entiers naturels non nuls, $\delta$ leur PGCD et $\mu$ leur PPCM, On a : $\delta \mu = ab$
Soient $a$ et $b$ deux dont le $PGCD\left( {a;b} \right)$ $= 1$ ; On dit alors que $a$ et $b$ sont premiers entre eux ou qu’ils sont étrangers.

3) Résolution dans $\mathbb{Z}^2$ des équations Diophantiennes : Équations du type $ax + by = c$ (E)

On appelle équation Diophantienne, toute équation de $\mathbb{Z}^2$ dont l’ensemble solution se présente sous forme de couple $\left( {x;y} \right)$.

1. L’équation (E) possède des solutions $\left( {x;y} \right) \in$ $\mathbb{Z}$, si et seulement si $PGCD(a,b)|c$. (conséquence du théorème de Bézout.)
2. Si $PGCD(a,b)|c$ alors il existe même une infinité de solutions entières et elles sont exactement les $\left( {x;y} \right) =$ $\left( {{x_0} + \alpha k;{y_0} + \beta k} \right)$ avec ${{x_0}}$, ${{y_0}}$, $\alpha$, $\beta$ $\in$ $\mathbb{Z}$, fixés et $k$ parcourant $\mathbb{Z}$, .

B. Les nombres premiers

Un nombre premier $p$ est un entier supérieur à 2 dont les seuls diviseurs positifs sont 1 et $p$.

Propriété
Tout entier naturel $n$ diffèrent de 0 et 1 admet au moins un diviseur premier

1) L'ensemble des nombres premiers

L'algorithme suivant dû à Ératosthène de Cyrène (276-194 av. J.-C.), permet de déterminer les nombres premiers inférieurs à un nombre donné $n$. On écrit les entiers naturels successifs compris entre 1 et $n$.
• On barre 1 qui n'est pas premier.
• Le nombre 2 est premier. On barre tous les multiples de 2 autres que 2.
• Le premier nombre non barré est 3. qui est donc premier.
On barre tous les multiples de 3 autres que 3.
• On itère le procédé jusqu'à la fin du tableau.

Propriété
Il existe une infinité de nombres premiers.

2) Décomposition en produit de facteurs premiers

Théorème fondamental
Soit $n$ entier naturel $\left( {n \ge 2} \right)$.
• Il existe des nombres premiers ${p_1}$, ${p_2}$, …, ${p_k}$ et des entiers naturels non nuls ${\alpha _1}$, ${\alpha _2}$, … , ${\alpha _k}$ tels que :
$n = p_1^{{\alpha _1}} \times p_2^{{\alpha _2}}$ $\times ... \times p_k^{{\alpha _k}}$ et ${p_1} \prec {p_2} \prec$ $... \prec {p_k}$
• Cette décomposition est unique