Nombres premiers

Merci !

Fiches
Classe(s) : Tle Générale | Thème(s) : Graphes et matrices


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 ap11 p.

Énoncé équivalent

Si p est un nombre premier, alors, pour tout entier naturel a, apa 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=17640 et B=4116.

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.

30 et 7 sont premiers entre eux, donc la fraction 307 est une fraction irréductible.

c. Tout diviseur (positif) de B est de la forme 2m×3n×7q, avec m, n, q entiers, 0m2, 0n1 et 0q2. 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.

Annabac est gratuit en septembre !

Inscris-toi pour en profiter.