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