Nombres premiers et Fermat : cours Terminale

Les nombres premiers sont les briques multiplicatives des entiers. La décomposition unique organise divisibilité, PGCD et calcul modulaire, tandis que le petit théorème de Fermat réduit certaines puissances.

Les applications au codage montrent l'utilité de l'arithmétique, mais un exemple scolaire de chiffrement n'est pas un protocole sécurisé pour des données réelles.

Table des Matières

Définir et tester la primalité

Nombre premier

Un entier p supérieur ou égal à 2 est premier s'il possède exactement deux diviseurs positifs : 1 et p.

Pour tester n, il suffit d'essayer les diviseurs premiers inférieurs ou égaux à $\sqrt n$ . Si n était composé, l'un de ses facteurs serait au plus égal à cette racine.

Décomposer un entier

Décomposition unique

Tout entier supérieur ou égal à 2 s'écrit comme produit de nombres premiers, de manière unique à l'ordre des facteurs près.

Cette écriture permet de lire les diviseurs, le PGCD et le PPCM par les exposants. Il faut conserver tous les facteurs et leurs multiplicités.

Comprendre l’infinité des nombres premiers

Supposons une liste finie de tous les nombres premiers et formons leur produit augmenté de 1. Aucun nombre premier de la liste ne divise ce nouvel entier. Celui-ci est premier ou possède un facteur premier absent de la liste, ce qui contredit l'hypothèse.

Contrôle utile : le nombre construit n'est pas nécessairement premier ; seul un facteur premier nouveau est garanti.

Appliquer le petit théorème de Fermat

Fermat

Si p est premier et si p ne divise pas a, alors $a^{p-1}\equiv1\pmod p$ . On a aussi $a^p\equiv a\pmod p$ pour tout entier a.

On réduit l'exposant modulo p - 1 lorsque l'hypothèse de coprimalité est vérifiée. La réciproque ne fournit pas un test de primalité universel.

Exemple de réduction d’exposant

Pour calculer $2^{100}$ modulo 13, on vérifie d'abord que 13 est premier et ne divise pas 2. Fermat donne $2^{12}\equiv1\pmod{13}$ . Comme $100=8\times12+4$ , la puissance est congrue à $2^4=16$ , donc à 3 modulo 13. La réduction porte sur l'exposant parce que les hypothèses du théorème sont satisfaites ; elle ne consiste pas à remplacer arbitrairement 100 par son reste.

Réduire une puissance modulo p — Le théorème de Fermat remplace un grand exposant par son reste modulo p - 1.

Coder et décoder un message simple

Un chiffrement affine remplace une classe x par $ax+b$ modulo n. Il est déchiffrable seulement si a possède un inverse modulo n, donc si a et n sont premiers entre eux. Cette condition doit être vérifiée avant d'écrire la fonction inverse.

choisir un codage numérique des symboles
vérifier l'existence de l'inverse
appliquer la transformation modulo n
contrôler le décodage sur chaque symbole

Comprendre une miniature de chiffrement à clé publique

Dans une miniature de RSA, on choisit deux nombres premiers p et q, puis (n=pq). Un exposant public e est choisi premier avec ((p-1)(q-1)), et l'exposant privé d vérifie (edequiv1) modulo ce produit.

Les très petits nombres utilisés en classe servent seulement à comprendre l'arithmétique. Ils n'offrent aucune sécurité réelle. La distinction entre modèle pédagogique et cryptographie opérationnelle doit rester explicite.

Encadrer la portée des résultats

Erreur fréquente : satisfaire une congruence de Fermat pour une base donnée ne prouve pas toujours qu'un entier est premier.

Contrôle utile : une petite factorisation ou un contrôle par calcul direct reste utile quand les nombres le permettent.

Le calcul modulo n fournit le langage. Bézout construit les inverses modulaires.

Les résultats sur les nombres premiers et Fermat relèvent de le programme officiel de mathématiques expertes en Terminale.