possède plusieurs produits possibles. En décomposant jusqu'aux nombres premiers, tu retrouves toujours \(2^2\times3\times5\), à l'ordre près. Cette stabilité rend la factorisation utile pour compter les diviseurs, reconnaître les carrés ou comparer deux entiers.
Prérequis. Division euclidienne, congruences, PGCD, Bézout et Gauss. Savoir distinguer une implication de sa réciproque est particulièrement important pour les tests de primalité.
L'énoncé de Fermat appartient au programme. Sa preuve par permutation et l'application RSA sont des prolongements guidés ; ils utilisent exclusivement les outils construits dans ces fiches.
L'idée avant la formule
Pourquoi arrêter les essais à la racine carrée ?
Si \(n=ab\) avec \(1<a\le b\), le plus petit facteur vérifie \(a^2\le ab=n\). Dans chaque paire de facteurs, l'un se trouve donc avant ou sur la racine carrée. Pour 91, tester jusqu'à 9 suffit : le facteur 7 révèle \(91=7\times13\). La borne inclut les carrés, comme 49 et son facteur 7.
L'unicité transforme un dessin de facteurs en preuve
Un arbre de décomposition suggère les facteurs premiers. Pour assurer que deux arbres donnent la même liste, nous utiliserons Gauss : un premier qui divise un produit doit diviser l'un de ses facteurs. C'est ce résultat qui permettra de comparer les facteurs un par un.
Les puissances peuvent revenir à 1
Modulo 5, les puissances de 2 donnent 2, 4, 3, 1, puis recommencent. Fermat garantira un retour à 1 après \(p-1\) étapes lorsque le module p est premier et ne divise pas la base. Il ne dira pas que cette période est la plus courte, ni que toute congruence réussie prouve la primalité.
Le cours formel
Nombres premiers et critère de recherche
2 est le seul nombre premier pair : un pair supérieur à 2 possède le diviseur 2 distinct de 1 et de lui-même. Être impair ne suffit pas : 9, 15 et 21 sont composés.
Il existe une infinité de nombres premiers
Décomposition en facteurs premiers
Lire les diviseurs, le PGCD et les carrés
Si \(d\mid n\), on a \(n=dq\) pour un entier positif \(q\). Dans leurs factorisations premières, les exposants de \(d\) et de \(q\) s'additionnent pour donner ceux de \(n\). Chaque exposant \(\beta_j\) de \(d\) est donc entre 0 et \(\alpha_j\) ; aucun premier absent de \(n\) ne peut apparaître. Réciproquement, pour tout tel choix, le produit \(q=\prod p_j^{\alpha_j-\beta_j}\) est un entier et \(dq=n\), donc \(d\) est bien un diviseur.
Pour le premier exposant, on a \(\alpha_1+1\) choix en comptant zéro ; pour chacun, \(\alpha_2+1\) choix pour le deuxième, et ainsi de suite. L'unicité de la factorisation garantit que deux listes d'exposants différentes donnent deux diviseurs différents. D'où le produit des nombres de choix.
Si \(n=m^2\) et \(m=\prod p_j^{\gamma_j}\), alors \(n=\prod p_j^{2\gamma_j}\) : tous ses exposants sont pairs. Réciproquement, si \(\alpha_j=2\gamma_j\) pour chaque \(j\), l'entier \(m=\prod p_j^{\gamma_j}\) vérifie \(m^2=n\). Cela prouve les deux sens de la caractérisation des carrés. Le nombre 1 est aussi un carré, \(1=1^2\), correspondant au produit vide.
Petit théorème de Fermat : deux versions
Trois algorithmes exacts
Crible d'Ératosthène
Pour lister les premiers jusqu'à N, marque tous les entiers de 2 à N comme candidats. À chaque premier p encore marqué, supprime ses multiples à partir de \(p^2\) ; les multiples plus petits ont déjà un facteur premier inférieur à p.
def crible(N):
if N < 2:
return []
premier = [True] * (N + 1)
premier[0] = premier[1] = False
p = 2
while p*p <= N:
if premier[p]:
for k in range(p*p, N + 1, p):
premier[k] = False
p += 1
return [k for k in range(2, N + 1) if premier[k]]
Le critère du diviseur inférieur ou égal à la racine carrée garantit qu'à l'arrêt aucun entier composé ne reste marqué.
Décomposition
def facteurs(n):
if n < 2:
raise ValueError("n >= 2 requis")
resultat = []
d = 2
while d*d <= n:
while n % d == 0:
resultat.append(d)
n //= d
d += 1
if n > 1:
resultat.append(n)
return resultat
Le produit des facteurs déjà extraits et de n courant reste égal au nombre initial. Après les divisions par les petits facteurs, le n final, s'il est supérieur à 1, est premier ; sinon il aurait encore un diviseur au plus égal à sa racine carrée.
Exponentiation rapide modulaire
def puissance_rapide(a, N, m):
if N < 0 or m < 1:
raise ValueError("N >= 0 et m >= 1 requis")
r, b, e = 1 % m, a % m, N
while e > 0:
if e % 2 == 1:
r = (r*b) % m
b = (b*b) % m
e //= 2
return r
Pourquoi ce code calcule la bonne puissance. Les variables sont un résultat partiel \(r\), une base courante \(b\) et un exposant restant \(e\). Au départ \(r=1\bmod m\), \(b=a\bmod m\), \(e=N\), donc \(rb^e\equiv a^N\).
Si \(e=2k\) est pair, \(rb^e=r(b^2)^k\). Mettre la base au carré et diviser l'exposant par deux conserve donc le produit représenté. Si \(e=2k+1\) est impair, \(rb^e=(rb)(b^2)^k\) : il faut d'abord transférer un facteur \(b\) dans \(r\), puis faire les mêmes changements. C'est exactement la branche if, suivie des deux affectations. Les réductions modulo \(m\) conservent la congruence et évitent de stocker de trop grands entiers.
À chaque tour avec \(e>0\), la division entière par 2 donne un entier plus petit, donc la boucle s'arrête à \(e=0\). L'invariant devient alors \(r\equiv a^N\) car \(b^0=1\). Comme \(r\) est entre 0 et \(m-1\), c'est le reste recherché. Pour \(N=0\), aucun tour n'est nécessaire ; le reste de 1 est déjà correct. Pour \(m=1\), il vaut 0. Diviser l'exposant par deux à chaque tour explique pourquoi quelques tours suffisent même pour un grand exposant.
Boîte à outils : factoriser ou réduire ?
Deux premières questions qui évitent des calculs inutiles
Cherches-tu à prouver qu'un nombre est premier, ou à calculer un reste ? Dans le premier cas, un test de diviseurs peut être concluant ; dans le second, une factorisation complète du nombre étudié est souvent superflue. Le petit théorème de Fermat réduit les puissances lorsque le module est premier, tandis que la division euclidienne garde les calculs de petite taille.
Diviseurs soumis à une condition
Pour \(n=2^4\times3^2\times5\), tout diviseur positif s'écrit \(2^a3^b5^c\), avec \(0\le a\le4\), \(0\le b\le2\), \(0\le c\le1\). Il y a 5×3×2=30 diviseurs en tout. Un diviseur impair impose a=0 : il en reste 3×2=6. Un diviseur carré impose a pair, b pair et c=0 : les choix sont a dans {0,2,4}, b dans {0,2}, donc six diviseurs carrés. Le calcul se construit à partir des exposants autorisés, pas à partir d'une nouvelle formule à mémoriser.
Pourquoi les candidats non premiers du code ne gênent pas
L'algorithme de factorisation essaie d=2,3,4,5,..., sans calculer d'avance la liste des premiers. Si d est composé, ses facteurs premiers plus petits ont déjà été totalement retirés du reste n ; il ne peut donc plus le diviser. Ce passage supplémentaire ralentit un peu l'algorithme, mais ne change pas sa correction. Si le reste devient 1, la factorisation est terminée ; si \(d^{2}\) le dépasse, le reste éventuellement supérieur à 1 est premier.
Exercices progressifs
Les exercices 1 à 5 consolident les bases, 6 à 10 relient les notions et 11 à 15 demandent davantage d'initiative. Cherche d'abord, puis utilise un indice si tu en as besoin.
Exercice 1 : Définition précise ★☆☆
Parmi 1, 2, 21, 29 et 49, lesquels sont premiers ? Justifie.
Exercice 2 : Factorisation ★☆☆
Décompose 360 et 504 en facteurs premiers.
Exercice 3 : Nombre de diviseurs ★☆☆
Combien 360 possède-t-il de diviseurs positifs ?
Exercice 4 : PGCD par facteurs ★☆☆
Calcule le PGCD et le PPCM de 360 et 504.
Exercice 5 : Fermat direct ★☆☆
Calcule le reste de \(2^{30}\) modulo 7.
Exercice 6 : Primalité de 127 ★★☆
Prouve que 127 est premier.
Exercice 7 : Compléter un carré ★★☆
Trouve le plus petit entier positif k tel que \(756k\) soit un carré.
Exercice 8 : Grande puissance ★★☆
Calcule \(5^{2026}\) modulo 13.
Exercice 9 : Un inverse avec Fermat ★★☆
Utilise Fermat pour exprimer un inverse de 3 modulo 7 et donne son représentant entre 0 et 6.
Exercice 10 : Une réciproque fausse ★★☆
Vérifie que 341 est composé mais que \(2^{340}\equiv1\pmod{341}\).
Exercice 11 : Un témoin de composition ★★★
Calcule \(2^{14}\) modulo 15. Que peut-on en déduire sans factoriser 15 ?
Exercice 12 : Un exposant nécessaire ★★★
Pour \(n\ge2\), montre que si \(2^n-1\) est premier, alors n est premier. La réciproque est-elle vraie ?
Exercice 13 : Crible ★★★
Exécute le crible jusqu’à 30. Pourquoi peut-on s’arrêter après le passage de 5 ?
Exercice 14 : Puissance rapide ★★★
Calcule \(7^{13}\pmod{11}\) par carrés successifs, puis compare à Fermat.
Exercice 15 : Un argument d’irrationalité ★★★
Prouve que \(\sqrt6\) est irrationnel en utilisant l’unicité de la factorisation.
Problème : Pour aller plus loin
Ce prolongement est accessible à partir du cours : les résultats supplémentaires sont guidés, et leur mémorisation n'est pas un préalable. Tu peux répartir la recherche sur plusieurs séances.
et \(e=3\). Un message est un entier \(m\in\{0,\ldots,54\}\) ; son chiffré c est le reste de \(m^3\) modulo 55. Ce petit modèle sert au calcul : ces nombres sont trop petits pour une utilisation réelle. Durée indicative : 90 minutes.
Partie I : Construire l'exposant inverse
Calcule \((p-1)(q-1)\) et vérifie \(\gcd(3,40)=1\).
Trouve d entre 1 et 39 tel que \(3d\equiv1\pmod{40}\).
Chiffre \(m=7\). Montre que déchiffrer par \(c^d\) revient à calculer \(m^{81}\) modulo 55.
Partie II : Une preuve valable pour tous les messages
Si 5 ne divise pas m, utilise Fermat pour montrer \(m^{81}\equiv m\pmod5\). Traite séparément le cas \(5\mid m\).
Fais de même modulo 11.
En utilisant Gauss, conclus \(m^{81}\equiv m\pmod{55}\). Pourquoi fallait-il traiter aussi les multiples de 5 ou de 11 ?
Partie III : Mettre en œuvre
Déchiffre le résultat de la partie I par carrés successifs.
Chiffre puis déchiffre \(m=5\) en expliquant pourquoi la preuve reste valable.
Écris deux fonctions Python sur les entiers, et une vérification pour les 55 messages possibles.
donc le code chiffré est \(c=13\). Comme \(c\equiv m^3\pmod{55}\), élever à la puissance 27 conserve la congruence : \(c^{27}\equiv(m^3)^{27}=m^{81}\). Il reste à prouver que cette dernière puissance retrouve \(m\).
Partie II : Couvrir aussi les bases non inversibles
1. Si 5 ne divise pas \(m\), Fermat donne \(m^4\equiv1\pmod5\). Écrivons \(81=1+4\times20\) :
Si 5 divise \(m\), les deux membres \(m^{81}\) et \(m\) sont divisibles par 5, donc encore congrus. Les deux cas couvrent tous les messages modulo 5.
2. Si 11 ne divise pas \(m\), Fermat donne \(m^{10}\equiv1\pmod{11}\). Comme \(81=1+10\times8\), \(m^{81}=m(m^{10})^8\equiv m\). Si 11 divise \(m\), les deux membres sont congrus à zéro. La conclusion vaut donc aussi pour tous les messages modulo 11.
3. La différence \(D=m^{81}-m\) est divisible par 5 et 11. Écrivons \(D=5k\). Comme \(11\mid5k\) et \(\gcd(11,5)=1\), Gauss donne \(k=11\ell\). Ainsi \(D=55\ell\), donc \(m^{81}\equiv m\pmod{55}\). Le déchiffrement renvoie un reste entre 0 et 54, tout comme le message initial ; deux représentants congrus dans cet intervalle sont égaux. Il retrouve donc exactement \(m\). Omettre les cas divisibles par 5 ou 11 aurait laissé par exemple \(m=5\) sans preuve.
Partie III : Calculer et vérifier
1. Pour \(c=13\), les carrés successifs modulo 55 sont : \(13^2=169\equiv4\) ; \(13^4\equiv4^2=16\) ; \(13^8\equiv16^2=256\equiv36\) ; \(13^{16}\equiv36^2=1296\equiv31\). Les restes se vérifient par \(169=3\times55+4\), \(256=4\times55+36\), \(1296=23\times55+31\).
Comme \(27=16+8+2+1\), \(13^{27}\equiv31\times36\times4\times13\). Réduisons progressivement : \(31\times36=1116\equiv16\) ; \(16\times4=64\equiv9\) ; \(9\times13=117\equiv7\). On retrouve le message 7.
donc \(c=15\). Les carrés donnent \(15^2=225\equiv5\), \(15^4\equiv25\), \(15^8\equiv625\equiv20\), \(15^{16}\equiv400\equiv15\). Alors \(15^{27}\equiv15\times20\times5\times15\). Les produits réduits valent successivement \(300\equiv25\), \(125\equiv15\), \(225\equiv5\). Le message 5 est bien retrouvé. Il est non inversible modulo 55, mais la preuve de la partie II traitait explicitement ce cas.
3. Python calcule ces puissances exactement avec trois arguments dans pow : la base, l'exposant et le module.
def chiffrer(m):
return pow(m, 3, 55)
def dechiffrer(c):
return pow(c, 27, 55)
assert all(dechiffrer(chiffrer(m)) == m for m in range(55))
range(55) fournit tous les messages de 0 à 54. Pour chacun, on chiffre puis déchiffre et on compare au message initial. all exige que les 55 comparaisons soient vraies ; assert signale une erreur si ce n'est pas le cas. Ce contrôle exhaustif vérifie ces valeurs, tandis que la partie II explique mathématiquement le fonctionnement et le traitement des cas non inversibles.
Faire le point par une variante autonome
Essaie cette variante sans relire le corrigé précédent. Explique le choix de ta méthode, puis utilise les contrôles pour décider quelle notion retravailler.
Fiche-mémoire
Premier : entier au moins 2 ayant exactement deux diviseurs positifs.
Un composé a un diviseur premier au plus égal à sa racine carrée.
Un premier divisant un produit divise au moins un facteur ; les facteurs premiers d'un entier sont uniques à l'ordre près.
Fermat : \(a^{p-1}\equiv1\pmod p\) si p est premier et \(p\nmid a\) ; \(a^p\equiv a\) pour tout entier a.
Fermat peut réfuter une primalité ; une congruence réussie pour une base ne la prouve pas.
Crible, divisions successives et carrés successifs répondent à trois questions différentes : lister, factoriser, calculer une puissance.
Contrôle. Ai-je inclus la borne racine carrée ? Vérifié les hypothèses de Fermat ? Réduit l'exposant modulo p-1 ? Évité de confondre un nombre et un diviseur premier de ce nombre ?
Maîtrise du chapitre
Validation contrôlée
Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.