La recherche de nombres premiers de plus en plus grands mobilise depuis des siècles certains passionnés. Les « grands » nombres premiers sont utilisés dans des procédés de cryptage, comme par exemple le système RSA.

I) Nombres premiers

Définition : On appelle nombre premier tout entier naturel non nul qui possède exactement deux diviseurs positifs : 1 et lui-même.

Un entier naturel distinct de 0 et 1 et non premier est dit composé.

L’ensemble des nombres premiers est infini.

À noter
Ce résultat a été démontré par Euclide au III^esiècle avant Jésus-Christ.

II) Divisibilité et nombres premiers

Tout entier naturel autre que 1 admet un diviseur premier.

Si p est un nombre premier et a un entier non divisible par p, alors a et p sont premiers entre eux.

Si un nombre premier p divise le produit ab de deux entiers, alors p divise a ou p divise b.

III) Décomposition d’un entier en produit de nombres premiers

Théorème de décomposition : Tout entier naturel autre que 0 et 1 est premier ou se décompose de manière unique, à l’ordre près, en produit de nombres premiers.

IV) Le petit théorème de Fermat

Théorème : Si p est un nombre premier et a un entier naturel non divisible par p, alors $a^{p - 1} \equiv 1 (p) .$

Énoncé équivalent

Si p est un nombre premier, alors, pour tout entier naturel a, $a^{p} \equiv a (p)$ .

À noter
Ce théorème a été énoncé par Fermat (1607-1665) en 1640, mais Fermat n’en a laissé aucune démonstration. Les premières démonstrations en sont attribuées à Leibniz (1646-1716) et Euler (1707-1783).

Méthode

Utiliser la décomposition d’entiers en produit de nombres premiers

a. Déterminer la décomposition en produit de nombres premiers des entiers $A = 17 640$ et $B = 4 116$ .

b. En déduire $PGCD (A; B)$ , puis l’écriture de $\frac{A}{B}$ sous forme de fraction irréductible.

c. Donner le nombre et la liste des diviseurs (positifs) de B.

Conseils
b. Utilisez le fait que, si d est un diviseur commun à A et B, et si p est un nombre premier apparaissant dans la décomposition de d, alors p divise A et B, donc p apparaît dans les décompositions de A et de B en produits de nombres premiers.
Le quotient $\frac{A}{B}$ peut être simplifié par tout diviseur commun à A et à B.
c. Comme à la question précédente, utilisez le fait que, si d est un diviseur de B et p un nombre premier apparaissant dans sa décomposition, alors p divise B, donc p est également présent dans la décomposition de B en produit de nombres premiers.

Solution

a. On a : $A = 2^{3} \times 3^{2} \times 5 \times 7^{2}$ et $B = 2^{2} \times 3 \times 7^{3}$ .

b. Soit $d = PGCD (A; B)$ . $d | A$ et $d | B$ , donc tout diviseur premier de d est aussi un diviseur premier de A et de B, donc les diviseurs premiers de d sont 2, 3 et 7. On en déduit que $d = 2^{α} \times 3^{β} \times 7^{γ}$ .

$α$ doit être le plus grand possible pour que $2^{α}$ divise A et B, donc $α = 2$ (en effet, $2^{3}$ divise A mais pas B) ; de même, $β = 1$ et $γ = 2$ .

Donc $d = 2^{2} \times 3 \times 7^{2}$ , soit $d = 588$ .

$A = 588 \times 30$ et $B = 588 \times 7$ , donc $\frac{A}{B} = \frac{588 \times 30}{588 \times 7}$ , donc $\frac{A}{B} = \frac{30}{7}$ .

c. Tout diviseur (positif) de B est de la forme $2^{m} \times 3^{n} \times 7^{q}$ , avec m, n, q entiers, $0 \leq m \leq 2$ , $0 \leq n \leq 1$ et $0 \leq q \leq 2$ . On a donc 3 valeurs possibles pour m, 2 valeurs pour n et 3 valeurs pour q. Le nombre de diviseurs (positifs) de B est donc $3 \times 2 \times 3$ , soit 18.

Ces 18 diviseurs sont : 1, 2, 3, 4, 6, 7, 12, 14, 21, 196, 294, 343, 588, 686, 1 029, 1 372, 2 058, 4 116.