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
Énoncé équivalent
Si p est un nombre premier, alors, pour tout entier naturel a, .
À 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 et .
b. En déduire , puis l’écriture de 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 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 : et .
b. Soit . et , 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 .
doit être le plus grand possible pour que divise A et B, donc (en effet, divise A mais pas B) ; de même, et .
Donc , soit .
et , donc , donc .
c. Tout diviseur (positif) de B est de la forme , avec m, n, q entiers, , et . 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 , 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.