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 IIIe siè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 ap−1≡1 p.
Énoncé équivalent
Si p est un nombre premier, alors, pour tout entier naturel a, ap≡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 PGCDA ; B, puis l’écriture de AB 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 AB 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=23×32×5×72 et B=22×3×73.
b. Soit d=PGCDA ; 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α×3β×7γ.
α doit être le plus grand possible pour que 2α divise A et B, donc α=2 (en effet, 23 divise A mais pas B) ; de même, β=1 et γ=2.
Donc d=22×3×72, soit d=588.
A=588×30 et B=588×7, donc AB=588×30 588×7, donc AB=307.
c. Tout diviseur (positif) de B est de la forme 2m×3n×7q, avec m, n, q entiers, 0≤m≤2, 0≤n≤1 et 0≤q≤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×2×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.