À retenir : Trois niveaux de lecture

Parcours principal :

unités 1 à 12, puis bilan de l’unité 17. On y construit les notions et les méthodes du chapitre.

Pour consolider :

boîtes « Si tu t’es trompé », rappels et reprises différées. Elles ne supposent pas que tous les acquis anciens soient déjà sûrs.

Pour aller plus loin :

unités 13 à 16. Les problèmes facultatifs proposés par le programme sont distingués du petit complément sur Wilson. Aucun de ces prolongements n’est nécessaire pour comprendre le parcours principal.

Rappel utile : Lire les noms des blocs

Une définition fixe un sens ; elle ne se démontre pas. Une notation fixe une écriture. Une propriété, une proposition et un théorème sont des résultats : ces noms ne correspondent pas à trois degrés de vérité. Un lemme sert dans une preuve ultérieure ; un corollaire découle d’un résultat déjà établi. Une caractérisation ou une équivalence demande les deux sens. Un contre-exemple suffit à réfuter une affirmation universelle. Une image pour comprendre ne remplace jamais une démonstration.

À retenir : Ce que tu vas apprendre

Distinguer un nombre premier d’un nombre composé, comprendre pourquoi 0 et 1 sont exclus, et ne plus confondre « premier » avec « premiers entre eux ».

Avant de commencer : Trois questions courtes

1. Que signifie \(4\mid20\) ? 2. Quels sont les diviseurs positifs de 1 ? 3. Les entiers 8 et 15 ont-ils un diviseur commun plus grand que 1 ?

Correction.

\(4\mid20\) signifie \(20=4k\) pour un entier \(k\) ; ici \(k=5\). Le seul diviseur positif de 1 est 1. Les listes \(\{1,2,4,8\}\) et \(\{1,3,5,15\}\) ont seulement 1 en commun. Si le symbole \(\mid\) ou le mot « positif » t’a gêné, commence par le rappel suivant.

Rappel utile : Entiers et divisibilité

On note \(\mathbb{N}=\{0,1,2,\ldots\}\), \(\mathbb{N}^*=\{1,2,3,\ldots\}\) et \(\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}\).

Pour \(a,b\in\mathbb{Z}\), dire que \(a\) divise \(b\), et écrire \(a\mid b\), signifie qu’il existe \(k\in\mathbb{Z}\) tel que \(b=ak\). Le nombre \(b\) est alors un multiple de \(a\). La notation \(a\nmid b\) signifie que \(a\) ne divise pas \(b\). Ainsi \(3\mid(-12)\) car \(-12=3(-4)\), mais \(3\nmid10\).

Pour chercher les diviseurs positifs d’un entier positif, on ne garde que les diviseurs strictement supérieurs à 0. Les diviseurs négatifs sont leurs opposés.

Définition : Nombre premier et nombre composé

Un entier naturel \(p\) est premier s’il possède exactement deux diviseurs positifs distincts : 1 et lui-même. Il vérifie donc \(p\ge2\). Un entier naturel \(n\ge2\) qui n’est pas premier est composé.

Exemple expliqué : Lire une liste de diviseurs

Pour 3, le seul entier à vérifier entre 1 et 3 est 2 : \(3=2\times1+1\), donc 2 ne divise pas 3. Les deux diviseurs 1 et 3 sont bien les seuls. Pour réfuter la primalité de 9, un seul diviseur supplémentaire, 3, suffit.

Remarque : Pourquoi pas 0, 1 ou un entier négatif ?

Tout entier strictement positif divise 0, car \(0=d\times0\) : 0 possède une infinité de diviseurs positifs, et non deux. Le nombre 1 en possède un seul. Les entiers négatifs ne sont pas des nombres premiers avec la définition adoptée ici ; on peut en revanche décomposer leur valeur absolue.

Exclure 1 évite aussi d’ajouter à volonté des facteurs 1 à une décomposition. Ce dernier argument explique l’intérêt de la convention, mais la définition « exactement deux diviseurs » suffit à décider.

Caractérisation : Reconnaître un entier composé

Pour \(n\in\mathbb{N}\), \(n\ge2\), les deux affirmations suivantes sont équivalentes :

1. \(n\) est composé ;

2. il existe des entiers \(a,b\ge2\) tels que \(n=ab\).

Démonstration : Les deux sens sont nécessaires

Si \(n\) est composé, il a un diviseur positif \(a\) différent de 1 et de \(n\). Ainsi \(1<a<n\) et \(n=ab\) avec \(b\) entier positif. Comme \(a<n\), on a \(b>1\). Les entiers \(a\) et \(b\) sont donc au moins égaux à 2.

Réciproquement, si \(n=ab\) avec \(a,b\ge2\), alors \(a\mid n\) et \(1<a\le n/2<n\). Il existe un diviseur de \(n\) autre que 1 et \(n\) : \(n\) n’est pas premier. Puisque \(n\ge2\), il est composé.

Représentation intuitive : Des paquets rectangulaires

Disposer \(n\) jetons en \(a\) rangées de \(b\) jetons traduit \(n=ab\). Un rectangle avec au moins deux rangées et deux colonnes révèle donc un nombre composé. Cette représentation donne du sens à un facteur.

Description : à gauche, douze points forment trois lignes de quatre ; à droite, treize points sont alignés. Pour 13, aucune autre disposition rectangulaire entière n’existe, à rotation près.

Limite :

ne pas réussir à dessiner un autre rectangle n’est pas une preuve de primalité. Il faut justifier que toutes les possibilités ont été examinées ; l’unité suivante fournit une borne efficace.

Définition : Deux entiers premiers entre eux

Deux entiers non tous deux nuls sont premiers entre eux si leur seul diviseur positif commun est 1, autrement dit si leur PGCD vaut 1. Cela ne signifie pas que chacun des deux est un nombre premier.

Exemple expliqué : Comparer les deux expressions

Les entiers 8 et 15 sont composés (\(8=2\times4\) et \(15=3\times5\)), mais les listes de diviseurs du repérage montrent qu’ils sont premiers entre eux. Les nombres 5 et 5 sont premiers, mais pas premiers entre eux : 5 est un diviseur commun supérieur à 1.

Deux nombres premiers distincts sont premiers entre eux : un diviseur positif de l’un vaut 1 ou ce premier ; ce dernier ne peut diviser l’autre premier distinct.

Proposition : Le seul nombre premier pair

Le nombre 2 est premier. Tout nombre premier différent de 2 est impair.

Démonstration : Utiliser un diviseur interdit

Les diviseurs positifs de 2 sont 1 et 2. Si \(n\) est pair et strictement supérieur à 2, alors \(n=2k\) avec \(k\ge2\) ; il est composé. Un nombre premier qui n’est pas 2 ne peut donc pas être pair.

Piège à éviter : La réciproque n’est pas automatique

« Premier différent de 2 \(\Rightarrow\) impair » est vrai. « Impair \(\Rightarrow\) premier » est faux : \(9=3\times3\) est un contre-exemple. Pour prouver une implication, on part de son hypothèse ; pour la réfuter, on cherche un cas où l’hypothèse est vraie et la conclusion fausse.

Méthode : Décider avec la définition

Premier geste :

vérifier que le nombre est un entier au moins égal à 2. Si l’on trouve un produit \(ab\) avec \(a,b>1\), on conclut immédiatement « composé ». Si l’on prétend conclure « premier », il faut exclure tous les diviseurs positifs autres que 1 et le nombre. Pour les grandes valeurs, la méthode de la racine carrée remplacera cette vérification longue.

Contrôle :

dans un produit qui sert de preuve de composition, aucun facteur ne doit valoir 1. L’écriture \(23=1\times23\) ne prouve rien.

À toi : Classer puis expliquer

Guidé.

Classe 0, 1, 2, 15 et 25 : premier, composé, ou ni l’un ni l’autre. Pour un composé, donne un produit de deux facteurs supérieurs à 1.

Tentative.

9 et 10 sont-ils premiers ? Sont-ils premiers entre eux ?

Justification personnelle.

Explique pourquoi une multiplication par 1 ne permet pas de conclure qu’un nombre est composé.

Variation.

L’affirmation « deux entiers impairs sont toujours premiers entre eux » est-elle vraie ? Un seul exemple favorable suffit-il ?

Indices progressifs : Choisir la bonne question

Pour un nombre, compte les diviseurs ou trouve un produit non trivial. Pour un couple, cherche les diviseurs communs. Pour réfuter « toujours », essaie deux multiples impairs de 3.

Correction expliquée : Classer puis expliquer

0 et 1 ne sont ni premiers ni composés. 2 est premier. \(15=3\times5\) et \(25=5\times5\) sont composés. \(9=3\times3\) et \(10=2\times5\) sont aussi composés. Leurs diviseurs positifs sont respectivement \(1,3,9\) et \(1,2,5,10\) ; seul 1 est commun. Ils sont donc premiers entre eux.

Une réponse correcte à la justification doit mentionner les deux facteurs strictement supérieurs à 1 : tous les entiers vérifient \(n=1\times n\), y compris les premiers.

Enfin 9 et 15 sont impairs, mais ont le diviseur commun 3. L’affirmation est fausse. Un cas favorable ne prouve pas une affirmation portant sur tous les couples ; un contre-exemple la réfute.

Si tu t’es trompé : Si tu as confondu premier et premiers entre eux

Erreur :

« 8 et 15 ne sont pas premiers entre eux, car 8 n’est pas premier. »

Rappel :

ce sont les diviseurs communs qui comptent.

Exemple plus simple corrigé :

4 et 9 sont composés, mais les listes \(1,2,4\) et \(1,3,9\) n’ont que 1 en commun.

Nouvel essai :

6 et 25 sont-ils premiers entre eux ?

Correction :

\(1,2,3,6\) et \(1,5,25\) n’ont que 1 en commun : oui.

Retour :

refais maintenant le cas 8 et 15 en écrivant les deux listes.

Pour réparer une erreur : Dans deux jours, sans ouvrir les définitions

Classe 1, 3, 21 ; compare ensuite les couples \((4,15)\) et \((3,21)\).

Aide :

une liste de diviseurs suffit.

Critère :

donner une raison différente pour une propriété individuelle et une propriété du couple.

Correction :

1 est exclu, 3 est premier, \(21=3\times7\) est composé. \(1,2,4\) et \(1,3,5,15\) n’ont que 1 en commun : 4 et 15 sont premiers entre eux. 3 et 21 ne le sont pas : leur PGCD vaut 3.

À retenir : Ne pas confondre les questions

Premier : exactement deux diviseurs positifs. Composé : entier \(\ge2\) produit de deux entiers \(>1\). Premiers entre eux : seul diviseur positif commun égal à 1. Impair n’est pas synonyme de premier.

À retenir : Ce que tu vas apprendre

Prouver qu’un entier est premier en utilisant une liste finie et complète de divisions ; repérer les cas où un seul facteur suffit à conclure.

Rappel utile : Le kit de cette unité

Un entier \(n\ge2\) est premier si ses seuls diviseurs positifs sont 1 et \(n\). Il est composé s’il s’écrit \(n=ab\) avec \(a,b\ge2\). La division euclidienne de \(n\) par \(d>0\) est \(n=dq+r\) avec \(q\in\mathbb{Z}\) et \(0\le r<d\). Le diviseur \(d\) divise \(n\) exactement quand \(r=0\).

Pour \(n\ge0\), \(\sqrt n\) est le nombre positif ou nul dont le carré est \(n\). Comparer les carrés de deux nombres positifs permet de comparer ces nombres.

Avant de commencer : Ce qui suffit, ce qui ne suffit pas

\(91=7\times13\) : peut-on conclure ? Et si l’on sait seulement que 101 n’est divisible ni par 2 ni par 5 ?

Correction.

91 est composé, car ses deux facteurs sont \(>1\). Les deux échecs pour 101 ne suffisent pas : il faut borner la recherche et examiner tous les premiers nécessaires. Si ce contraste n’est pas clair, relis les définitions du rappel avant la preuve suivante.

Lemme : Un diviseur premier pour tout entier au moins égal à 2

Tout entier \(n\ge2\) possède au moins un diviseur premier. Plus précisément, son plus petit diviseur strictement supérieur à 1 est premier.

Démonstration : Choisir le plus petit

L’ensemble des diviseurs de \(n\) strictement supérieurs à 1 n’est pas vide, puisqu’il contient \(n\) ; il possède donc un plus petit élément \(d\). Si \(d\) était composé, on aurait \(d=uv\) avec \(1<u<d\) et \(v>1\). Comme \(d\mid n\), on peut écrire \(n=dk\) ; alors \(n=(uv)k=u(vk)\), donc \(u\mid n\). Cela contredit le choix de \(d\) comme plus petit diviseur \(>1\). Ainsi \(d\) est premier.

On utilise ici le principe élémentaire : une partie non vide de \(\mathbb{N}\) possède un plus petit élément, résultat antérieur sur les entiers.

Théorème : La borne de la racine carrée

Si un entier \(n\ge2\) est composé, alors il possède un diviseur premier \(p\) tel que \(2\le p\le\sqrt n\).

Démonstration : Un des deux facteurs ne peut pas être trop grand

Écrivons \(n=ab\) avec \(2\le a\le b\). Alors \(a^2\le ab=n\), donc \(a\le\sqrt n\). D’après le lemme, \(a\) possède un diviseur premier \(p\). Comme \(p\mid a\) et \(a\mid n\), \(p\mid n\) ; de plus \(2\le p\le a\le\sqrt n\). Le diviseur annoncé existe.

L’égalité peut se produire, par exemple pour \(n=49=7^2\).

Critère : Un test qui permet de conclure

Pour un entier \(n\ge2\), si aucun nombre premier inférieur ou égal à \(\sqrt n\) ne divise \(n\), alors \(n\) est premier.

Démonstration : La contraposée

Supposons les divisions toutes non exactes. Si \(n\) n’était pas premier, il serait composé ; le théorème fournirait un diviseur premier au plus égal à \(\sqrt n\), en contradiction avec les tests. Donc \(n\) est premier. Il ne s’agit pas de la réciproque de « premier implique impair », mais de la contraposée du théorème de la borne.

Méthode : Tester les bons diviseurs

Indices :

on te donne un entier isolé et aucun facteur n’est visible.

Conditions :

\(n\) est entier, \(n\ge2\).

Premier geste :

encadrer \(\sqrt n\) par deux entiers, en comparant leurs carrés.

1. Écrire tous les nombres premiers \(p\) tels que \(p^2\le n\), c’est-à-dire \(p\le\sqrt n\) exactement. L’entier supérieur utilisé pour encadrer \(\sqrt n\) ne devient pas lui-même une nouvelle borne de test. Pour \(n=2\) ou \(n=3\), cette liste est vide : ces deux entiers sont premiers.

2. Diviser par chacun, dans l’ordre croissant. Dès qu’un reste est nul, donner le produit trouvé et conclure « composé ».

3. Si tous les restes sont non nuls, citer le critère et conclure « premier ».

Contrôle :

vérifier \(n=dq+r\) et \(0\le r<d\) pour chaque ligne. Une valeur décimale affichée par la calculatrice est moins sûre qu’une égalité entière.

Exemple expliqué : Certifier que 173 est premier

On cherche une preuve, pas seulement plusieurs divisions qui échouent. Puisque \(13^2=169<173<196=14^2\), on a \(13<\sqrt{173}<14\). Si 173 était composé, il aurait donc un diviseur premier parmi \(2,3,5,7,11,13\). Voici toutes les divisions nécessaires :

Exemple expliqué : S’arrêter dès qu’un diviseur est trouvé

Pour 221, on a \(14^2=196<221<225=15^2\) : les premiers possibles sont \(2,3,5,7,11,13\). Les premiers tests ne donnent aucun reste nul : \(221=2\times110+1=3\times73+2=5\times44+1\) et \(221=7\times31+4=11\times20+1\).

Mais \(221=13\times17\) : 221 est composé. Il est inutile de poursuivre. Les cinq premiers échecs n’avaient pas autorisé à conclure qu’il était premier.

Rappel utile : Des tests de divisibilité qui accélèrent les premiers essais

Un entier est divisible par 2 si son chiffre des unités est pair, par 5 si ce chiffre vaut 0 ou 5 ; par 3 ou par 9 si la somme de ses chiffres est divisible respectivement par 3 ou par 9.

Justification :

écrire \(n=10a+b\) montre que \(n-b=10a\) est divisible par 2 et par 5. Pour 3 et 9, \(10^k-1\) est divisible par 9 pour \(k\ge1\), car \(10^k-1=9(1+10+\cdots+10^{k-1})\). En écrivant le nombre chiffre par chiffre, la différence entre le nombre et la somme des chiffres est donc divisible par 9, puis par 3.

Ainsi les deux nombres ont la même divisibilité par chacun de ces modules.

Pour 173, la somme \(1+7+3=11\) exclut la divisibilité par 3 ; elle ne prouve pas la primalité, car les autres diviseurs restent à examiner.

Bon réflexe : Tester seulement les nombres premiers

Tester 4 après avoir exclu 2 est inutile : si \(4\mid n\), alors \(2\mid n\). Plus généralement, tout diviseur composé a un facteur premier. L’astuce réduit donc le nombre de divisions sans perdre de cas.

Limite :

la liste utilisée doit être complète. Oublier 11 entre 7 et 13 n’est pas une optimisation, mais une lacune dans la preuve.

À toi : Essai guidé puis tentative sans modèle

Guidé.

97 est-il premier ? Encadre \(\sqrt{97}\) entre deux entiers consécutifs, écris la liste des nombres premiers à essayer, puis toutes les divisions utiles.

À chercher avant de lire la correction.

Décide pour chacun des nombres 121 et 131. Explique pourquoi la division par 11 ne joue pas le même rôle dans les deux cas.

Justifie avec tes mots.

Pourquoi l’arrêt doit-il avoir lieu après tous les nombres premiers inférieurs ou égaux à la racine, et non strictement inférieurs ? Une réponse attendue doit citer un carré de nombre premier et identifier son diviseur oublié.

Indices progressifs : À consulter seulement si nécessaire

1. \(9^2=81\), \(10^2=100\), \(11^2=121\), \(12^2=144\). 2. Pour 97, seuls \(2,3,5,7\) sont à tester. 3. Pour 121, examine précisément le diviseur égal à la racine.

Correction expliquée : Essai guidé et tentative

Comme \(81<97<100\), \(9<\sqrt{97}<10\). \(97=2\times48+1=3\times32+1=5\times19+2=7\times13+6\). Les quatre restes sont non nuls : 97 est premier.

Pour 121, \(121=11\times11\) : il est composé. Ici \(11=\sqrt{121}\), donc remplacer « inférieur ou égal » par « strictement inférieur » aurait laissé échapper le seul diviseur premier utile.

Enfin \(121<131<144\) : on doit tester \(2,3,5,7,11\).

Si tu t’es trompé : Si tu as arrêté trop tôt

Erreur repérée :

« 49 n’est divisible ni par 2, ni par 3, ni par 5, donc il est premier. »

Rappel :

on inclut la borne.

Exemple plus simple :

\(25=5^2\) ; tester seulement 2 et 3 manque le facteur 5.

Nouvel essai :

décide pour 49 en reprenant la liste complète.

Correction :

\(\sqrt{49}=7\) et \(49=7\times7\) ; 49 est composé.

Retour :

refais maintenant 121, puis retrouve dans ta première liste l’endroit exact où 11 avait été oublié.

Pour réparer une erreur : Demain, avant de relire

Décide si 149 est premier.

Aide minimale :

\(12^2=144<149<169=13^2\).

Critères :

liste complète, restes exacts, recours explicite au critère.

Correction à masquer pendant la recherche :

les diviseurs premiers possibles sont \(2,3,5,7,11\) et \(149=2\times74+1=3\times49+2=5\times29+4 =7\times21+2=11\times13+6\). Aucun reste n’est nul ; 149 est premier.

À retenir : Deux types de certificat

Pour prouver « composé », un produit de deux entiers \(>1\) suffit. Pour prouver « premier » par divisions, toutes les divisions par les premiers \(p\le\sqrt n\) doivent échouer. La borne est inclusive.

À retenir : Ce que tu vas apprendre

Comprendre un programme de primalité, décrire ses états, construire tous les nombres premiers jusqu’à une borne et justifier pourquoi le crible s’arrête.

Rappel utile : Ce qu’utilisent les deux algorithmes

Un entier \(n\ge2\) est composé s’il possède un facteur entre 2 et \(\sqrt n\) ; il suffit de chercher les facteurs premiers, mais essayer tous les entiers dans cet intervalle fonctionne aussi.

En Python, n % d est le reste de la division entière par d, n // d son quotient entier. Le test == compare deux valeurs ; = affecte une valeur à une variable. True et False signifient vrai et faux.

Avant de commencer : Lire avant d’exécuter

Que valent 29 % 5 et 29 // 5 ? Si une boucle teste d*d < n, détecte-t-elle toujours un carré de premier ?

Correction.

\(29=5\times5+4\) donne 4 et 5. Pour \(n=49\), le test strict s’arrêterait avant \(d=7\) : il faut d*d <= n. Le rappel ci-dessus donne le sens des opérateurs ; le cas limite explique le signe d’inégalité.

Algorithme : Un test exact, simple à justifier

Entrée :

un entier n.

Sortie :

vrai exactement lorsque n est premier. Le programme refuse d’abord les valeurs inférieures à 2.

def est_premier(n):
    if n < 2:
        return False
    d = 2
    while d*d <= n:
        if n % d == 0:
            return False
        d = d + 1
    return True

Démonstration : Terminaison et exactitude

À l’entrée de la boucle, aucun entier de 2 à \(d-1\) ne divise \(n\) : c’est vrai au début, car il n’y a aucun entier entre 2 et 1. Si \(d\) divise \(n\), le programme renvoie faux avec un véritable diviseur \(2\le d\le\sqrt n<n\) (pour \(n\ge2\)). Sinon, augmenter \(d\) de 1 conserve l’affirmation pour la prochaine entrée de boucle.

Comme \(d\) augmente, il finit par vérifier \(d^2>n\) ; la boucle termine. Si l’on arrive au dernier return True, aucun entier compris entre 2 et \(\sqrt n\) ne divise \(n\) : le critère de primalité s’applique.

Exemple expliqué : La trace pour 29 puis pour 25

Pour 29, d prend 2, 3, 4, 5 ; les restes valent respectivement 1, 2, 1, 4, puisque \(29=2\times14+1=3\times9+2=4\times7+1=5\times5+4\). Après le dernier échec, d devient 6 et \(36>29\) : la sortie est vrai.

Pour 25, les restes pour 2, 3, 4 valent 1, 1, 1, puis celui pour 5 vaut 0. La sortie est faux avant l’incrément suivant. Le programme teste parfois un diviseur inutile, comme 4 ; c’est moins rapide, mais pas incorrect.

Méthode : Le crible d’Ératosthène

But :

chercher tous les premiers inférieurs ou égaux à un entier \(N\ge2\).

Premier geste :

écrire les entiers de 2 à \(N\) ; 1 n’est pas dans la liste.

1. Garder le plus petit nombre non rayé \(p\).

2. Rayer ses multiples à partir de \(p^2\), sans rayer \(p\) lui-même.

3. Recommencer avec le nombre non rayé suivant, tant que \(p^2\le N\).

À la fin, les nombres non rayés sont exactement les nombres premiers.

Démonstration : Pourquoi commencer à \(p^2\) ? Pourquoi s’arrêter ?

Un multiple \(kp\) avec \(2\le k<p\) a un diviseur premier au plus égal à \(k\), donc strictement inférieur à \(p\) : il a déjà été rayé lors d’un passage précédent. Le premier multiple pouvant rester est donc \(p^2\).

Un nombre premier n’est jamais rayé, car on ne raye que des produits de deux entiers \(\ge2\).

Réciproquement, tout composé \(m\le N\) a un diviseur premier \(p\le\sqrt m\le\sqrt N\). Il est rayé au passage de ce premier (ou avant). Lorsque le prochain \(p\) vérifie \(p^2>N\), tous les composés ont donc été éliminés. Le crible garde tous les premiers et seulement eux.

Exemple expliqué : Un crible jusqu’à 50

Au passage de 2, on élimine \(4,6,8,\ldots,50\). Au passage de 3, on commence à 9 : les nouveaux nombres rayés sont \(9,15,21,27,33,39,45\) ; les multiples pairs étaient déjà rayés. Au passage de 5, les nouveaux sont 25 et 35. Au passage de 7, on raye encore 49. Le prochain premier est 11 et \(11^2=121>50\) : arrêt.

Les survivants sont

Contrôle :

49 doit avoir disparu ; oublier le passage de 7 aurait laissé un composé. Les petits premiers 2, 3, 5 et 7 doivent être restés.

Algorithme : Une version avec tableau de booléens

garde[k] indique si l’entier \(k\) reste candidat. Les cases 0 et 1 sont mises à faux. range(a,b,c) énumère \(a,a+c,\ldots\) sans atteindre \(b\).

def crible(N):
    if N < 2:
        return []
    garde = [True] * (N + 1)
    garde[0] = False
    garde[1] = False
    p = 2
    while p*p <= N:
        if garde[p]:
            for m in range(p*p, N + 1, p):
                garde[m] = False
        p = p + 1
    return [k for k in range(2, N + 1) if garde[k]]

La preuve du crible précédent justifie les cases finales.

À toi : Exécuter, expliquer, corriger

Guidé.

Fais le crible jusqu’à 30. Note seulement les nombres nouvellement rayés au passage de 3 puis de 5.

Tentative.

Fais la trace du test est_premier pour 35. Combien de divisions sont effectuées ?

Justifie.

Pourquoi faut-il commencer les rayures à \(p^2\) et non à \(p\) ? Cite le nombre qui serait perdu.

Variation.

Un programme commence par renvoyer vrai pour tous les nombres inférieurs à 2, puis utilise la bonne boucle. Est-il correct ?

Indices progressifs : Voir l’état avant de modifier une case

Les multiples pairs sont déjà rayés avant le passage de 3.

Pour 35, examine \(d=2,3,4,5\). Une sortie return termine immédiatement la fonction.

Correction expliquée : Trace et diagnostic

Jusqu’à 30, les nouveaux multiples rayés de 3 sont \(9,15,21,27\) ; au passage de 5, il ne reste que 25 à rayer. Les premiers obtenus sont \(2,3,5,7,11,13,17,19,23,29\).

Pour 35, les divisions sont \(35=2\times17+1=3\times11+2=4\times8+3=5\times7\). La quatrième division a un reste nul : sortie faux, sans essayer 6. Rayer à partir de \(p\) supprimerait le nombre premier \(p\) lui-même, par exemple 3 au passage de 3. Les multiples de \(p\) à éliminer ont au moins deux facteurs \(>1\) ; \(p=1\times p\) ne convient pas.

Le dernier programme est faux pour 0 et 1 (et pour les entiers négatifs). Une boucle correcte ne répare pas une initialisation incorrecte.

Si tu t’es trompé : Si une mise à jour te semble mystérieuse

Erreur :

« Au passage de 3, je dois encore garder 9 puisqu’il était vrai. »

Rappel :

vrai signifie seulement pas encore éliminé.

Exemple simple :

avant le passage de 2, la case 4 est vraie ; l’instruction garde[4] = False la change parce que \(4=2\times2\).

Nouvel essai :

que devient la case 9 au passage de 3 ?

Correction :

\(9=3\times3\) ; elle passe de vrai à faux et ne redeviendra jamais vraie.

Retour :

refais le passage de 3 jusqu’à 30, en séparant cases déjà fausses et cases qui changent.

Pour réparer une erreur : Plus tard, tester le cas limite

Trouve les premiers jusqu’à 10 et explique le comportement pour \(N=1\).

Aide :

une liste peut être vide ; le crible ne doit jamais lire une case inexistante.

Correction :

pour 10, 2 raye 4, 6, 8, 10 ; 3 raye 9 ; la sortie est \([2,3,5,7]\). Pour 1, la première condition renvoie la liste vide avant la création des cases.

Critères :

sortie exacte, ordre des opérations et explication de l’arrêt.

À retenir : Ce qu’un programme doit rendre vérifiable

Entrées, état initial, test de boucle, mises à jour, arrêt et sens de la sortie. Tester quelques entrées contrôle le code ; la justification des invariants explique pourquoi il fonctionne pour toutes les entrées prévues.

À retenir : Ce que tu vas apprendre

Comprendre la démonstration d’Euclide, identifier précisément sa contradiction et distinguer un nouveau nombre d’un nouveau diviseur premier.

Rappel utile : Les deux outils de la preuve

Tout entier \(N\ge2\) a un diviseur premier : son plus petit diviseur \(>1\) est premier, car un facteur plus petit contredirait ce choix. Si \(d\mid A\) et \(d\mid B\), alors \(d\mid(A-B)\) : en écrivant \(A=du\) et \(B=dv\), on obtient \(A-B=d(u-v)\).

Enfin, dire qu’un ensemble est fini signifie que ses éléments peuvent être écrits dans une liste complète de longueur finie.

Avant de commencer : Ce que le calcul n’établit pas

Une machine a trouvé un million de nombres premiers. Cela prouve-t-il qu’il en existe une infinité ? Si un entier \(N>1\) est composé, a-t-il quand même un diviseur premier ?

Correction.

Un million reste un nombre fini : la première réponse est non. La seconde est oui, par le lemme du rappel. Ces deux idées sont exactement celles dont la démonstration a besoin.

Théorème : Infinité des nombres premiers

L’ensemble des nombres premiers est infini. Il n’existe donc pas de plus grand nombre premier.

Démonstration : Un diviseur premier qui manque à la liste

Supposons, pour obtenir une contradiction, qu’il n’y ait qu’un nombre fini de nombres premiers. Écrivons alors leur liste complète \(p_1,p_2,\ldots,p_r\) et posons

Mais il divise aussi \(N\). Il divise alors leur différence : \(N-P=(P+1)-P=1\). Un entier \(q\ge2\) ne peut pas diviser 1. C’est la contradiction recherchée : la liste complète finie n’existe pas. L’ensemble des nombres premiers est donc infini.

Le nombre \(N\) lui-même n’a jamais été supposé premier. C’est l’existence de son diviseur premier \(q\) qui fait fonctionner la preuve.

Remarque : Lire le raisonnement par l’absurde

L’hypothèse provisoire est « tous les premiers tiennent dans la liste ». La contradiction n’est pas « le nouveau nombre est grand » : une liste de nombres peut avoir un maximum sans contradiction. Elle est l’existence d’un entier premier \(q\ge2\) qui diviserait 1.

On rejette donc l’hypothèse provisoire, et non les propriétés de divisibilité. La preuve n’a pas besoin de connaître à l’avance la valeur de \(q\).

Exemple expliqué : Une liste incomplète mise en défaut

Partons de \(2,3,5,7\). Leur produit vaut \(2\times3\times5\times7=6\times35=210\). Le nombre construit est \(211\). Il laisse le reste 1 quand on le divise par 2, 3, 5 ou 7. Ici 211 est lui-même premier : \(14^2<211<15^2\) et il reste à tester 11 et 13 ; \(211=11\times19+2=13\times16+3\).

La liste initiale manque donc au moins 211. Mais cette situation particulière ne permet pas de généraliser que le nombre construit sera toujours premier.

Piège à éviter : Ajouter 1 ne fabrique pas toujours un premier

Méthode : Rédiger une preuve d’infinité à partir d’une liste

Indice :

on veut montrer qu’aucune liste finie ne peut être complète.

Premier geste :

supposer une liste complète puis construire un entier dont les divisions par ses éléments auront un reste imposé. Ici, « produit \(+1\) » impose le reste 1. Il faut ensuite passer par un diviseur premier du nombre construit, puis expliquer pourquoi il ne peut appartenir à la liste.

Contrôle :

cherche dans ta rédaction la phrase qui garantit l’existence de ce diviseur et celle qui rend la contradiction impossible.

Notation : Factorielle

Pour un entier \(m\ge1\), \(m!=1\times2\times\cdots\times m\). Par convention \(0!=1\). Par exemple \(4!=1\times2\times3\times4=24\). Le point d’exclamation fait partie de la notation, ce n’est pas une puissance.

Corollaire : Un premier plus grand qu’un entier donné

Pour tout entier \(m\ge1\), il existe un nombre premier strictement supérieur à \(m\).

Démonstration : Une construction explicite qui prolonge la preuve

L’entier \(m!+1\) est au moins égal à 2. Soit \(q\) l’un de ses diviseurs premiers. Si \(q\le m\), il apparaît parmi les facteurs de \(m!\), donc il divise \(m!\). Il diviserait alors \((m!+1)-m!=1\), ce qui est impossible.

On a donc \(q>m\). Le corollaire découle aussi de l’infinité : il n’y a qu’un nombre fini d’entiers au plus égaux à \(m\).

Exemple expliqué : Au-delà de 5

\(5!+1=120+1=121=11^2\). Le nombre construit n’est pas premier, mais son diviseur premier 11 est bien strictement supérieur à 5. Cette variante n’affirme ni que \(m!+1\) est premier, ni qu’on obtient le premier nombre premier après \(m\) : après 5, il y a déjà 7.

À toi : Reconstituer la logique

Guidé.

À partir de la liste \(2,3,5\), calcule le produit \(+1\). Explique pourquoi aucun nombre de la liste ne le divise.

Tentative.

Avec \(m=6\), calcule \(m!+1\) et vérifie qu’il est divisible par 7. Que garantit la construction sur tous ses diviseurs premiers ?

Justification personnelle.

Dans la preuve d’Euclide, pourquoi est-il indispensable de dire que la liste est complète ?

Variation.

Peut-on remplacer le produit \(+1\) par le produit lui-même ?

Indices progressifs : Retrouver la contradiction

Pour un élément \(p\) de la liste, le produit est un multiple de \(p\).

Pour \(6!+1\), calcule \(7\times103\). Une différence égale à 0 ne produit pas la même contradiction qu’une différence égale à 1.

Correction expliquée : Les quantificateurs comptent

\(2\times3\times5+1=31\). \(31=2\times15+1=3\times10+1=5\times6+1\) : aucun ne le divise.

Pour \(m=6\), \(6!=720\), donc \(6!+1=721=7\times103\). Chaque diviseur premier est strictement supérieur à 6 : un premier \(\le6\) diviserait 720 et 721, donc 1.

La liste complète est nécessaire pour affirmer que le diviseur premier \(q\) appartient à la liste ; sans cette hypothèse, le trouver absent ne donne qu’une liste incomplète, pas une contradiction générale.

La réponse personnelle doit mentionner ce passage précis.

Enfin le produit seul est divisible par tous les éléments de la liste : on ne fabrique plus de reste 1, donc la preuve ne fonctionne pas.

Si tu t’es trompé : Si tu as écrit « donc le nouveau nombre est premier »

Rappel :

un nombre peut n’avoir aucun facteur dans une petite liste tout en étant composé.

Exemple simple corrigé :

\(25=5\times5\) n’est divisible ni par 2 ni par 3, mais n’est pas premier.

Nouvel essai :

quel rôle joue 11 dans \(5!+1=121\) ?

Correction :

11 est un diviseur premier de 121, absent de la liste des premiers \(\le5\) ; 121 n’est pas le nouveau premier.

Retour :

remplace dans ta preuve « \(N\) est premier » par « \(N\ge2\) possède un diviseur premier \(q\) », puis vérifie toutes les phrases qui suivent.

Pour réparer une erreur : Après quelques jours

Prouve sans calculer \(20!\) qu’il existe un nombre premier plus grand que 20.

Aide :

construis \(20!+1\), puis choisis un diviseur premier.

Correction :

ce nombre est \(>1\), donc a un diviseur premier \(q\). Si \(q\le20\), \(q\mid20!\) et \(q\mid(20!+1)\), donc \(q\mid1\), impossible. Ainsi \(q>20\).

Critères :

existence de \(q\), hypothèse contraire, différence 1, conclusion ; aucune valeur explicite de \(q\) n’est nécessaire.

À retenir : L’idée essentielle

Une liste finie de premiers ne peut contenir tous les diviseurs premiers de son produit augmenté de 1. L’infinité est prouvée par un raisonnement, pas par une liste de plus en plus longue.

À retenir : Ce que tu vas apprendre

Justifier le rôle particulier des nombres premiers dans un produit, comprendre les dépendances Bézout–Gauss–Euclide et éviter les divisions illégales dans une congruence.

Rappel utile : Le kit de divisibilité

\(d\mid a\) signifie \(a=dk\) avec \(k\in\mathbb{Z}\). Si \(d\) divise deux entiers, il divise chacune de leurs combinaisons à coefficients entiers : de \(a=du\), \(b=dv\), on tire \(ra+sb=d(ru+sv)\) pour \(r,s\in\mathbb{Z}\). Le PGCD de deux entiers non tous deux nuls est leur plus grand diviseur positif commun. Ils sont premiers entre eux si ce PGCD vaut 1.

Pour \(m\ge1\), \(x\equiv y\;[m]\) signifie \(m\mid(x-y)\).

Avant de commencer : Une implication à examiner

De \(6\mid ab\), peut-on toujours déduire \(6\mid a\) ou \(6\mid b\) ? Et quels peuvent être les diviseurs positifs communs de 13 et de \(a\) ?

Correction.

Non : \(6\mid2\times3\) mais 6 ne divise ni 2 ni 3. Comme 13 est premier, les seuls diviseurs communs possibles sont 1 et 13. Le problème n’est donc pas seulement la taille du diviseur, mais sa primalité.

Théorème : Identité de Bézout, rappel démontré

Si \(a,b\in\mathbb{Z}\) ne sont pas tous deux nuls et \(d=\operatorname{PGCD}(a,b)\), il existe \(u,v\in\mathbb{Z}\) tels que \(au+bv=d\). En particulier, \(a\) et \(b\) sont premiers entre eux si et seulement s’il existe \(u,v\in\mathbb{Z}\) tels que \(au+bv=1\).

Démonstration : La plus petite combinaison positive

L’ensemble des entiers strictement positifs de la forme \(ax+by\) n’est pas vide : si \(a\ne0\), on peut obtenir \(|a|\) en choisissant \(x=1\) ou \(-1\) et \(y=0\) ; sinon, on obtient \(|b|\). Soit \(c=au+bv\) son plus petit élément.

Divisons \(a\) par \(c\) : \(a=cq+r\), avec \(0\le r<c\). Alors

Tout diviseur commun positif \(h\) de \(a,b\) divise aussi \(c=au+bv\) ; il vérifie donc \(h\le c\). Ainsi \(c\) est le PGCD, ce qui prouve l’identité. Si le PGCD vaut 1, l’identité donne la combinaison annoncée.

Réciproquement, si \(au+bv=1\), tout diviseur commun positif divise 1, donc vaut 1 : le PGCD est 1. Les deux sens sont établis.

Théorème : Gauss, rappel démontré

Si \(a,b,c\in\mathbb{Z}\), \(a\) et \(b\) sont premiers entre eux et \(a\mid bc\), alors \(a\mid c\).

Démonstration : Transformer le produit en combinaison

Bézout fournit \(u,v\in\mathbb{Z}\) tels que \(au+bv=1\). On multiplie les deux membres par \(c\) : \(auc+bvc=c\). Le premier terme est divisible par \(a\) ; le second aussi car \(a\mid bc\). Leur somme \(c\) est donc divisible par \(a\).

Cette preuve ne suppose pas déjà la décomposition en facteurs premiers.

Exemple expliqué : La coprimalité n’est pas décorative

Si \(13\mid20b\), alors \(13\mid b\), car \(2\times20-3\times13=40-39=1\) prouve que 13 et 20 sont premiers entre eux. En multipliant cette identité par \(b\), on lit \(b=2(20b)-3(13b)\) : les deux termes à droite sont des multiples de 13.

Avec \(6\mid2b\), la même conclusion sur 6 serait fausse : pour \(b=3\), \(2b=6\) est divisible par 6 mais \(b=3\) ne l’est pas.

Lemme : Lemme d’Euclide

Soit \(p\) un nombre premier et \(a,b\in\mathbb{Z}\). Si \(p\mid ab\), alors \(p\mid a\) ou \(p\mid b\). Le « ou » est inclusif : les deux divisibilités peuvent être vraies.

Démonstration : Deux cas, sans division illicite

Si \(p\mid a\), la conclusion est déjà vraie. Sinon, les seuls diviseurs positifs de \(p\) sont 1 et \(p\), et le second ne divise pas \(a\). Donc \(p\) et \(a\) sont premiers entre eux. Le théorème de Gauss appliqué à \(p\mid ab\) donne alors \(p\mid b\).

Les deux cas couvrent tous les entiers \(a\), y compris \(a=0\) dans le premier cas.

Corollaire : Plusieurs facteurs ; une puissance

Si un premier \(p\) divise \(a_1\cdots a_r\), avec \(r\ge1\), il divise au moins l’un des \(a_i\). En particulier, pour \(k\ge1\),

Démonstration : Répéter le lemme, puis vérifier la réciproque

Pour un facteur, c’est immédiat. Pour plusieurs facteurs, on écrit le produit comme \(a_1(a_2\cdots a_r)\). Le lemme donne \(p\mid a_1\) ou \(p\mid(a_2\cdots a_r)\) ; dans le second cas, on recommence. Après un nombre fini d’étapes, un facteur est trouvé. Pour \(a^k\), tous les facteurs sont égaux à \(a\), d’où le sens direct. Réciproquement, si \(a=pt\), alors \(a^k=p(p^{k-1}t^k)\), donc \(p\mid a^k\).

Piège à éviter : Le diviseur doit être premier et l’exposant positif

\(4\mid2^2\), mais \(4\nmid2\) : le corollaire ne s’applique pas à un diviseur composé. Pour \(k=0\), \(a^0=1\) lorsque \(a\ne0\), et aucun premier ne divise 1 : ce n’est pas le domaine de l’énoncé.

Caractérisation : Une propriété qui reconnaît les premiers

Un entier \(n\ge2\) est premier si et seulement si, pour tous \(a,b\in\mathbb{Z}\), \(n\mid ab\) entraîne \(n\mid a\) ou \(n\mid b\).

Démonstration : Ne pas oublier le sens réciproque

Le sens direct est le lemme d’Euclide. Si \(n\) est composé, \(n=ab\) avec \(1<a<n\) et \(1<b<n\). Alors \(n\mid ab\), mais \(n\) ne divise ni \(a\) ni \(b\), car ce sont des entiers positifs strictement plus petits que \(n\). La propriété annoncée est donc fausse. Par contraposée, si elle est vraie pour tous \(a,b\), \(n\) est premier.

Propriété : Annulation modulo un premier

Si \(p\) est premier, \(p\nmid a\) et \(ax\equiv ay\;[p]\), alors \(x\equiv y\;[p]\).

Démonstration : Revenir à la divisibilité

La congruence signifie \(p\mid(ax-ay)\), c’est-à-dire \(p\mid a(x-y)\). Le lemme d’Euclide donne \(p\mid a\) ou \(p\mid(x-y)\). Le premier cas est exclu par hypothèse. Il reste \(p\mid(x-y)\), donc \(x\equiv y\;[p]\).

Exemple expliqué : Un bon et un mauvais raccourci

De \(3x\equiv3y\;[7]\), on peut déduire \(x\equiv y\;[7]\), car 7 est premier et ne divise pas 3. En revanche, \(14\times1\equiv14\times2\;[7]\) puisque les deux produits sont multiples de 7 ; pourtant \(1\not\equiv2\;[7]\).

Le facteur 14 est non nul, mais divisible par le module : sa non-nullité dans \(\mathbb{Z}\) ne suffit pas à l’annuler dans une congruence.

Méthode : Reconnaître quand Euclide ou Gauss s’applique

Premier geste :

nommer le diviseur et vérifier s’il est premier. S’il est premier, le lemme sépare les facteurs. Pour exclure un facteur, vérifie qu’il n’est pas divisible par ce premier. S’il n’est pas premier, cherche une condition de coprimalité et applique Gauss, ou construis un contre-exemple ; ne supprime pas la condition.

Contrôle :

réécris la phrase obtenue sous forme d’une égalité avec un entier multiplicateur pour vérifier ce que tu as réellement prouvé.

À toi : Utiliser les hypothèses

Guidé.

Si \(7\mid10x\), montrer que \(7\mid x\).

Tentative.

Si \(11\mid n(n+2)\), quelles sont les classes possibles de \(n\) modulo 11 ? Les deux possibilités sont-elles toutes réalisables ?

Justifie.

De \(5\mid a^3\), pourquoi déduit-on \(5\mid a\) ? Écris le produit avant d’utiliser le lemme.

Variation.

Remplace 5 par 8 dans cette dernière affirmation et teste \(a=2\).

Indices progressifs : Un produit et un diviseur

7 ne divise pas 10. Le nombre 11 est premier. La condition \(11\mid n+2\) équivaut à \(n\equiv-2\equiv9\;[11]\).

Correction expliquée : Toutes les possibilités, puis le contrôle

7 est premier. De \(7\mid10x\), Euclide donne \(7\mid10\) ou \(7\mid x\). Or \(10=7+3\), donc le premier cas est impossible ; \(7\mid x\). De même, \(11\mid n(n+2)\) entraîne \(11\mid n\) ou \(11\mid(n+2)\), donc \(n\equiv0\) ou \(n\equiv9\;[11]\).

Réciproquement, chacun de ces cas rend un facteur divisible par 11, donc rend le produit divisible : les deux classes sont exactement les solutions.

Pour \(a^3=a\times a\times a\), le corollaire d’Euclide oblige 5 à diviser l’un des trois facteurs, tous égaux à \(a\). Avec 8, \(2^3=8\) est divisible par 8 mais 2 ne l’est pas. La primalité est bien une hypothèse indispensable. Une justification complète doit la citer.

Si tu t’es trompé : Si tu as annulé un facteur sans vérifier

Erreur :

« \(6\mid2b\), donc \(6\mid b\). »

Rappel :

il manque la coprimalité de 6 et 2.

Exemple simple corrigé :

\(3\mid2b\) implique \(3\mid b\), car 3 est premier et \(3\nmid2\).

Nouvel essai :

de \(5\mid15b\), peut-on déduire \(5\mid b\) ?

Correction :

non ; \(b=1\) donne un produit divisible par 5, mais \(1\) ne l’est pas.

Retour :

écris maintenant l’hypothèse exacte qui autorisait le raisonnement pour \(7\mid10x\).

Pour réparer une erreur : Demain, une équation de restes

Si \(13\mid n^2\), démontrer que \(13\mid n\). Puis étudier \(13\mid n(n-1)\).

Aide :

séparer les facteurs.

Correction :

\(n^2=n\times n\) ; Euclide donne \(13\mid n\) dans les deux cas.

Pour \(n(n-1)\), il donne \(n\equiv0\) ou \(n\equiv1\;[13]\) ; les réciproques se vérifient par le facteur divisible.

Critères :

nommer la primalité de 13, conserver le « ou », vérifier les deux classes.

À retenir : La chaîne logique

Bézout permet Gauss ; Gauss permet le lemme d’Euclide ; le lemme explique les facteurs premiers d’un produit et les simplifications modulo un premier. Le diviseur premier n’est jamais une condition décorative.

À retenir : Ce que tu vas apprendre

Construire une décomposition en facteurs premiers, distinguer existence et unicité, et comprendre un algorithme qui n’oublie aucun facteur.

Rappel utile : Des outils locaux pour les preuves

Un entier \(n\ge2\) est premier ou s’écrit \(n=ab\) avec \(2\le a,b<n\). Toute partie non vide de \(\mathbb{N}\) a un plus petit élément. Le lemme d’Euclide dit : si un premier divise un produit entier, il divise l’un des facteurs ; répété, il vaut pour une liste finie de facteurs.

Il découle de Gauss : un premier \(p\) qui ne divise pas \(a\) est premier avec \(a\), donc \(p\mid ab\) entraîne \(p\mid b\). Les règles de puissances sont \(a^u a^v=a^{u+v}\) et \((a^u)^v=a^{uv}\) pour les exposants naturels utilisés ici. Ainsi \(2^3\) est \(2\times2\times2\), pas \(2\times3\).

Avant de commencer : Est-ce terminé ?

Les écritures \(84=4\times21\) et \(84=2\times2\times3\times7\) sont-elles toutes deux des décompositions en facteurs premiers ?

Correction.

Les deux produits valent 84, mais 4 et 21 sont composés. Seule la seconde écriture n’utilise que des premiers. Un contrôle du produit ne suffit donc pas : il faut aussi contrôler chaque facteur.

Théorème : Décomposition en facteurs premiers

Tout entier \(n\ge2\) est un produit de nombres premiers. Cette décomposition est unique à l’ordre des facteurs près. En regroupant les facteurs égaux, on peut écrire

Les facteurs et leurs exposants sont alors uniques.

Démonstration : Existence : le plus petit contre-exemple n’existe pas

Supposons qu’il existe un entier \(n\ge2\) sans décomposition première, et choisissons le plus petit d’entre eux. Il ne peut pas être premier : un nombre premier constitue déjà un produit d’un seul facteur premier.

Il est donc composé : \(n=ab\), avec \(2\le a,b<n\). Par minimalité de \(n\), \(a\) et \(b\) ont chacun une décomposition première. Multiplier leurs deux listes de facteurs donne une décomposition première de \(ab=n\), contradiction. Tous les entiers \(n\ge2\) possèdent donc une décomposition. C’est une forme de raisonnement par descente, proche de la récurrence forte ; aucune unicité n’a encore été supposée.

Démonstration : Unicité : comparer deux listes de facteurs

Supposons qu’un même entier \(n\ge2\) s’écrive \(n=p_1\cdots p_r=q_1\cdots q_s\), avec tous les facteurs premiers. Comme \(p_1\) divise le produit \(q_1\cdots q_s\), le lemme d’Euclide, répété si nécessaire, montre qu’il divise l’un des facteurs \(q_j\).

Or \(q_j\) est premier : son diviseur \(p_1>1\) ne peut être que \(q_j\). On place ce facteur au début de la deuxième liste en changeant seulement l’ordre des facteurs. Les deux produits contiennent donc le même facteur \(p_1=q_j\), non nul ; on divise l’égalité par ce facteur.

On recommence avec les listes restantes. À chaque étape, leur produit commun est divisé par un nombre au moins égal à 2 et un facteur est retiré de chacune des deux listes. Le processus est fini. Si l’une des listes s’épuisait avant l’autre, on obtiendrait \(1=\) un produit non vide de nombres premiers, donc un nombre au moins égal à 2.

Ce serait impossible. Les listes s’épuisent donc ensemble, avec les mêmes facteurs et les mêmes répétitions. L’unicité est établie à l’ordre près.

Avant de commencer : Ce qu’autorise le mot « plus petit »

Supposons que \(n\) soit le plus petit entier \(\ge2\) sans décomposition première. Si \(2\le a<n\), peut-on affirmer que \(a\) est premier ? Peut-on affirmer qu’il possède une décomposition première ?

Correction.

La première conclusion n’est pas justifiée : être plus petit ne signifie pas être premier. La seconde l’est : sinon \(a\) serait un contre-exemple plus petit que \(n\). Si cette différence te gêne, reprends la preuve d’existence ci-dessus, à la phrase « Par minimalité de \(n\) ».

Exemple expliqué : Des facteurs composés peuvent parfaitement convenir

Dans \(60=6\times10\), ni 6 ni 10 n’est premier. Pourtant \(6=2\times3\) et \(10=2\times5\) donnent \(60=(2\times3)(2\times5)=2^2\times3\times5\). La preuve générale n’exige donc pas que les deux facteurs soient premiers : elle exige qu’ils soient décomposables. La minimalité du contre-exemple garantit précisément cette propriété.

À toi : Reconstruire le raisonnement, puis le rédiger

Guidé.

Complète les trois articulations : « Le contre-exemple minimal \(n\) n’est pas premier, car … ; on écrit donc \(n=ab\) avec \(2\le a,b<n\) ; \(a\) et \(b\) sont décomposables, car … ; leurs décompositions permettent de …  d’où la contradiction. »

Tentative avant correction.

Sans recopier la preuve, rédige maintenant un raisonnement complet à partir de l’hypothèse « Il existe un entier \(\ge2\) qui n’est pas produit de nombres premiers ». Explique pourquoi on peut choisir le plus petit de ces entiers.

Justification personnelle.

Quelle différence y a-t-il entre prouver l’existence d’une décomposition et prouver son unicité ?

Variation.

Si l’on choisit un contre-exemple quelconque, la phrase « \(a\) et \(b\) sont plus petits, donc décomposables » est-elle justifiée ?

Indices progressifs : Deux propriétés des entiers, pas une conjecture

Une partie non vide de \(\mathbb{N}\) possède un plus petit élément. Un premier est déjà un produit d’un seul facteur premier. Si tous les nombres plus petits ont une décomposition, multiplier deux de ces produits donne encore un produit fini de premiers.

Correction expliquée : Les étapes qui ferment la contradiction

Les trois compléments du guidage sont : « un premier est déjà un produit de premiers » ; « ils sont au moins égaux à 2 et strictement plus petits que le contre-exemple minimal » ; « décomposer leur produit \(n\) ».

Pour la tentative : supposons l’ensemble des contre-exemples non vide. Comme c’est une partie de \(\mathbb{N}\), il possède un plus petit élément \(n\). Ce nombre n’est pas premier, sinon il aurait une décomposition à un facteur. Il est composé, donc \(n=ab\) avec \(2\le a,b<n\).

Par minimalité, aucun des deux facteurs n’est un contre-exemple : \(a=p_1\cdots p_r\) et \(b=q_1\cdots q_s\), avec tous ces facteurs premiers. Alors \(n=p_1\cdots p_rq_1\cdots q_s\) possède une décomposition, contrairement à son choix. Il n’existe donc aucun contre-exemple.

L’existence garantit au moins une décomposition ; l’unicité garantit que toutes ont les mêmes facteurs avec les mêmes répétitions. Sans minimalité, rien n’exclut que \(a\) soit un contre-exemple plus petit : la variation laisse un trou dans le raisonnement.

Critères :

choix minimal justifié, cas premier exclu, deux facteurs dans le domaine \([2,n[\), usage précis de la minimalité, produit final et contradiction. L’unicité n’est utilisée à aucune étape.

Si tu t’es trompé : Si tu as remplacé « décomposable » par « premier »

Erreur :

« \(n=ab\) et \(a,b<n\), donc \(a\) et \(b\) sont premiers. »

Rappel :

la minimalité exclut seulement les contre-exemples à la décomposabilité.

Exemple plus simple corrigé :

\(12=3\times4\), avec \(4=2\times2\) ; 4 est composé mais décomposable.

Nouvel essai :

pour \(72=8\times9\), remplace les deux facteurs par des premiers sans affirmer que 8 et 9 sont premiers.

Correction :

\(8=2^3\), \(9=3^2\), donc \(72=2^3\times3^2\).

Retour :

dans ta preuve générale, souligne la propriété exacte obtenue pour \(a\) et \(b\), puis refais la phrase qui décompose \(n\).

Pour réparer une erreur : Dans deux jours, reconstruire plutôt que réciter

Explique pourquoi la démonstration suivante est incomplète, puis répare-la : « Soit \(n\) un entier non décomposable en premiers. Il est composé, donc \(n=ab\). Comme \(a,b<n\), ils sont décomposables, contradiction. »

Aide :

cherche une hypothèse de choix manquante et des bornes nécessaires sur les facteurs.

Correction :

supposer d’abord qu’un contre-exemple \(\ge2\) existe, puis en choisir le plus petit. Un premier ne peut pas être ce contre-exemple ; choisir \(2\le a,b<n\) est alors possible. La minimalité donne les deux décompositions, dont le produit décompose \(n\), contradiction. Les critères sont les mêmes que ci-dessus : la taille seule ne suffit pas, et l’unicité n’intervient pas.

Convention : Le nombre 1 et les exposants nuls

Le théorème ci-dessus porte sur \(n\ge2\). Pour les calculs de diviseurs, on utilise \(p^0=1\) ; un exposant nul signifie que le facteur \(p\) est absent. On peut aussi convenir que le produit d’une liste vide vaut 1.

Le nombre 1 n’a aucun facteur premier. Pour un entier négatif, on écrit son signe \(-\) devant la décomposition de sa valeur absolue.

Représentation intuitive : Une fiche d’identité multiplicative

La liste des premiers et de leurs nombres d’apparitions joue le rôle d’une fiche d’identité pour la multiplication. Par exemple \(72=2^3\times3^2\) contient trois facteurs 2 et deux facteurs 3. Changer leur ordre ne change pas le nombre ; changer une quantité le change.

Limite :

l’image ne décrit pas une décomposition additive : \(72=70+2\) n’est pas une autre fiche de facteurs premiers. L’unicité est un théorème démontré, pas une conséquence de l’image.

Méthode : Divisions successives, méthode conseillée

Indices :

on cherche les diviseurs, un carré, un PGCD ou une fraction irréductible.

Premier geste :

essayer le plus petit premier, 2, puis 3, 5, etc. Tant qu’un premier divise le quotient courant, diviser encore par ce même premier. Quand il ne divise plus, passer au suivant. Continuer jusqu’à 1. Regrouper ensuite les facteurs égaux par des puissances.

Contrôle double :

tous les facteurs sont premiers et leur produit redonne l’entier de départ.

Exemple expliqué : Décomposer 1 260 sans perdre une répétition

Les divisions donnent

Contrôle :

\(2^2\times3^2\times5\times7=4\times9\times35 =36\times35=1260\). Écrire \(2\times3\times5\times7\) oublierait un facteur 2 et un facteur 3.

Méthode : Variante : un arbre ou des produits connus

Si un produit est visible, on peut commencer par lui : \(1260=126\times10=(14\times9)\times(2\times5)\), puis \(14=2\times7\) et \(9=3\times3\). On poursuit chaque branche jusqu’à un facteur premier, et on lit toutes les feuilles, y compris les répétitions.

Cette variante est utile pour un calcul mental rapide ; les divisions successives sont plus systématiques quand aucune factorisation n’est visible. L’unicité garantit le même résultat, pas les mêmes étapes.

Exemple expliqué : Un arbre dont les feuilles sont les facteurs

Description : 180 se sépare en 18 et 10 ; 18 se sépare en 2 et 9, 9 en 3 et 3, et 10 en 2 et 5. Les cinq feuilles donnent \(180=2\times3\times3\times2\times5=2^2\times3^2\times5\). On ne multiplie pas les nœuds intermédiaires 18, 9 ou 10 en plus des feuilles.

Algorithme : Décomposition par divisions entières

Entrée :

un entier \(n\ge2\). La liste renvoyée contient les facteurs premiers avec répétitions, dans l’ordre croissant.

def facteurs_premiers(n):
    if n < 2:
        raise ValueError("n doit etre au moins egal a 2")
    r = n
    d = 2
    L = []
    while d*d <= r:
        while r % d == 0:
            L.append(d)
            r = r // d
        d = d + 1
    if r > 1:
        L.append(r)
    return L

Exemple expliqué : Suivre le reste de la décomposition

Pour décomposer 180, on conserve un entier courant \(r\) et une liste \(L\) des facteurs déjà trouvés. Au départ, \(r=180\) et \(L\) est vide. Au début puis après chaque étape complète (ajout et division), la règle « \(180=(\text{produit des éléments de }L)\times r\) » reste vraie.

Quand le diviseur \(d\) divise \(r\), on ajoute d’abord \(d\) à la liste, puis on remplace \(r\) par le quotient entier \(r/d\) ; on garde le même diviseur pour ne pas oublier un facteur répété. Cette règle n’est pas affirmée entre les deux mises à jour. Quand \(d\) ne divise plus \(r\), on passe au diviseur suivant : ici 45 est impair, donc on passe de 2 à 3.

Après les divisions par 3, la mise à jour \(d=d+1\) donne \(d=4\) et \(r=5\). Le test suivant échoue puisque \(4^2=16>5\) : c’est l’état effectif de sortie. Les diviseurs plus petits ont été épuisés ; en particulier 2 ne divise pas 5. Le critère de la racine carrée montre donc que le reste 5 est premier ; il faut encore l’ajouter.

Ainsi \(L=[2,2,3,3,5]\) et \(180=2^2\times3^2\times5\). Le contrôle \(4\times9\times5=180\) détecterait l’oubli du dernier facteur.

Démonstration : Pourquoi les facteurs sortis sont premiers

À l’entrée d’un passage pour \(d\), aucun entier entre 2 et \(d-1\) ne divise le reste courant \(r\). Si \(d\) divisait \(r\) tout en étant composé, un facteur premier plus petit que \(d\) diviserait \(r\), contradiction.

Tout facteur ajouté dans la boucle est donc premier. Après chaque ajout suivi de sa division, le produit des facteurs de la liste, multiplié par \(r\), reste égal à \(n\). Les divisions par \(d\ge2\) font diminuer \(r\) ; entre elles, \(d\) augmente. Les boucles terminent. À la sortie, \(d^2>r\) et tous les plus petits diviseurs ont été exclus : si \(r>1\), le critère de la racine carrée montre qu’il est premier. On l’ajoute une dernière fois.

Si \(r=1\), rien ne doit être ajouté : 1 n’est pas premier.

À toi : Calculer et expliquer l’unicité

Guidé.

Décompose 420 par divisions successives ; compte les apparitions de 2 avant de passer à 3.

Tentative.

Décompose 936, puis retrouve le même résultat en partant de \(936=9\times104\).

Justifie.

Pourquoi deux arbres différents ne produisent-ils pas deux listes finales différentes de facteurs premiers ? N’écris pas seulement « parce qu’on trouve le même résultat ».

Variation.

Que manque-t-il à l’écriture \(936=2^3\times117\) ?

Indices progressifs : Traiter les branches jusqu’au bout

\(420\div2=210\) ; \(936\div2=468\). Le nombre 117 est divisible par 3, car \(1+1+7=9\). Pour la justification, rappelle le rôle du lemme d’Euclide dans la comparaison de deux produits de premiers.

Correction expliquée : Deux chemins, une fiche de facteurs

\(420\to210\to105\to35\to7\to1\) par divisions par \(2,2,3,5,7\). Donc \(420=2^2\times3\times5\times7\) ; contrôle \(4\times3\times35=420\).

Pour 936 : \(936\to468\to234\to117\to39\to13\to1\) par \(2,2,2,3,3,13\). Donc \(936=2^3\times3^2\times13\). La variante donne \(9=3^2\) et \(104=8\times13=2^3\times13\), donc la même écriture.

Contrôle :

\(8\times9\times13=72\times13=936\).

L’unicité dit que deux produits de premiers égaux ont les mêmes facteurs, avec les mêmes répétitions : Euclide force chaque premier de la première liste à apparaître dans la seconde, puis on simplifie et on recommence. C’est l’argument attendu.

Dans \(2^3\times117\), le facteur 117 n’est pas premier : il faut encore écrire \(117=3\times3\times13\).

Si tu t’es trompé : Si tu as oublié une répétition ou le dernier reste

Erreur :

« \(180=2\times3\times5\). »

Rappel :

on garde un facteur autant de fois qu’il divise le quotient.

Exemple simple corrigé :

\(12\div2=6\), \(6\div2=3\), puis le reste 3 est premier : \(12=2^2\times3\), et non \(2\times3\).

Nouvel essai :

décompose 75.

Correction :

\(75=3\times25=3\times5\times5=3\times5^2\) ; le produit \(3\times25\) redonne 75.

Retour :

refais la trace de 180 et entoure les deux apparitions de 2, les deux de 3 et le dernier facteur 5.

Pour réparer une erreur : Demain, sans regarder les listes

Décompose 882. Explique aussi pourquoi l’algorithme renvoie \([19]\) pour 19.

Aide :

\(882\div2=441\) et \(441=21^2\).

Correction :

\(441=3^2\times7^2\), donc \(882=2\times3^2\times7^2\) ; \(2\times9\times49=882\).

Pour 19, aucun de 2, 3, 4 ne divise le reste ; à \(d=5\), \(25>19\), le reste 19 est ajouté.

Critères :

chaque facteur premier, produit exact, dernier reste expliqué, sens de l’unicité distinct du calcul.

À retenir : Deux affirmations différentes

L’existence garantit qu’on peut finir en facteurs premiers. L’unicité garantit que les facteurs et leurs répétitions ne dépendent pas du chemin choisi. Le calcul pratique doit vérifier les deux : facteurs premiers et produit d’origine.

À retenir : Ce que tu vas apprendre

Obtenir une liste complète de diviseurs, justifier qu’il n’y a ni oubli ni doublon, et compter sans devoir toujours écrire toute la liste.

Rappel utile : Une décomposition unique

Tout entier \(n\ge2\) possède une décomposition unique en facteurs premiers, à l’ordre près. On regroupe les répétitions : \(72=2^3\times3^2\). Un exposant nul signifie l’absence du facteur : \(2^0=1\). Si \(d\mid n\) avec \(d>0\), il existe \(k\ge1\) tel que \(n=dk\).

Multiplier deux puissances de même base additionne leurs exposants.

Avant de commencer : Un facteur peut-il apparaître de nulle part ?

Le nombre \(72=2^3\times3^2\) peut-il avoir 5 pour diviseur ? Et \(2^4=16\) ?

Correction.

Non dans les deux cas. Un facteur 5 dans un diviseur apparaîtrait dans la décomposition du produit égal à 72 ; il y est absent. Un diviseur contenant quatre facteurs 2 en demanderait plus que les trois disponibles. C’est l’idée que nous allons formaliser.

Théorème : Diviseurs et exposants

Soit \(n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\), avec les \(p_i\) premiers distincts et \(\alpha_i\ge1\). Les diviseurs positifs de \(n\) sont exactement

Démonstration : Nécessité et suffisance

Si \(d\mid n\), écrivons \(n=dk\) avec \(k\ge1\). Chaque facteur premier de \(d\) apparaît dans \(n\) ; par unicité de la décomposition, il est l’un des \(p_i\). L’exposant de \(p_i\) dans \(n\) est la somme de son exposant \(\beta_i\) dans \(d\) et de son exposant dans \(k\), qui est positif ou nul. Donc \(0\le\beta_i\le\alpha_i\).

Réciproquement, si ces inégalités sont vérifiées, les entiers \(\alpha_i-\beta_i\) sont positifs ou nuls. Le produit \(k=p_1^{\alpha_1-\beta_1}\cdots p_r^{\alpha_r-\beta_r}\) est entier et \(dk=n\). Ainsi \(d\mid n\). Le choix de tous les exposants nuls donne bien le diviseur 1 ; le choix \(\beta_i=\alpha_i\) donne \(n\).

Corollaire : Nombre de diviseurs positifs

Avec les mêmes hypothèses, le nombre de diviseurs positifs est

Démonstration : Compter les choix, sans compter deux fois un nombre

Pour \(\beta_1\), on a les \(\alpha_1+1\) choix \(0,1,\ldots,\alpha_1\). Pour chacun d’eux, on peut choisir indépendamment \(\beta_2\), puis les autres exposants. On multiplie donc les nombres de choix.

Deux listes d’exposants différentes donnent deux entiers différents par unicité de la décomposition première. Aucun diviseur n’est donc compté deux fois ; le théorème précédent garantit qu’ils le sont tous.

Méthode : Construire une liste organisée

Premier geste :

décomposer le nombre et écrire les puissances autorisées de chaque facteur, en commençant par la puissance 0. Construire les produits dans un tableau ou une arborescence, un facteur après l’autre. Classer ensuite si l’on demande une liste croissante.

Contrôles :

le nombre de résultats doit être celui du corollaire ; à chaque diviseur \(d\) doit correspondre le diviseur \(n/d\). Ce dernier contrôle est utile, mais ne suffit pas seul à prouver qu’une liste est exhaustive : plusieurs paires pourraient avoir été oubliées.

Exemple expliqué : Les 24 diviseurs de 360

\(360=36\times10=2^3\times3^2\times5\). Les exposants de 2 ont 4 choix, ceux de 3 en ont 3, ceux de 5 en ont 2 : il y a \(4\times3\times2=24\) diviseurs positifs. On construit d’abord les produits de \(1,2,4,8\) par \(1,3,9\), puis les mêmes produits multipliés par 5 :

Le tableau contient \(3\times8=24\) nombres différents. Par exemple, \(24=2^3\times3\) a pour complément \(360/24=15=3\times5\). Le diviseur 1 est présent ; 360 aussi. Le nombre 16 n’est pas présent, car il demanderait un exposant de 2 égal à 4.

Méthode : Variante par paires de diviseurs

Pour un nombre petit, on peut chercher \(d\) jusqu’à \(\sqrt n\) et associer à chaque diviseur \(d\) le quotient \(n/d\). Pour 36, les paires sont \((1,36),(2,18),(3,12),(4,9),(6,6)\), donc les diviseurs sont \(1,2,3,4,6,9,12,18,36\).

Il faut écrire 6 une seule fois : le centre est une paire égale. Cette variante est efficace si la borne est petite ; les exposants organisent mieux les grands nombres déjà décomposés.

Proposition : Un nombre impair de diviseurs

Un entier positif possède un nombre impair de diviseurs positifs si et seulement si c’est un carré parfait.

Démonstration : Le seul diviseur qui peut se retrouver seul

Les diviseurs se groupent en paires \(d\) et \(n/d\). Les deux membres sont distincts sauf si \(d=n/d\), c’est-à-dire \(d^2=n\). Si \(n\) n’est pas un carré, toutes les paires ont deux membres : le nombre de diviseurs est pair. S’il est un carré, seul \(d=\sqrt n\) reste non apparié, et tous les autres vont par deux : le nombre est impair. Pour \(n=1\), le seul diviseur est 1, ce qui est cohérent.

À toi : Lister, puis imposer une condition

Guidé.

Décompose 84, compte ses diviseurs et écris-les tous.

Tentative.

Pour \(450=2\times3^2\times5^2\), combien y a-t-il de diviseurs positifs ? Parmi eux, combien sont multiples de 6 ? Donne cette sous-liste.

Justifie.

Pourquoi doit-on autoriser l’exposant 0 dans la description ? La réponse doit montrer au moins un diviseur qui disparaîtrait sinon.

Variation.

Explique pourquoi 18 divise 450, mais 12 ne le divise pas, sans effectuer les deux divisions décimales.

Indices progressifs : Transformer la condition en exposants

\(84=4\times21\). Pour un multiple de \(6=2\times3\), l’exposant de 2 doit valoir 1 et celui de 3 doit être au moins 1 ; celui de 5 reste libre.

Correction expliquée : Toutes les possibilités justifiées

\(84=2^2\times3\times7\) : il a \((2+1)(1+1)(1+1)=12\) diviseurs, qui sont \(1,2,3,4,6,7,12,14,21,28,42,84\). Les paires \((1,84),(2,42),(3,28),(4,21),(6,14),(7,12)\) contrôlent les produits.

Pour 450, il y a \((1+1)(2+1)(2+1)=18\) diviseurs. Les multiples de 6 sont \(2\times3^b\times5^c\) avec \(b\in\{1,2\}\) et \(c\in\{0,1,2\}\) : \(1\times2\times3=6\) choix. On trouve \(6,18,30,90,150,450\). L’exposant 0 représente l’absence d’un facteur : sans lui, 1 serait toujours oublié, et 2 serait oublié dès que d’autres facteurs sont présents.

Enfin \(18=2\times3^2\) n’utilise pas plus de facteurs que 450 ; \(12=2^2\times3\) exige deux facteurs 2 alors que 450 n’en contient qu’un.

Si tu t’es trompé : Si tu as multiplié les exposants sans ajouter 1

Erreur :

« \(12=2^2\times3\) a \(2\times1=2\) diviseurs. »

Rappel :

les exposants vont de 0 au maximum, bornes comprises.

Exemple corrigé :

ceux de 2 sont \(0,1,2\) (trois choix), ceux de 3 sont \(0,1\) (deux choix). Les six diviseurs sont \(1,2,3,4,6,12\).

Nouvel essai :

compte les diviseurs de \(20=2^2\times5\).

Correction :

\((2+1)(1+1)=6\) ; ce sont \(1,2,4,5,10,20\).

Retour :

recalcule les nombres de choix pour 84 avant de relire sa liste.

Pour réparer une erreur : Demain, sans tableau prérempli

Trouve tous les diviseurs de \(90=2\times3^2\times5\), puis les diviseurs impairs.

Aide :

impair signifie que l’exposant de 2 est nul.

Correction :

les 12 diviseurs sont \(1,2,3,5,6,9,10,15,18,30,45,90\) ; les 6 impairs sont \(1,3,5,9,15,45\).

Critères :

liste sans doublon, compte \(2\times3\times2=12\), condition d’imparité traduite en exposant.

Proposition : Somme des diviseurs, conséquence de l’énumération

La somme des diviseurs positifs de \(n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\) vaut

Démonstration : Développer toutes les possibilités

En développant le produit, on choisit exactement une puissance dans chaque parenthèse. Chaque terme obtenu est donc un diviseur ; tous les diviseurs apparaissent une fois, par le théorème des exposants. Cela suffit à prouver la formule, sans introduire de nouvelle fonction.

Exemple expliqué : Un essai supplémentaire corrigé

Pour \(18=2\times3^2\), la somme vaut \((1+2)(1+3+9)=3\times13=39\) ; la liste \(1,2,3,6,9,18\) donne bien 39. À toi : fais de même pour 28.

Correction :

\(28=2^2\times7\), donc \((1+2+4)(1+7)=7\times8=56\). Les diviseurs strictement inférieurs à 28 ont pour somme \(56-28=28\). Un entier positif égal à la somme de ses diviseurs positifs strictement plus petits que lui est appelé parfait. Ce vocabulaire est ici un complément ; il n’est pas nécessaire au parcours principal.

Avant de commencer : Lire les exposants avant de chercher le nombre

Soient \(p\) et \(q\) deux nombres premiers distincts. Combien de diviseurs positifs ont \(p^2\) et \(pq\) ? Justifie sans choisir de valeurs pour \(p,q\).

Correction.

Pour \(p^2\), l’exposant du diviseur est 0, 1 ou 2 : les trois diviseurs sont \(1,p,p^2\). Pour \(pq\), chacun des deux exposants vaut 0 ou 1 ; les quatre diviseurs sont \(1,p,q,pq\). Si tu as répondu 2 dans le premier cas ou 3 dans le second, reprends le comptage des choix d’exposants : il faut inclure l’exposant nul et toutes les combinaisons. La formule \((\alpha_1+1)\cdots(\alpha_r+1)\) du nombre de diviseurs encode ces choix.

Méthode : Retrouver un entier depuis son nombre de diviseurs

Indice :

on connaît le nombre de diviseurs, mais pas encore l’entier.

Premier geste :

factoriser le nombre de choix \((\alpha_1+1)\cdots(\alpha_r+1)\), et non deviner directement \(n\). Chaque facteur \(\alpha_i+1\) est au moins égal à 2, car on ne garde que les premiers réellement présents dans \(n\). Par exemple, pour exactement neuf diviseurs, les seules décompositions de 9 en facteurs entiers au moins égaux à 2 sont \(9\) et \(3\times3\).

On a donc soit un seul exposant \(\alpha=8\), soit deux exposants égaux à 2 :

Contrôle :

si l’on écrit deux premiers égaux dans la deuxième forme, on obtient \(p^4\), qui a cinq diviseurs et non neuf. Les profils d’exposants doivent utiliser des bases premières distinctes.

Exemple expliqué : Exactement neuf diviseurs et moins de 150

La forme \(p^8\) est impossible : \(p\ge2\) impose \(p^8\ge2^8=256>150\).

Pour \(p^2q^2<150\), on peut choisir \(p<q\) et l’on doit avoir \(pq<\sqrt{150}<13\), donc \(pq\le12\). Si \(p=2\), les seuls premiers \(q>2\) avec \(2q\le12\) sont 3 et 5. Si \(p\ge3\), alors \(q\ge5\), donc \(pq\ge15>12\) : aucun autre cas. Les deux nombres sont \(2^2\times3^2=36\) et \(2^2\times5^2=100\).

Chacun a \((2+1)(2+1)=9\) diviseurs. L’analyse était exhaustive et la vérification montre que les deux candidats conviennent.

À toi : Des profils à retrouver

Guidé.

Quelle est la forme d’un entier ayant exactement trois diviseurs positifs ? Trouve tous ceux qui sont inférieurs à 50.

Tentative.

Retrouve tous les entiers inférieurs à 200 ayant exactement neuf diviseurs.

Justifie.

Pourquoi la forme \(p^2q^2\) exige-t-elle \(p\ne q\) ? Donne la décomposition regroupée lorsque \(p=q\).

Variation.

Un entier ayant exactement quatre diviseurs est-il nécessairement le produit de deux premiers distincts ?

Indices progressifs : Compter les choix d’exposants

Trois est premier : un produit de facteurs au moins égaux à 2 égal à 3 n’a qu’un seul facteur. Pour neuf diviseurs, la borne 200 ne permet toujours pas \(p^8\) ; dans l’autre cas, \(pq<\sqrt{200}<15\). Pour quatre diviseurs, examine aussi la décomposition multiplicative \(4=4\).

Correction expliquée : Analyse puis vérification

Trois diviseurs imposent un seul exposant \(\alpha\) tel que \(\alpha+1=3\), donc \(n=p^2\) avec \(p\) premier. Sous 50, \(p<\sqrt{50}<8\) : \(p=2,3,5,7\), d’où \(n=4,9,25,49\). Pour neuf diviseurs sous 200, \(p^8\ge256\) est exclu. La condition \(p<q\), \(pq\le14\) donne \((p,q)=(2,3),(2,5),(2,7)\) ; si \(p\ge3\), \(q\ge5\), donc \(pq\ge15\). Les nombres sont \(36,100,196\).

Tous ont les deux exposants 2, donc neuf diviseurs. Si \(p=q\), \(p^2q^2=p^4\), avec un seul exposant 4 : il y a cinq diviseurs.

Enfin quatre diviseurs correspondent à \(n=p^3\) ou \(n=pq\) avec premiers distincts. Le contre-exemple \(8=2^3\) réfute l’affirmation de la variation.

Critères :

profils exhaustifs, bornes vérifiées, bases distinctes, vérification du compte final.

Si tu t’es trompé : Si tu as oublié un profil

Erreur :

« six diviseurs signifie deux exposants 2 et 1 seulement ».

Rappel :

le produit des nombres de choix peut ne comporter qu’un facteur.

Exemple simple :

deux diviseurs correspond à \(\alpha+1=2\), donc à un premier seul.

Nouvel essai :

complète les profils pour six diviseurs.

Correction :

\(6=6\) ou \(6=3\times2\), donc \(p^5\) ou \(p^2q\) avec \(p\ne q\) premiers.

Retour :

refais les deux profils pour neuf.

Pour réparer une erreur : Plus tard : vérifier la frontière

Quels sont les entiers ayant neuf diviseurs et inférieurs ou égaux à 256 ?

Aide :

cette fois \(2^8\) atteint la borne.

Correction :

le profil \(p^8\) donne 256 seulement ; le profil \(p^2q^2\) impose \(pq\le16\) et \(p<q\). Les paires sont \((2,3),(2,5),(2,7),(3,5)\), donnant \(36,100,196,225\). La liste complète est donc \(36,100,196,225,256\) ; chacune des deux formes a exactement neuf diviseurs. L’égalité à la borne ne doit pas être omise.

À retenir : Lire les exposants

Diviseur : chaque exposant entre 0 et celui de \(n\). Nombre de diviseurs : produit des nombres de choix, donc des exposants augmentés de 1. Une condition supplémentaire, comme « pair » ou « multiple de 6 », se traduit par une restriction sur ces choix.

À retenir : Ce que tu vas apprendre

Reconnaître les puissances parfaites, compléter un nombre en carré ou en cube, et démontrer l’irrationalité d’une racine carrée de nombre premier.

Rappel utile : Les outils réunis ici

Un carré parfait est un entier de la forme \(a^2\) avec \(a\in\mathbb{N}\) ; un cube parfait positif est de la forme \(a^3\) avec \(a\in\mathbb{N}^*\).

Pour \(n\ge2\), la décomposition en facteurs premiers est unique. Les puissances vérifient \((p^u)^v=p^{uv}\) : élever au carré double les exposants ; élever au cube les triple. Si un premier \(p\) divise \(a^2\), il divise \(a\) par le lemme d’Euclide. Un rationnel positif s’écrit \(a/b\) avec \(a,b\in\mathbb{N}^*\) premiers entre eux après simplification de la fraction.

Avant de commencer : Des exposants, pas seulement une valeur décimale

\(2^4\times3^2\) est-il un carré ? Et \(2^3\times3^2\) ?

Correction.

Le premier est \((2^2\times3)^2=12^2=144\). Le second n’est pas un carré : l’exposant de 2 est impair ; le théorème suivant justifie ce critère. Si tu as obtenu \(2^6\times3^4\) en élevant \(2^3\times3^2\) au carré, tu as correctement doublé les exposants.

Théorème : Carrés et puissances parfaites

Soit \(n\ge2\) de décomposition \(n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\). L’entier \(n\) est un carré parfait si et seulement si tous les \(\alpha_i\) sont pairs. Plus généralement, pour un entier \(k\ge2\), \(n\) est une puissance \(k\)-ième d’entier positif si et seulement si tous les \(\alpha_i\) sont multiples de \(k\).

Démonstration : Prouver les deux sens

Si \(n=a^k\), décomposons \(a\) en facteurs premiers. En élevant ce produit à la puissance \(k\), chaque exposant est multiplié par \(k\). L’unicité oblige donc chaque exposant \(\alpha_i\) de \(n\) à être multiple de \(k\).

Réciproquement, si \(\alpha_i=k\beta_i\) avec \(\beta_i\in\mathbb{N}\), alors

Les cas \(n=0\) et \(n=1\) se traitent directement : \(0=0^2=0^3\) et \(1=1^2=1^3\). On ne décompose pas 0 en facteurs premiers.

Méthode : Compléter en une puissance avec le plus petit multiplicateur

Le nombre à multiplier est un entier \(n\ge1\) ; on cherche un multiplicateur entier strictement positif. Autoriser un nombre rationnel changerait le problème et le raisonnement sur les exposants.

Si \(n=1\), le multiplicateur minimal est directement 1.

Premier geste :

décomposer \(n\) et regarder chaque exposant. Pour obtenir un carré, ajouter un facteur \(p\) exactement lorsque son exposant est impair. Pour obtenir un cube, compléter chaque exposant au prochain multiple de 3 : ajouter 0, 1 ou 2 facteurs selon le cas.

On n’ajoute aucun nouveau premier, car cela agrandirait inutilement le multiplicateur.

Pourquoi est-ce minimal ?

Pour chaque premier, tout multiplicateur admissible doit fournir au moins le nombre de facteurs manquants. Le produit choisi divise donc tout autre multiplicateur admissible ; comme ils sont positifs, il est le plus petit.

Contrôle :

calculer la racine entière obtenue et élever de nouveau à la bonne puissance.

Exemple expliqué : Compléter 540 en carré puis en cube

On a \(540=54\times10=2^2\times3^3\times5\). Pour un carré, les exposants 3 de la base 3 et 1 de la base 5 sont impairs : il faut ajouter un facteur 3 et un facteur 5. Le plus petit multiplicateur est \(15=3\times5\). Alors

Corollaire : Quels diviseurs sont des carrés ?

Parmi les diviseurs de \(n\), les carrés sont exactement ceux dont tous les exposants sont pairs. Pour chaque premier \(p_i\), on choisit donc \(0,2,4,\ldots\) sans dépasser \(\alpha_i\).

Démonstration : Croiser deux conditions

La condition « diviseur » impose \(0\le\beta_i\le\alpha_i\). Le théorème des carrés impose que chaque \(\beta_i\) soit pair. Les deux conditions sont nécessaires et suffisantes ensemble ; il suffit de retenir leurs choix communs. Par exemple, pour \(72=2^3\times3^2\), les exposants possibles sont 0 ou 2 pour chaque base : les carrés diviseurs sont \(1,4,9,36\).

Théorème : Irrationalité de \(\sqrt p\)

Si \(p\) est un nombre premier, alors \(\sqrt p\) n’est pas un nombre rationnel.

Démonstration : Une fraction irréductible qui ne pourrait pas l’être

Supposons \(\sqrt p=a/b\) avec \(a,b\in\mathbb{N}^*\) premiers entre eux. En élevant les deux membres au carré, \(p=a^2/b^2\). Comme \(b\ne0\), on multiplie les deux membres par \(b^2\) : \(pb^2=a^2\). Ainsi \(p\mid a^2\), donc \(p\mid a\) par le lemme d’Euclide.

Écrivons \(a=pc\) avec \(c\in\mathbb{N}^*\). Substituons dans l’égalité : \(pb^2=(pc)^2=p^2c^2\). Le nombre \(p\) est non nul ; on divise les deux membres par \(p\) et on obtient \(b^2=pc^2\). Donc \(p\mid b^2\), puis \(p\mid b\). Le nombre \(p>1\) divise à la fois \(a\) et \(b\), en contradiction avec la fraction irréductible. L’hypothèse de rationalité est fausse.

Remarque : Ce que prouve, ou non, la calculatrice

Une écriture décimale longue ne prouve pas l’irrationalité : \(1/7\) possède déjà une écriture infinie, bien qu’il soit rationnel. La preuve précédente établit une impossibilité pour toute fraction, pas seulement pour les premières décimales observées.

À toi : Puissances et justification

Guidé.

Pour \(72=2^3\times3^2\), trouve le plus petit multiplicateur entier strictement positif donnant un carré, puis celui donnant un cube.

Tentative.

Fais les deux recherches pour 108 et donne tous ses diviseurs carrés.

Justification personnelle.

Explique pourquoi, dans la preuve d’irrationalité, le fait que \(p\) divise \(a\) ne suffit pas encore à la contradiction.

Variation.

Si on remplace « \(p\) premier » par « \(n\) composé », la racine est-elle toujours rationnelle ? Cherche un exemple de chaque type.

Indices progressifs : Compléter, puis contrôler

\(108=4\times27=2^2\times3^3\). Pour les diviseurs carrés, les exposants doivent être pairs et ne pas dépasser ceux de 108. Pour la variation, compare \(\sqrt4\) et \(\sqrt6\).

Correction expliquée : Les exposants disent quoi ajouter

Pour 72, le carré exige un facteur 2 : \(72\times2=144=12^2\). Le cube exige un facteur 3 : \(72\times3=216=6^3\).

Pour 108, le carré exige un facteur 3 : \(108\times3=2^2\times3^4=(2\times9)^2=324\). Le cube exige un facteur 2 : \(108\times2=2^3\times3^3=6^3=216\). Les diviseurs carrés de 108 sont \(2^a3^b\) avec \(a,b\in\{0,2\}\), soit \(1,4,9,36\). Une fraction irréductible peut avoir un numérateur divisible par \(p\) ; la contradiction exige un facteur commun au numérateur et au dénominateur. C’est pourquoi la preuve continue jusqu’à \(p\mid b\).

Enfin \(\sqrt4=2\) est rationnel. Pour \(\sqrt6\), supposons \(6b^2=a^2\) avec \(a,b\) entiers positifs. Dans les décompositions, l’exposant de 2 à gauche vaut \(1+2u\), donc est impair ; celui de droite vaut \(2v\), donc est pair. L’égalité est impossible. Ainsi \(\sqrt6\) est irrationnel, bien que 6 soit composé.

Si tu t’es trompé : Si tu as confondu carré et exposant 2 seulement

Erreur :

« \(2^4\times3^2\) n’est pas un carré car l’exposant 4 est trop grand. »

Rappel :

tout exposant pair convient.

Exemple simple corrigé :

\(2^4=(2^2)^2=4^2\).

Nouvel essai :

\(3^6\times5^2\) est-il un carré ?

Correction :

oui, \((3^3\times5)^2=135^2=18\,225\).

Retour :

coupe maintenant en deux les exposants de \(2^4\times3^2\) pour retrouver sa racine entière 12.

Pour réparer une erreur : À refaire avant de relire

Pour \(200=2^3\times5^2\), trouve le plus petit multiplicateur entier strictement positif donnant un carré, puis un cube. Explique pourquoi \(\sqrt{11}\) est irrationnel.

Aide :

pour le cube, l’exposant 3 convient déjà.

Correction :

multiplicateur 2 pour le carré : \(400=20^2\) ; multiplicateur 5 pour le cube : \(1000=10^3\).

Pour 11, si \(\sqrt{11}=a/b\) irréductible, \(11b^2=a^2\) entraîne \(11\mid a\). Avec \(a=11c\), on obtient \(b^2=11c^2\), puis \(11\mid b\), contradiction.

Critères :

les deux divisibilités, l’hypothèse « 11 premier » et la fraction initialement irréductible doivent apparaître.

Avant de commencer : Compter des occurrences, pas seulement des nombres

Dans \(25\times10\), combien de fois le facteur premier 5 apparaît-il ?

Correction.

\(25=5\times5\) et \(10=2\times5\), donc \(25\times10=2\times5\times5\times5=2\times5^3\). Il y a trois occurrences de 5, alors que seuls deux nombres du produit sont des multiples de 5. Si tu as répondu 2, reviens à la règle \(5^u5^v=5^{u+v}\) : dans un produit, les exposants d’une même base s’additionnent. Ici, celui de 25 vaut 2 et celui de 10 vaut 1.

Proposition : Compter un facteur premier dans une factorielle

Pour connaître le nombre total de facteurs \(p\) dans \(N!\), où \(p\) est premier et \(N\ge1\), on additionne le nombre de multiples de \(p\) entre 1 et \(N\), puis le nombre de multiples de \(p^2\), puis de \(p^3\), etc.

On s’arrête lorsque la puissance dépasse \(N\).

Démonstration : Compter chaque occurrence une fois

Chaque multiple de \(p\) fournit au moins un facteur \(p\). Un multiple de \(p^2\) en fournit au moins un deuxième, qui doit être compté en plus du premier ; un multiple de \(p^3\) en fournit encore un autre. Plus précisément, un entier qui contient exactement \(e\) facteurs \(p\) est compté dans les listes des multiples de \(p,p^2,\ldots,p^e\), et pas dans la suivante : il contribue exactement \(e\), comme il le faut.

En additionnant sur les facteurs \(1,2,\ldots,N\) de la factorielle, on compte donc toutes les occurrences, sans omission ni double comptage d’une même occurrence.

Exemple expliqué : Combien de zéros terminent l’écriture de \(40!\) ?

Un zéro final correspond à un facteur 10, donc à une paire de facteurs 2 et 5. Entre 1 et 40, on compte huit multiples de 5 et un multiple de 25. Ce dernier fournit un facteur 5 supplémentaire : \(40!\) contient exactement \(8+1=9\) facteurs 5. Il contient au moins 20 facteurs 2 grâce aux vingt entiers pairs : les facteurs 2 sont donc assez nombreux.

Il y a exactement neuf paires 2–5, donc exactement neuf zéros finaux.

Contrôle du sens :

ne compter que les multiples de 5 aurait oublié le deuxième facteur 5 de 25. Il n’est pas nécessaire de calculer l’immense entier \(40!\).

Méthode : Compter sans calculer la factorielle

Premier geste :

identifier le premier à compter. Pour les zéros finaux en écriture décimale, on a besoin de paires 2–5. Compter les multiples de 5, puis de 25, puis de 125, etc., jusqu’à dépasser la borne. Ce sont les quotients entiers des divisions de \(N\) par ces puissances.

Vérifier qu’il y a au moins autant de facteurs 2 ; pour les exemples ci-dessous, les entiers pairs fournissent déjà une borne suffisante.

Contrôle :

expliquer quel facteur supplémentaire représente chaque terme de la somme. Un multiple de 25 doit contribuer deux fois au total, pas une seule.

À toi : Compter une occurrence supplémentaire

Guidé.

Combien de zéros finaux possède \(30!\) ?

Tentative.

Même question pour \(80!\) ; puis trouve le nombre de facteurs 3 présents dans \(20!\).

Justifie.

Pourquoi 25 doit-il être compté dans deux listes ?

Variation.

« \(80!\) a 16 zéros car il y a 16 multiples de 5 » : localise exactement les occurrences oubliées.

Indices progressifs : Les puissances successives

Pour 30, regarde 5 et 25. Pour 80, les multiples de 25 sont 25, 50, 75.

Pour 20 et le facteur 3, les puissances utiles sont 3 et 9 ; 27 est trop grand.

Correction expliquée : Les totaux et leur sens

Dans \(30!\), il y a 6 multiples de 5 et 1 multiple de 25, soit 7 facteurs 5. Les 15 entiers pairs fournissent au moins 15 facteurs 2 : il y a 7 zéros. Dans \(80!\), il y a 16 multiples de 5 et 3 multiples de 25, soit 19 facteurs 5 ; les 40 pairs fournissent assez de facteurs 2 : il y a 19 zéros.

Dans \(20!\), les multiples de 3 sont 3, 6, 9, 12, 15, 18 (six nombres), et ceux de 9 sont 9, 18 (deux nombres). Le total vaut \(6+2=8\) facteurs 3. Le nombre \(25=5^2\) fournit un premier facteur 5 dans la liste des multiples de 5, puis son deuxième dans celle des multiples de 25.

Dans l’affirmation erronée sur \(80!\), on oublie les deuxièmes facteurs 5 de 25, 50 et 75. Les critères sont un compte exact, une occurrence expliquée et, pour les zéros, la vérification des facteurs 2.

Si tu t’es trompé : Si tu comptes des entiers au lieu des facteurs

Erreur :

compter 25 pour un seul facteur 5.

Rappel :

on compte les occurrences dans la décomposition, pas seulement le nombre d’entiers concernés.

Exemple simple corrigé :

\(25\times10=5^2\times(2\times5) =2\times5^3\) contient trois facteurs 5, bien qu’il n’y ait que deux entiers multipliés.

Nouvel essai :

combien de facteurs 5 dans \(50\times15\) ?

Correction :

\(50=2\times5^2\), \(15=3\times5\), donc \(50\times15=2\times3\times5^3\) : trois occurrences.

Retour :

recompte les trois facteurs supplémentaires de \(80!\).

Pour réparer une erreur : Demain : une puissance de plus

Combien de zéros finaux dans \(125!\) ?

Aide :

il faut aller jusqu’aux multiples de 125.

Correction :

25 multiples de 5, 5 multiples de 25, 1 multiple de 125, donc \(25+5+1=31\) facteurs 5. Il y a 62 entiers pairs, donc au moins 62 facteurs 2. Le nombre \(125!\) se termine exactement par 31 zéros. Le facteur 125 apporte trois occurrences, une à chacun des trois comptages.

À retenir : Lire un carré ou un cube

Carré : tous les exposants pairs. Cube : tous multiples de 3. Pour compléter, on ajoute seulement les facteurs manquants. Pour prouver une irrationalité, on raisonne sur une fraction supposée exacte, jamais sur l’approximation décimale de la racine.

À retenir : Ce que tu vas apprendre

Lire un PGCD dans deux décompositions, simplifier une fraction avec justification et transformer une équation entière en une recherche de diviseurs. Le PPCM est un complément séparé.

Rappel utile : Le kit de cette unité

Le PGCD de deux entiers positifs est leur plus grand diviseur commun. Un diviseur de \(p_1^{\alpha_1}\cdots p_r^{\alpha_r}\) possède les mêmes facteurs possibles, avec des exposants entre 0 et les maxima correspondants.

Une fraction est irréductible lorsque son numérateur et son dénominateur sont premiers entre eux. On peut diviser ses deux termes par un même nombre non nul sans changer sa valeur. L’identité \(x^2-y^2=(x-y)(x+y)\) vient du développement \(x^2+xy-xy-y^2=x^2-y^2\).

Avant de commencer : Facteurs communs ou tous les facteurs ?

Quel est le PGCD de \(40=2^3\times5\) et \(72=2^3\times3^2\) ? Pourquoi 5 ne peut-il pas y apparaître ?

Correction.

Le PGCD vaut \(2^3=8\) : les trois facteurs 2 sont communs, mais 5 n’apparaît pas dans 72 et 3 n’apparaît pas dans 40. Si tu as pris tous les facteurs, relis la définition d’un diviseur commun.

Propriété : PGCD : les plus petits exposants

Écrivons deux entiers positifs \(A\) et \(B\) avec la même liste de premiers, en autorisant des exposants nuls : \(A=\prod_{i=1}^r p_i^{\alpha_i}\) et \(B=\prod_{i=1}^r p_i^{\beta_i}\). Alors

Démonstration : Être commun, puis être le plus grand

Pour diviser à la fois \(A\) et \(B\), l’exposant d’un premier doit être au plus égal à \(\alpha_i\) et à \(\beta_i\), donc au plus égal au plus petit des deux. Le produit proposé respecte ces bornes : c’est un diviseur commun.

Tout autre diviseur commun a des exposants inférieurs ou égaux, donc divise ce produit. Un entier positif qui divise un autre entier positif lui est inférieur ou égal : le produit proposé est bien le plus grand.

Méthode : Simplifier avec le PGCD

Premier geste :

écrire les deux décompositions avec les mêmes premiers alignés, y compris les exposants 0 si nécessaire. Prendre les minima pour le PGCD \(d\), puis diviser le numérateur et le dénominateur par ce même \(d>0\). Les exposants restants n’ont plus de premier commun : pour chaque base, l’un des deux exposants devient 0. La fraction obtenue est irréductible.

Contrôle :

produit en croix, et absence de facteur premier commun. Si les nombres sont très grands et non factorisés, l’algorithme d’Euclide peut être plus rapide pour le PGCD ; les deux méthodes ne s’excluent pas.

Exemple expliqué : Simplifier sans effacer un facteur qui reste

Les décompositions sont \(756=2^2\times3^3\times7\) et \(540=2^2\times3^3\times5\). Le facteur commun \(2^2\times3^3=4\times27=108\) est non nul. En divisant le numérateur et le dénominateur par 108, on obtient

La fraction est donc irréductible.

Contrôle par produit en croix :

\(756\times5=3\,780\) et \(540\times7=3\,780\). Pour additionner \(\frac75\) et \(\frac13\), il faut ensuite un dénominateur commun :

Exemple expliqué : Contrôler par l’algorithme d’Euclide

Pour les mêmes nombres, \(756=540+216\), \(540=2\times216+108\), puis \(216=2\times108\). Le dernier reste non nul est 108 : on retrouve le PGCD lu dans les décompositions. La raison de l’algorithme est \(\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,a-qb)\) : les diviseurs communs sont inchangés lorsqu’on retranche un multiple de l’un des nombres à l’autre. C’est donc un contrôle indépendant des exposants.

Définition : Plus petit commun multiple positif

Pour \(A,B\in\mathbb{N}^*\), leur PPCM est le plus petit entier strictement positif multiple de \(A\) et de \(B\). Il existe puisque \(AB\) est déjà un multiple commun. Ce complément n’est pas une nouvelle notion nominale obligatoire du chapitre dans le BO ; il prolonge naturellement la lecture des exposants.

Propriété : PPCM : les plus grands exposants

Avec les notations précédentes, \(\operatorname{PPCM}(A,B)=\prod_{i=1}^r p_i^{\max(\alpha_i,\beta_i)}\). De plus, \(\operatorname{PGCD}(A,B)\times\operatorname{PPCM}(A,B)=AB\).

Démonstration : La condition inverse de celle du PGCD

Un multiple commun doit contenir au moins tous les facteurs de \(A\) et tous ceux de \(B\) : chaque exposant est au moins le maximum correspondant. Le produit des maxima est lui-même multiple des deux nombres et divise tout multiple commun ; c’est le plus petit positif.

Pour chaque couple d’exposants, \(\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)=\alpha_i+\beta_i\). Les deux membres de l’identité PGCD \(\times\) PPCM ont donc exactement les exposants du produit \(AB\) : l’identité est prouvée.

Exemple expliqué : Un multiple commun minimal

Pour 756 et 540, les maxima donnent \(2^2\times3^3\times5\times7=3780\). On vérifie \(3780=756\times5=540\times7\). Un produit de deux entiers n’est leur PPCM que lorsqu’ils sont premiers entre eux : l’identité précédente montre que le PGCD doit alors valoir 1.

Méthode : Remplacer une différence de carrés par deux diviseurs

Indice :

les inconnues sont entières et l’on voit \(x^2-y^2=N\).

Premier geste :

écrire \((x-y)(x+y)=N\). Si \(x\ge y\ge0\) et \(N>0\), poser \(u=x-y>0\) et \(v=x+y\ge u\). Chercher toutes les paires de diviseurs positifs \(uv=N\), puis garder celles où \(u,v\) ont la même parité. En effet,

La même parité garantit que les deux quotients sont entiers.

Contrôle :

substituer chaque couple dans l’équation de départ et expliquer pourquoi aucune paire de diviseurs n’a été omise.

Exemple expliqué : Résoudre \(x^2-y^2=45\) dans les entiers \(x\ge y\ge0\)

Comme \(45=3^2\times5\), ses paires de diviseurs \(u\le v\) sont \((1,45),(3,15),(5,9)\). Elles sont toutes de même parité. On obtient respectivement

Contrôles :

\(23^2-22^2=529-484=45\), \(9^2-6^2=81-36=45\), \(7^2-2^2=49-4=45\). La liste des paires était complète ; la liste des solutions l’est donc aussi.

À toi : Deux réinvestissements

Guidé.

Pour 360 et 504, calcule le PGCD et simplifie \(360/504\). Puis résous \(x^2-y^2=21\) pour \(x\ge y\ge0\) entiers.

Tentative.

Fais les mêmes recherches avec 840 et 1260, puis avec \(x^2-y^2=27\).

Justifie.

Pourquoi prend-on les minima pour un PGCD et non les maxima ? Pourquoi la parité doit-elle être vérifiée avant de reconstruire \(x,y\) ?

Variation.

Existe-t-il des entiers \(x\ge y\ge0\) tels que \(x^2-y^2=18\) ?

Indices progressifs : Ne pas mélanger les conditions

\(360=2^3\times3^2\times5\) ; \(504=2^3\times3^2\times7\).

Pour 21, les paires sont \((1,21),(3,7)\) ; pour 27, \((1,27),(3,9)\).

Pour 18, examine \((1,18),(2,9),(3,6)\).

Correction expliquée : Réponses et exhaustivité

Le PGCD de 360 et 504 vaut \(2^3\times3^2=72\). En divisant les deux termes par 72, \(360/504=5/7\), irréductible car 5 et 7 sont des premiers distincts. Pour 21, les paires donnent \(((1+21)/2,(21-1)/2)=(11,10)\) et \(((3+7)/2,(7-3)/2)=(5,2)\) ; \(121-100=21\) et \(25-4=21\).

Ensuite \(840=2^3\times3\times5\times7\) et \(1260=2^2\times3^2\times5\times7\) : le PGCD est \(2^2\times3\times5\times7=420\) et \(840/1260=2/3\).

Pour 27, les paires de diviseurs sont \((1,27)\) et \((3,9)\), toutes deux de même parité. La première donne \(x=(1+27)/2=28/2=14\) et \(y=(27-1)/2=26/2=13\). La seconde donne \(x=(3+9)/2=12/2=6\) et \(y=(9-3)/2=6/2=3\). Les solutions sont donc \((14,13)\) et \((6,3)\) ; \(196-169=27\) et \(36-9=27\).

Les minima sont nécessaires pour ne pas exiger plus de facteurs que l’un des deux nombres n’en possède. La parité est nécessaire pour que les divisions par 2 donnent des entiers. Aucune paire de diviseurs de 18 n’a la même parité : il n’y a donc aucune solution entière dans le domaine demandé. Un produit de deux entiers de même parité est impair ou multiple de 4, jamais égal à 18.

Si tu t’es trompé : Si une formule donne un résultat non entier

Erreur :

garder la paire \((2,9)\) pour 18 et annoncer une solution entière.

Rappel :

\(x=(u+v)/2\), \(y=(v-u)/2\) doivent être entiers.

Exemple simple corrigé :

\((u,v)=(1,5)\) donne \((x,y)=(3,2)\), mais \((1,4)\) donne \((5/2,3/2)\), non entier.

Nouvel essai :

la paire \((3,6)\) convient-elle pour 18 ?

Correction :

\((x,y)=(9/2,3/2)\), donc non.

Retour :

reprends toutes les paires de 18 en inscrivant leur parité. Pour une erreur de PGCD, reviens à 40 et 72 : le facteur 5 est absent de 72, donc ne peut pas être conservé dans un diviseur commun.

Pour réparer une erreur : Dans quelques jours

Simplifie \(252/198\), puis résous \(x^2-y^2=15\) pour des entiers \(x\ge y\ge0\).

Aide :

\(252=2^2\times3^2\times7\) et \(198=2\times3^2\times11\).

Correction :

le PGCD est 18, donc \(252/198=14/11\). Les paires \((1,15),(3,5)\) donnent \((8,7)\) et \((4,1)\) ; \(64-49=15\) et \(16-1=15\).

Critères :

même diviseur appliqué aux deux termes, fraction irréductible, paires exhaustives et contrôle des solutions.

À retenir : Ce que l’on fait des facteurs

Pour un diviseur commun, on garde les minima ; pour un multiple commun minimal, les maxima. Dans une équation entière, factoriser peut transformer une recherche infinie d’inconnues en une liste finie de paires de diviseurs.

À retenir : Ce que tu vas apprendre

Reconnaître les deux formes du petit théorème de Fermat, vérifier leurs hypothèses, comprendre une démonstration complète et établir une divisibilité sans calculer une puissance immense.

Rappel utile : Divisibilité, nombres premiers et congruences

Pour des entiers \(a,b\), écrire \(a\mid b\) signifie qu’il existe \(k\in\mathbb{Z}\) tel que \(b=ak\). Un nombre premier est un entier \(p\ge2\) dont les seuls diviseurs positifs sont \(1\) et \(p\). Si \(p\) est premier et ne divise pas \(a\), alors \(\operatorname{PGCD}(a,p)=1\) : un diviseur commun positif ne peut être que \(1\) ou \(p\), et le second choix est exclu.

Pour \(m\ge2\), \(x\equiv y\;[m]\) signifie \(m\mid(x-y)\). On peut ajouter, soustraire ou multiplier des congruences de même module. En particulier, \(x\equiv y\;[m]\) entraîne \(x^r\equiv y^r\;[m]\) pour tout entier \(r\ge1\). Pourquoi peut-on multiplier ? Si \(x=y+km\) et \(u=v+\ell m\), alors

En revanche, on ne peut pas toujours simplifier un facteur dans une congruence.

Rappel utile : Le résultat de Bézout utilisé ici

Le théorème de Bézout, établi dans le chapitre sur le PGCD et repris dans l’unité consacrée au lemme d’Euclide, donne : si \(\operatorname{PGCD}(a,p)=1\), il existe \(u,v\in\mathbb{Z}\) tels que \(au+pv=1\). Nous utilisons ce résultat antérieur avec ses hypothèses ; le petit théorème de Fermat n’intervient pas dans sa démonstration.

Lemme : Lemme d’Euclide, dans la forme nécessaire

Soit \(p\) premier. Si \(p\mid ab\) et \(p\nmid a\), alors \(p\mid b\).

Démonstration : Pourquoi le facteur premier ne disparaît pas

Comme \(p\nmid a\), on a \(\operatorname{PGCD}(a,p)=1\). Bézout fournit \(au+pv=1\). On multiplie les deux membres par \(b\) :

En répétant ce raisonnement, si \(p\) divise un produit de plusieurs entiers, il divise au moins l’un de ses facteurs.

Corollaire : Une simplification autorisée modulo un nombre premier

Si \(p\) est premier, \(p\nmid c\) et \(cu\equiv cv\;[p]\), alors \(u\equiv v\;[p]\).

Démonstration : On ne divise pas des restes

La congruence de départ signifie \(p\mid c(u-v)\). Le lemme, appliqué au produit \(c(u-v)\) et à l’hypothèse \(p\nmid c\), donne \(p\mid(u-v)\). C’est précisément \(u\equiv v\;[p]\).

Avant de commencer : Vérifier une hypothèse avant de calculer

Pour chacun des couples \((p,a)=(5,15)\), \((7,-3)\) et \((4,3)\), réponds : \(p\) est-il premier ? \(p\) divise-t-il \(a\) ?

Correction.

\(5\) est premier, mais \(15=5\times3\) : la condition \(p\nmid a\) échoue. \(7\) est premier et \(-3=7\times(-1)+4\), avec un reste non nul : \(7\nmid-3\). Enfin \(4=2\times2\) n’est pas premier, même si \(4\) ne divise pas \(3\). Reprends les définitions du kit si tu as confondu « \(p\) ne divise pas \(a\) » et « \(p\) est premier ».

Théorème : Petit théorème de Fermat

Soit \(p\) un nombre premier et \(a\) un entier relatif.

1. Pour tout entier \(a\), on a

   \[\boxed{a^p\equiv a\;[p]},\qquad\text{c'est-à-dire}\qquad p\mid(a^p-a).\]

2. Si, de plus, \(p\) ne divise pas \(a\), alors

   \[\boxed{a^{p-1}\equiv1\;[p]},\qquad\text{c'est-à-dire}\qquad p\mid(a^{p-1}-1).\]

Les exposants sont \(p\) dans la première forme et \(p-1\) dans la seconde.

Remarque : Ce que dit le théorème, et ce qu’il ne dit pas

Il donne un reste ou une divisibilité à partir d’une primalité connue. Il ne dit pas que le reste de \(a^p\) est nécessairement le nombre \(a\) : si \(a\) n’est pas entre \(0\) et \(p-1\), on prend son représentant dans cet intervalle. Il ne dit pas non plus qu’une congruence vérifiée suffit à prouver que le module est premier.

Notation : Une écriture courte pour un produit

Pour \(n\ge1\), la factorielle \(n!\) désigne \(1\times2\times\cdots\times n\). Ainsi \(1!=1\) et \(4!=1\times2\times3\times4=24\). Dans la preuve, \((p-1)!\) est un entier non nul, mais sa seule non-nullité ne permettra pas de le simplifier modulo \(p\) : il faudra aussi montrer que \(p\) ne le divise pas.

Représentation intuitive : Réordonner des étiquettes, sans en perdre

Imagine les \(p-1\) étiquettes \(1,2,\ldots,p-1\). Multiplier par \(a\), puis prendre le reste modulo \(p\), donne une nouvelle étiquette à chaque ancienne. Lorsque \(p\) est premier et \(p\nmid a\), la preuve va montrer qu’on ne crée ni l’étiquette \(0\), ni deux fois la même étiquette.

La nouvelle liste contient donc les mêmes étiquettes dans un autre ordre. Cette image explique le mot permutation, qui signifie ici simplement « réorganisation d’une liste ». L’image ne prouve pas que les étiquettes sont différentes : c’est précisément le travail du lemme.

Démonstration : D’abord la forme avec l’exposant \(p-1\)

On suppose \(p\) premier et \(p\nmid a\). Pour chaque \(j\in\{1,2,\ldots,p-1\}\), notons \(r_j\) le reste de \(aj\) dans la division par \(p\). On a donc \(aj\equiv r_j\;[p]\) et \(0\le r_j<p\).

1. Aucun reste n’est nul.

Si \(r_j=0\), alors \(p\mid aj\). Puisque \(p\nmid a\), le lemme d’Euclide donnerait \(p\mid j\). Or \(1\le j<p\) : aucun tel \(j\) n’est un multiple de \(p\). C’est impossible. Tous les restes sont donc parmi \(1,2,\ldots,p-1\).

2. Deux indices différents ne donnent pas le même reste.

Supposons \(r_j=r_k\). Alors \(aj\equiv ak\;[p]\), donc \(p\mid a(j-k)\). Le lemme donne \(p\mid(j-k)\). Or \(-(p-1)\le j-k\le p-1\) ; le seul multiple de \(p\) dans cet intervalle est \(0\). Ainsi \(j-k=0\), puis \(j=k\).

3. La liste des restes est une permutation de la liste initiale.

Il y a \(p-1\) restes, tous différents, choisis parmi exactement \(p-1\) nombres possibles. Ils les utilisent donc tous une fois. Leur produit vaut

4. On multiplie les congruences, puis on simplifie licitement.

En multipliant les \(p-1\) congruences \(aj\equiv r_j\;[p]\), on obtient

On peut donc appliquer le corollaire de simplification avec \(c=(p-1)!\) :

Démonstration : Puis la forme valable pour tout entier \(a\)

Si \(p\nmid a\), on multiplie \(a^{p-1}\equiv1\;[p]\) par \(a\) :

Ce second cas comprend \(a=0\) et les multiples négatifs de \(p\).

Pour \(p=2\), la première partie de la preuve utilise seulement la liste à un élément \(1\) et \(1!=1\) : elle reste valable. Elle dit qu’un entier impair vérifie \(a^1\equiv1\;[2]\) ; la forme générale donne \(a^2\equiv a\;[2]\) pour tout entier, pair ou impair.

Exemple expliqué : Voir la permutation avec \(p=7\) et \(a=4\)

Les multiples \(4,8,12,16,20,24\) ont pour restes modulo \(7\) :

Le produit des multiples est \(4^6\times6!\), celui des restes est \(6!\). Comme \(7\) ne divise aucun des facteurs \(1,\ldots,6\), on simplifie \(6!\) dans la congruence et on retrouve \(4^6\equiv1\;[7]\). Ce calcul illustre la preuve générale ; lui seul ne prouverait pas le théorème pour tous les nombres premiers.

Méthode : Établir une divisibilité avec Fermat

Indices.

Un module premier \(p\) est donné et l’expression ressemble à \(a^p-a\), \(a^{p-1}-1\) ou contient une grande puissance.

Premier geste.

Écrire le module et vérifier sa primalité ; noter ensuite si \(p\) divise la base \(a\).

1. Avec \(a^p-a\), employer la forme valable pour tout entier \(a\).

2. Avec \(a^{p-1}-1\), vérifier explicitement \(p\nmid a\) avant de conclure.

3. Traduire le reste nul en divisibilité. Pour un autre exposant, la réduction par multiples de \(p-1\) se justifie en décomposant l’exposant.

Contrôle.

Les mots « premier » et, lorsque nécessaire, « ne divise pas la base » doivent correspondre aux données réelles.

Exemple expliqué : Une divisibilité universelle, puis une condition indispensable

Pour tout entier \(n\), \(11\mid(n^{11}-n)\), car \(11\) est premier et la première forme de Fermat s’applique sans restriction sur \(n\). En particulier, il n’est pas nécessaire de traiter séparément les multiples de \(11\) dans cette application : ce cas est déjà inclus dans le théorème.

À l’inverse, \(13\nmid(26^{12}-1)\). En effet, \(26=2\times13\), donc \(26^{12}\equiv0\;[13]\) et \(26^{12}-1\equiv-1\equiv12\;[13]\). Écrire \(26^{12}\equiv1\;[13]\) aurait utilisé une hypothèse fausse.

Piège à éviter : Ni module composé, ni réciproque automatique

Même si \(a\) et le module sont premiers entre eux, on ne peut pas appliquer Fermat avec un module composé : \(3\) et \(4\) sont premiers entre eux, mais \(3^{4-1}=27=4\times6+3\), donc \(3^3\not\equiv1\;[4]\).

Réciproquement, \(8\equiv-1\;[9]\), donc \(8^8\equiv(-1)^8=1\;[9]\), alors que \(9=3^2\) est composé. Une congruence qui convient à une base ne constitue pas un certificat de primalité du module.

À toi : Des hypothèses qui changent la conclusion

Guidé.

Montrer que \(13\mid(9^{12}-1)\). Identifie \(p\), compare l’exposant à \(p-1\), puis vérifie si \(p\) divise \(9\).

Tentative avant correction.

Décide si chacune des affirmations est vraie : \(17\mid(3^{17}-3)\) ; \(17\mid(34^{16}-1)\). Pour une affirmation fausse, donne le reste de l’expression.

Justifie avec tes mots.

Pourquoi, dans la preuve, faut-il montrer que \(p\) ne divise pas \((p-1)!\) avant de simplifier ?

Critères :

nommer le lemme utilisé et donner un exemple où la simplification d’un facteur divisible par le module serait fausse.

Indices progressifs : Choisir une forme sans perdre une condition

Pour le guidé, \(12=13-1\). Pour la première tentative, compare directement \(3^{17}\) à \(3\). Pour la seconde, commence par \(34=2\times17\). Pour la justification, compare \(5\times1\) et \(5\times2\) modulo \(5\).

Correction expliquée : Les trois décisions et une justification possible

\(13\) est premier et ne divise pas \(9\). La seconde forme donne \(9^{12}\equiv1\;[13]\), donc \(13\mid(9^{12}-1)\). Les nombres \(13\) et \(17\) sont premiers : pour chacun, il suffit de tester \(2\) et \(3\), les seuls premiers au plus égaux à sa racine carrée ; aucune de ces divisions n’est exacte.

\(17\) étant premier, la première forme donne \(3^{17}\equiv3\;[17]\) : la première affirmation est vraie. En revanche \(34\equiv0\;[17]\), donc \(34^{16}-1\equiv0-1\equiv16\;[17]\). Ce reste non nul prouve que la seconde affirmation est fausse.

Une justification possible est : « Le lemme d’Euclide autorise la simplification d’un facteur qui n’est pas divisible par le nombre premier. Sans cette condition, \(5\times1\equiv5\times2\;[5]\) est vraie, mais \(1\equiv2\;[5]\) est fausse. Montrer seulement que le facteur est non nul ne suffit donc pas. »

Si tu t’es trompé : Si tu as oublié de tester la base

Erreur.

« \(7\) est premier, donc \(14^6\equiv1\;[7]\). »

Rappel.

La forme à l’exposant \(p-1\) exige aussi \(p\nmid a\). Ici \(14=2\times7\) : c’est précisément l’hypothèse manquante.

Plus simple, corrigé.

Avec \(p=2\) et \(a=4\), on a \(4^{2-1}=4\equiv0\;[2]\), et non \(1\).

Nouvel essai.

Quel est le reste de \(39^{12}-1\) modulo \(13\) ?

Correction.

\(39=3\times13\), donc \(39^{12}-1\equiv-1\equiv12\;[13]\) ; le reste est \(12\).

Retour.

Pour l’affirmation initiale, \(14^6\equiv0\;[7]\) et \(14^6-1\equiv6\;[7]\). Réécris ta première ligne en séparant les deux hypothèses au lieu de répéter seulement le nom du théorème.

Pour réparer une erreur : Demain, sans rouvrir la preuve d’abord

1. Montrer que \(11\mid\bigl((-2)^{11}+2\bigr)\). 2. Donner les restes de \((-2)^{10}\) et \(22^{10}\) modulo \(11\).

Aide minimale.

Les entiers négatifs sont autorisés ; vérifie séparément si la base est divisible par \(11\).

Correction à masquer pendant la recherche.

La forme générale donne \((-2)^{11}\equiv-2\;[11]\), donc \((-2)^{11}+2\equiv0\;[11]\). Ensuite \(11\nmid-2\) permet d’écrire \((-2)^{10}\equiv1\;[11]\). Enfin \(22=2\times11\) donne \(22^{10}\equiv0\;[11]\). Les restes demandés sont respectivement \(1\) et \(0\), tous deux dans l’intervalle de \(0\) à \(10\).

À retenir : Le théorème et le mécanisme de sa preuve

Avec \(p\) premier : \(a^p\equiv a\;[p]\) pour tout entier \(a\) ; \(a^{p-1}\equiv1\;[p]\) seulement si \(p\nmid a\). La preuve réordonne les restes non nuls, multiplie leurs congruences puis simplifie une factorielle première avec le module. La propriété d’un nombre premier est une hypothèse, jamais une conclusion obtenue par la simple réciproque de Fermat.

Remarque : Une preuve facultative, indépendante de la permutation

La preuve par permutation reste la première méthode conseillée. Voici une autre démonstration, fondée sur le développement d’un produit. Elle constitue une piste de problème possible du programme ; tu n’as pas besoin de la maîtriser pour utiliser le théorème dans le parcours principal.

Les outils de dénombrement nécessaires sont expliqués ici.

Définition : Coefficients binomiaux : compter des groupes

Pour \(n\ge1\) et \(0\le k\le n\), on note \(\binom nk\) le nombre de manières de choisir un groupe de \(k\) éléments parmi \(n\) éléments distincts, sans tenir compte de l’ordre. C’est un entier : il compte des groupes.

Il y a un seul groupe vide et un seul groupe qui contient tous les éléments ; ainsi \(\binom n0=\binom nn=1\). Par exemple, choisir deux éléments parmi cinq peut se faire en prenant d’abord un premier élément (\(5\) choix), puis un autre (\(4\) choix). Ces \(5\times4=20\) choix ordonnés comptent chaque paire deux fois, dans les deux ordres. Donc \(\binom52=20/2=10\).

Ce quotient est entier parce qu’il provient de ce comptage, pas parce que toute fraction d’entiers serait un entier.

Lemme : Les coefficients intermédiaires d’un binôme premier

Si \(p\) est premier et \(1\le k<p\), alors \(p\) divise \(\binom pk\).

Démonstration : Une identité entière avant de simplifier

Comptons les choix d’un groupe de \(k\) éléments parmi \(p\), avec un membre distingué dans ce groupe. On peut choisir d’abord le groupe, puis son membre distingué : cela fait \(k\binom pk\) choix. On peut aussi choisir d’abord le membre distingué parmi les \(p\) éléments, puis les \(k-1\) autres membres parmi les \(p-1\) restants : cela fait \(p\binom{p-1}{k-1}\) choix.

Les deux procédés décrivent exactement les mêmes objets, chacun une fois. Ainsi

Le lemme d’Euclide permet alors de conclure \(p\mid\binom pk\). On n’a pas divisé une congruence par \(k\) sans justification.

Proposition : Le binôme obtenu par distributivité

Pour \(n\ge2\) et tout entier \(a\),

Démonstration : D’où vient chaque coefficient ?

Écrivons \((a+1)^n\) comme un produit de \(n\) facteurs \((a+1)\). Lorsqu’on distribue, on choisit dans chacun de ces facteurs soit \(a\), soit \(1\), puis on multiplie les \(n\) termes choisis. Pour obtenir \(a^k\), on choisit \(a\) dans exactement \(k\) des \(n\) positions, et \(1\) dans les autres. Il existe exactement \(\binom nk\) choix de ces positions. Chaque choix contribue une fois au développement.

Choisir uniquement des \(1\) donne le terme \(1\) ; choisir uniquement des \(a\) donne \(a^n\). Additionner tous les choix donne la formule annoncée. Le raisonnement n’impose pas \(a>0\) : il s’agit de la distributivité, valable aussi pour un entier négatif ou nul.

Pour voir le mécanisme avec trois facteurs, les huit choix donnent

Démonstration : Fermat par récurrence, puis pour les entiers négatifs

Fixons un nombre premier \(p\). Dans le développement précédent avec \(n=p\), tous les coefficients intermédiaires sont divisibles par \(p\), d’après le lemme. Leurs produits par les entiers \(a^k\) sont encore divisibles par \(p\).

Il reste donc, pour tout entier \(a\),

Montrons par récurrence sur \(a\in\mathbb{N}\) que \(a^p\equiv a\;[p]\).

Initialisation.

Pour \(a=0\), \(0^p=0\) puisque \(p\ge2\).

Hérédité.

Supposons \(a^p\equiv a\;[p]\) pour un entier \(a\ge0\). La relation issue du binôme donne

Pour un entier relatif quelconque \(b\), écrivons sa division euclidienne par \(p\) : \(b=pq+r\) avec \(0\le r<p\). Alors \(b\equiv r\;[p]\), donc \(b^p\equiv r^p\;[p]\). Comme \(r\) est naturel, la récurrence donne \(r^p\equiv r\;[p]\). Ainsi \(b^p\equiv r\equiv b\;[p]\), y compris si \(b<0\).

Par exemple \(-8=7\times(-2)+6\) : on se ramène au reste naturel \(6\), pas à une récurrence mal définie vers les entiers négatifs.

Enfin, si \(p\nmid b\), l’égalité de congruences \(b\,b^{p-1}\equiv b\times1\;[p]\) se simplifie par le lemme d’Euclide et donne \(b^{p-1}\equiv1\;[p]\). Les deux formes de Fermat sont ainsi retrouvées sans utiliser la preuve par permutation.

À toi : Vérifier le rôle de chaque condition dans cette autre preuve

1. Sans calculer d’abord \(\binom73\), montre que ce nombre est divisible par \(7\), puis calcule-le pour vérifier. 2. Pourquoi ne peut-on pas remplacer « \(p\) premier » par « \(p\ge2\) » dans le lemme ? Examine \(\binom42\).

Indice.

Utilise l’identité avec un membre distingué. Pour compter une paire, les deux ordres décrivent le même groupe.

Correction.

L’identité donne \(3\binom73=7\binom62\). Comme \(7\) est premier et ne divise pas \(3\), le lemme d’Euclide donne \(7\mid\binom73\). Pour vérifier la valeur, \(\binom62=(6\times5)/2=15\) ; donc \(3\binom73=7\times15=105\). En divisant les deux membres de l’égalité par \(3\ne0\), on obtient \(\binom73=35=7\times5\).

Enfin \(\binom42=(4\times3)/2=6\) n’est pas divisible par \(4\). L’identité de comptage demeure vraie, mais le passage de \(4\mid2\binom42\) à \(4\mid\binom42\) ne serait pas autorisé.

À retenir : Ce que tu vas apprendre

Calculer un reste sans développer une puissance gigantesque ; choisir entre Fermat, un cycle et les carrés successifs ; comprendre et contrôler un algorithme d’exponentiation modulaire.

Rappel utile : Un reste n’est pas n’importe quel représentant

Pour \(m\ge2\), \(a\equiv b\;[m]\) signifie que \(a-b\) est un multiple de \(m\). Le reste de \(a\) dans la division euclidienne par \(m\) est l’unique entier \(r\) tel que \(a\equiv r\;[m]\) et \(0\le r<m\). Ainsi \(-3\equiv10\;[13]\), car \(-3=13\times(-1)+10\) ; le reste est \(10\), et non \(-3\).

Les congruences de même module se multiplient : si \(x\equiv x'\;[m]\) et \(y\equiv y'\;[m]\), alors \(xy\equiv x'y'\;[m]\). On peut donc réduire un résultat après chaque multiplication sans changer le reste final. Pour les puissances, \(a^{r+s}=a^ra^s\) et \(a^{rs}=(a^r)^s\). Pour \(a\ne0\), \(a^0=1\).

L’expression \(0^0\) n’est pas utilisée dans cette unité.

Rappel utile : Fermat, avec toutes ses hypothèses

Si \(p\) est premier, \(a^p\equiv a\;[p]\) pour tout entier relatif \(a\). Si, en outre, \(p\nmid a\), alors \(a^{p-1}\equiv1\;[p]\). Ces deux formes ont été démontrées dans l’unité sur Fermat ; elles sont réénoncées ici pour que tu puisses choisir une méthode sans la rouvrir.

Un module composé n’autorise pas l’emploi automatique de ces formules.

Avant de commencer : Trois gestes courts avant une grande puissance

1. Écris la division de \(47\) par \(8\). 2. Si \(x\equiv6\;[25]\), à quoi \(x^2\) est-il congru ? 3. Peut-on appliquer directement la forme \(a^{p-1}\equiv1\) avec le module \(21\) ?

Correction.

\(47=8\times5+7\) : le quotient est \(5\), le reste \(7\). Ensuite \(x^2\equiv6^2=36=25+11\), donc \(x^2\equiv11\;[25]\).

Enfin \(21=3\times7\) est composé : Fermat ne s’y applique pas directement. Si tu avais remplacé \(6^2\) par \(2\times6\), reprends le sens d’une puissance : \(6^2=6\times6\), tandis que \(2\times6=12\).

Proposition : Réduction par un multiple de \(p-1\)

Soit \(p\) premier et \(a\in\mathbb{Z}\) tel que \(p\nmid a\). Si \(n=(p-1)q+r\), avec \(q\in\mathbb{N}\) et \(0\le r<p-1\), alors

Démonstration : Pourquoi on divise l’exposant par \(p-1\)

Les règles des puissances donnent

Méthode : La méthode conseillée quand le module est premier

Indices.

Le module est un nombre premier connu et la base n’est pas un multiple de ce module.

Premier geste.

Écrire les deux hypothèses et la congruence \(a^{p-1}\equiv1\;[p]\).

1. Diviser l’exposant \(n\) par \(p-1\), en écrivant \(n=(p-1)q+r\).

2. Remplacer \(a^n\) par \((a^{p-1})^q a^r\), puis réduire à \(a^r\).

3. Calculer cette petite puissance, éventuellement avec des carrés successifs, et réduire le résultat entre \(0\) et \(p-1\).

Contrôle.

La division porte sur \(p-1\), pas sur \(p\), et le dernier nombre annoncé doit être un reste euclidien. Si \(p\mid a\) et \(n\ge1\), le reste est directement \(0\) : cette méthode de réduction de l’exposant n’est alors pas applicable.

Exemple expliqué : Réduire un exposant, sous les bonnes conditions

On cherche le reste de \(7^{2026}\) dans la division par 13. Le nombre 13 est premier et ne divise pas 7 ; Fermat donne donc \(7^{12}\equiv1\;[13]\). La division de l’exposant est \(2026=12\times168+10\), d’où

Comme \(0\le4<13\), le reste demandé est 4. Le théorème a été utilisé dans le sens « premier \(\Rightarrow\) congruence ». Une congruence vérifiée ne permet pas de remonter automatiquement au caractère premier du module.

Bon réflexe : Un exposant exactement multiple : le cas à ne pas oublier

Pour le même module \(13\) et la même base \(7\), on a \(2028=12\times169\). Comme \(13\nmid7\),

Proposition : Un retour à \(1\) suffit pour réduire les exposants

Soient \(m\ge2\), \(a\in\mathbb{Z}\) et \(t\ge1\). Si \(a^t\equiv1\;[m]\), alors, pour tout \(n=tq+r\) avec \(q\in\mathbb{N}\) et \(0\le r<t\),

Démonstration : Même calcul, hypothèse différente

On écrit \(a^n=(a^t)^qa^r\equiv1^qa^r=a^r\;[m]\). Cette preuve n’exige pas que \(m\) soit premier : elle exige que la congruence \(a^t\equiv1\;[m]\) ait été établie. Le nombre \(t\) n’a pas besoin d’être le plus petit exposant possible.

Méthode : Exploiter une petite puissance facile

Indices.

Une première puissance est congrue à \(1\) ou à \(-1\), ou les restes calculés semblent se répéter très vite.

Premier geste.

Calculer et justifier une petite puissance, au lieu d’affirmer qu’un motif observé se prolongera toujours. Si \(a^t\equiv1\), diviser l’exposant par \(t\) et utiliser la proposition. Si \(a^t\equiv-1\), écrire d’abord \(a^{2t}\equiv(-1)^2=1\).

Contrôle.

Un retour seulement supposé, ou plusieurs restes qui se ressemblent, ne constituent pas une preuve de période.

Exemple expliqué : Un module composé n’empêche pas un calcul court

Calculons le reste de \(8^{2026}\) modulo \(21\). On a \(8^2=64=3\times21+1\), donc \(8^2\equiv1\;[21]\). Comme \(2026=2\times1013\),

Le raisonnement repose sur le carré calculé, pas sur Fermat avec \(21\).

Remarque : Tous les cycles ne commencent pas par un retour à \(1\)

Modulo \(8\), les restes de \(2^1,2^2,2^3,2^4\) sont \(2,4,0,0\). Pour tout \(n\ge3\), \(2^n=8\times2^{n-3}\) est divisible par \(8\). Il y a donc une suite de restes finalement constante, mais aucune de ces puissances positives n’est congrue à \(1\). N’invente pas une période permettant de ramener n’importe quel exposant à \(0\).

Méthode : Une méthode générale, sans primalité du module

Indices.

Pas de retour court évident, ou un module qui ne permet pas d’appliquer Fermat directement.

Premier geste.

Réduire la base modulo \(m\), puis calculer les restes de \(a^2,a^4,a^8,a^{16},\ldots\) en élevant chaque reste au carré.

1. Décomposer \(n\) en somme de puissances de \(2\) distinctes. On peut soustraire à chaque fois la plus grande puissance de \(2\) qui ne dépasse pas le reste de l’exposant.

2. Multiplier seulement les puissances retenues.

3. Réduire modulo \(m\) après chaque multiplication pour garder de petits nombres.

Pourquoi cela fonctionne.

\(a^{u+v}=a^ua^v\) et les congruences se multiplient ; aucune hypothèse « \(m\) premier » n’est nécessaire.

Contrôle.

Vérifier la somme des exposants retenus, puis que le dernier reste est compris entre \(0\) et \(m-1\).

Exemple expliqué : Calculer \(3^{47}\) modulo \(25\)

Les carrés successifs donnent

La vérification \(32+8+4+2+1=47\) contrôle le choix des puissances ; elle ne remplace pas le contrôle des multiplications.

Algorithme : Exponentiation modulaire

Les entrées sont des entiers \(a\), \(n\ge0\) et \(m\ge2\) ; le couple \((a,n)=(0,0)\) est exclu. La sortie est le reste de \(a^n\) modulo \(m\). Dans le code, % donne un reste et // le quotient de la division entière. La variable \(R\) accumule les facteurs retenus, \(X\) est la base courante et \(E\) l’exposant qu’il reste à traiter.

def puissance_modulaire(a, n, m):
    if m < 2 or n < 0 or (a == 0 and n == 0):
        raise ValueError("entrees invalides")
    if n == 0:
        return 1
    R = 1
    X = a % m
    E = n
    while E > 0:
        if E % 2 == 1:
            R = (R * X) % m
        X = (X * X) % m
        E = E // 2
    return R

Démonstration : Invariant, sortie et terminaison

Lorsque \(E>0\), au début d’un passage dans la boucle, la relation conservée est \(RX^E\equiv a^n\;[m]\). Elle est vraie initialement puisque \(R=1\), \(E=n\) et \(X\equiv a\;[m]\). Notons \(R,X,E\) les valeurs avant les mises à jour.

Si \(E=2h\) est pair et positif, \(h\ge1\). Le nouvel accumulateur reste congru à \(R\), la nouvelle base à \(X^2\), et le nouvel exposant vaut \(h\). Leur produit pertinent est donc \(R(X^2)^h=RX^{2h}=RX^E\) : l’invariant est conservé.

Si \(E=2h+1\) est impair avec \(h\ge1\), le nouvel accumulateur est congru à \(RX\), la nouvelle base à \(X^2\) et le nouvel exposant vaut \(h\). On obtient \((RX)(X^2)^h=RX^{2h+1}=RX^E\) : même conclusion.

Il reste le cas \(E=1\) : la mise à jour donne \(R_{\rm nouveau}\equiv RX\), qui est congru à \(a^n\) par l’invariant. Le nouvel exposant est \(0\), la boucle s’arrête et le résultat est acquis. On n’a pas eu besoin d’interpréter une expression \(0^0\).

Enfin \(E\) est un entier positif tant que la boucle continue et son remplaçant, le quotient entier de sa division par \(2\), est strictement plus petit : la boucle se termine. Les réductions par % m maintiennent \(0\le R<m\) ; le nombre retourné est donc le reste euclidien demandé.

Si \(n=0\) et \(a\ne0\), la sortie directe \(1\) correspond à \(a^0=1\).

Exemple expliqué : Une trace complète pour \(5^{13}\) modulo \(23\)

À chaque ligne, les trois valeurs de gauche sont celles avant le passage, celles de droite sont obtenues après toutes les mises à jour.

Les nouvelles bases viennent de \(5^2=25=23+2\), \(2^2=4\), \(4^2=16\), puis \(16^2=256=11\times23+3\). Les exposants sont les quotients entiers successifs de \(13,6,3,1\) par \(2\) : \(6,3,1,0\). La sortie est \(21\).

Contrôle indépendant par les puissances sélectionnées :

\(13=8+4+1\), \(5^2\equiv2\), \(5^4\equiv4\), \(5^8\equiv16\;[23]\) ; donc \(5^{13}\equiv16\times4\times5=320\equiv21\;[23]\). L’invariant porte sur les étapes complètes, pas sur un état situé au milieu des mises à jour.

À toi : Trois calculs, sans écrire les grands nombres

Guidé.

Calculer le reste de \(6^{2025}\) modulo \(11\). Écris la congruence fournie par Fermat, divise \(2025\) par \(10\), puis calcule la puissance qui reste.

Tentatives avant correction.

Détermine les restes de \(4^{103}\) modulo \(15\) et de \(6^{37}\) modulo \(25\). Choisis une démarche et justifie-la ; plusieurs méthodes sont possibles.

Justifie avec tes mots.

Pourquoi réduit-on l’exposant modulo \(p-1\), et non modulo \(p\), dans la méthode de Fermat ?

Critères :

écrire la puissance qui vaut \(1\) modulo \(p\) et exhiber un contre-exemple à la réduction incorrecte.

Indices progressifs : Une première puissance peut suffire

Pour le guidé, \(2025=10\times202+5\) ; calcule \(6^2\), puis \(6^4\). Pour le premier essai, regarde \(4^2\) modulo \(15\). Pour le second, utilise les carrés d’exposants \(2,4,8,16,32\) et \(37=32+4+1\), ou cherche un retour à \(1\).

Pour la justification, compare \(2^6\) et \(2^1\) modulo \(5\).

Correction expliquée : Des méthodes adaptées à chaque module

\(11\) est premier et ne divise pas \(6\). Ainsi \(6^{10}\equiv1\;[11]\), puis \(6^{2025}\equiv6^5\;[11]\). On calcule \(6^2=36=3\times11+3\), donc \(6^4\equiv3^2=9\) et \(6^5\equiv9\times6=54=4\times11+10\).

Le reste est \(10\).

On a \(4^2=16=15+1\) et \(103=2\times51+1\) ; donc \(4^{103}\equiv1^{51}\times4=4\;[15]\). Il n’a pas été nécessaire de supposer \(15\) premier.

Pour \(6^{37}\) modulo \(25\), les carrés donnent

Avec \(37=5\times7+2\), on retrouve \(6^{37}\equiv6^2\equiv11\).

Une justification possible est : « Fermat donne \(a^{p-1}\equiv1\), donc on retire des paquets de \(p-1\) facteurs, pas des paquets de \(p\). Par exemple \(2^6=64\equiv4\;[5]\), alors que réduire \(6\) modulo \(5\) à \(1\) ferait annoncer \(2^1\equiv2\), ce qui est faux. »

Exemple expliqué : Variation : une base négative ou divisible par le module

Pour \((-3)^{28}\) modulo \(13\), les hypothèses de Fermat sont satisfaites : \(13\) est premier et \(13\nmid-3\). Comme \(28=12\times2+4\),

Pour \(7^0\), le reste modulo \(13\) vaut \(1\) ; un exposant nul ne produit pas un résultat nul.

Si tu t’es trompé : Si tu as utilisé Fermat avec un module composé

Erreur.

« \(2^8\equiv1\;[9]\), car \(8=9-1\). »

Rappel.

Il manque l’hypothèse « module premier » : \(9=3^2\).

Plus simple, corrigé.

\(2^3=8\equiv0\;[4]\), et non \(1\). Un exposant égal au module moins \(1\) ne suffit pas.

Nouvel essai.

Recalcule \(2^8\) modulo \(9\) par carrés successifs.

Correction.

\(2^2=4\) ; \(2^4=16\equiv7\;[9]\) ; \(2^8\equiv7^2=49=5\times9+4\equiv4\;[9]\).

Retour.

La réponse initiale \(1\) est remplacée par \(4\), avec une méthode qui ne suppose pas la primalité du module.

Si tu t’es trompé : Si l’algorithme utilise le nouveau carré trop tôt

Erreur.

Remplacer d’abord \(X\) par son carré, puis multiplier \(R\) par ce nouveau \(X\) lorsque \(E\) est impair.

Rappel.

Le facteur retenu est l’ancienne base ; le carré prépare seulement l’étape suivante.

Plus simple, corrigé.

Pour \(2^1\) modulo \(5\), la bonne étape donne \(R=1\times2=2\). Utiliser d’abord le carré donnerait \(4\), résultat faux.

Nouvel essai.

Trace les deux passages pour \(5^3\) modulo \(7\).

Correction.

De \((R,X,E)=(1,5,3)\), on passe à \((5,4,1)\), car \(5^2=25\equiv4\;[7]\). On passe ensuite à \((6,2,0)\), car \(5\times4=20\equiv6\) et \(4^2=16\equiv2\;[7]\). La sortie \(6\) coïncide avec \(125=17\times7+6\).

Retour.

Dans la trace de \(5^{13}\) modulo \(23\), vérifie que la dernière multiplication utilise \(16\), et non son nouveau carré \(3\).

Pour réparer une erreur : Demain, avant de relire les méthodes

1. Détermine le reste de \(3^{30}\) modulo \(17\). 2. Trace les valeurs de \((R,X,E)\) pour \(5^4\) modulo \(12\).

Aide minimale.

Pour la première question, \(30=16+14\) et \(14=8+4+2\). Pour la seconde, \(5^2\equiv1\;[12]\).

Correction à masquer pendant la recherche.

\(17\) est premier et ne divise pas \(3\), donc \(3^{30}\equiv3^{14}\;[17]\). On a \(3^2=9\), \(3^4=81=4\times17+13\), \(3^8\equiv13^2=169=9\times17+16\). Le produit est \(16\times13\times9\) ; on réduit \(16\times13=208=12\times17+4\), puis \(4\times9=36=2\times17+2\).

Le premier reste demandé est \(2\). La seconde trace est \((1,5,4)\to(1,1,2)\to(1,1,1)\to(1,1,0)\) : la sortie est \(1\).

À retenir : Choisir sans mélanger les justifications

Fermat réduit l’exposant modulo \(p-1\) lorsque \(p\) est premier et ne divise pas la base. Un cycle établi \(a^t\equiv1\) permet une réduction modulo \(t\), même si le module est composé. Les carrés successifs fonctionnent dans les deux situations. Dans l’algorithme, le facteur de l’étape courante est utilisé avant le nouveau carré ; l’invariant se contrôle après les mises à jour complètes. Un reste final doit satisfaire \(0\le r<m\).

À retenir : Ce que tu vas apprendre

Déterminer un inverse modulo un entier par Bézout ou par Fermat, résoudre une congruence linéaire et traiter les coefficients non inversibles sans effectuer une division interdite.

Rappel utile : Ce que signifie résoudre une congruence

Dans toute cette unité, \(m\) est un entier avec \(m\ge2\) et les inconnues sont des entiers relatifs. La notation \(u\equiv v\;[m]\) signifie qu’il existe \(k\in\mathbb{Z}\) tel que \(u-v=mk\). Ainsi

On peut additionner, soustraire et multiplier des congruences de même module. La division par un entier non nul n’est pas une règle générale.

Rappel utile : PGCD et Bézout, avec leurs hypothèses

Puisque \(m>0\), \(g=\operatorname{PGCD}(a,m)\) est le plus grand diviseur commun positif de \(a\) et \(m\), même lorsque \(a\) est nul ou négatif. Le théorème de Bézout donne des entiers \(u,v\) tels que \(au+mv=g\). En particulier, \(a\) et \(m\) sont premiers entre eux si et seulement si il existe \(u,v\in\mathbb{Z}\) avec \(au+mv=1\).

Ces résultats ont été établis dans le chapitre PGCD/Bézout/Gauss ; ils sont repris ici sous la forme exacte dont nous avons besoin.

Pour trouver les coefficients, l’algorithme d’Euclide enchaîne des divisions euclidiennes jusqu’au reste nul ; le dernier reste non nul est le PGCD. On remonte ensuite les égalités pour écrire ce PGCD comme combinaison entière des deux nombres de départ. L’exemple ci-dessous montre toutes les substitutions nécessaires.

Avant de commencer : Multiplier pour obtenir un reste égal à \(1\)

1. Vérifie que \(3\times3\equiv1\;[8]\). 2. Peut-on trouver un entier \(u\) tel que \(2u\equiv1\;[8]\) ? 3. Traduis \(x\equiv-2\;[7]\) en une famille d’entiers.

Correction.

\(3\times3=9=8+1\). En revanche, \(2u\equiv1\;[8]\) signifierait \(2u-1=8k\), donc \(1=2u-8k=2(u-4k)\) : un nombre impair serait pair, contradiction.

Enfin les solutions sont \(x=-2+7k\), \(k\in\mathbb{Z}\), ou, de manière équivalente, \(x=5+7k\), \(k\in\mathbb{Z}\). Les représentants \(-2\) et \(5\) diffèrent de \(7\). Si tu avais répondu seulement \(x=5\), reprends la traduction du kit.

Définition : Inverse modulaire

Un entier \(u\) est un inverse de \(a\) modulo \(m\) lorsque

Exemple expliqué : Un inverse n’est pas la fraction \(1/a\)

\(3\) est un inverse de \(3\) modulo \(8\), car \(3\times3=9=8+1\). Dans les nombres réels, l’inverse de \(3\) est \(1/3\), pas \(3\). Dans notre calcul modulo \(8\), on travaille avec des entiers et avec la condition de congruence. Les entiers \(3+8k\), \(k\in\mathbb{Z}\), sont eux aussi des inverses de \(3\) modulo \(8\), puisque \(3(3+8k)=9+24k=1+8(1+3k)\).

Caractérisation : Quand un inverse existe-t-il ?

Un entier \(a\) possède un inverse modulo \(m\ge2\) si et seulement si \(\operatorname{PGCD}(a,m)=1\). Lorsqu’il existe, cet inverse est unique modulo \(m\) : tous les inverses sont congrus entre eux.

Démonstration : Existence : les deux sens ; puis unicité

Si un inverse existe.

Soit \(u\) tel que \(au\equiv1\;[m]\). On peut écrire \(au-1=km\), donc \(au-km=1\). Tout diviseur commun positif de \(a\) et \(m\) divise \(au\) et \(km\), donc leur différence \(1\). Ce diviseur vaut nécessairement \(1\) ; ainsi \(\operatorname{PGCD}(a,m)=1\).

Si le PGCD vaut \(1\).

Bézout fournit \(au+mv=1\). On a \(au-1=-mv\), multiple de \(m\) ; donc \(au\equiv1\;[m]\). Le coefficient \(u\) est un inverse de \(a\).

Unicité modulo \(m\).

Si \(u\) et \(w\) sont deux inverses, alors \(au\equiv aw\equiv1\;[m]\) et \(m\mid a(u-w)\). Choisissons une identité de Bézout \(as+mt=1\) et multiplions-la par \(u-w\) :

Enfin chaque entier \(u+mk\) est bien un inverse, puisque \(a(u+mk)=au+amk\equiv1\;[m]\).

Corollaire : Le cas particulier d’un module premier

Si \(p\) est premier, un entier \(a\) possède un inverse modulo \(p\) si et seulement si \(p\nmid a\).

Démonstration : Les deux seuls diviseurs possibles

Un diviseur commun positif de \(a\) et \(p\) vaut \(1\) ou \(p\). Le PGCD vaut donc \(1\) exactement lorsque \(p\) ne divise pas \(a\). On applique alors la caractérisation précédente.

Méthode : Méthode de référence : Euclide puis Bézout

Indices.

On cherche un inverse modulo un entier, premier ou non.

Premier geste.

Calculer le PGCD : s’il n’est pas \(1\), aucun inverse n’existe et il est inutile de poursuivre une recherche au hasard. Si le PGCD vaut \(1\), remonter les divisions pour obtenir \(au+mv=1\). Le coefficient de \(a\), et non celui de \(m\), est l’inverse recherché.

On peut remplacer ce coefficient par son reste modulo \(m\).

Contrôle.

Multiplier l’inverse proposé par \(a\) et vérifier que la différence avec \(1\) est un multiple de \(m\).

Exemple expliqué : Construire un inverse de \(7\) modulo \(19\)

Les divisions d’Euclide donnent

Contrôle :

\(7\times11=77=4\times19+1\). Le coefficient \(3\) de \(19\) n’est pas l’inverse cherché ; le produit \(7\times3=21\) n’a pas pour reste \(1\) modulo \(19\).

Proposition : Un inverse donné par Fermat

Si \(p\) est premier et \(p\nmid a\), alors \(a^{p-2}\) est un inverse de \(a\) modulo \(p\).

Démonstration : Une multiplication ramène au théorème

Le petit théorème de Fermat, démontré dans l’unité correspondante, donne \(a^{p-1}\equiv1\;[p]\). Or \(a\times a^{p-2}=a^{p-1}\) : la définition d’un inverse est satisfaite.

Pour \(p=2\), l’exposant \(p-2\) vaut \(0\) ; la base \(a\) est impaire, donc non nulle, et \(a^0=1\) est bien son inverse modulo \(2\).

Méthode : Fermat : utile si le module est premier

Vérifier que le module \(p\) est premier et ne divise pas \(a\), puis calculer le reste de \(a^{p-2}\) par carrés successifs ou par un cycle justifié. Le reste obtenu est l’inverse ; le produit final par \(a\) le contrôle.

Cette méthode ne remplace pas Bézout avec un module composé, et elle n’est pas toujours plus courte qu’une remontée d’Euclide.

Exemple expliqué : Deux calculs de puissance qui certifient un inverse

Avec \(a=7\) et \(p=19\), Fermat propose \(7^{17}\). Modulo \(19\), on calcule

Pour inverser \(5\) modulo \(13\), Fermat propose \(5^{11}\). Or \(5^2=25\equiv-1\;[13]\) ; ainsi \(5^4\equiv1\) et \(5^8\equiv1\). Puisque \(11=8+2+1\),

Contrôle :

\(5\times8=40=3\times13+1\).

Proposition : Une seule famille de solutions modulo \(m\)

Si \(\operatorname{PGCD}(a,m)=1\) et \(u\) est un inverse de \(a\) modulo \(m\), alors

Démonstration : Une équivalence, pas une seule implication

Si \(ax\equiv b\;[m]\), on multiplie les deux membres par \(u\) : \(uax\equiv ub\;[m]\). Comme \(ua\equiv1\), cela donne \(x\equiv ub\;[m]\).

Réciproquement, si \(x\equiv ub\;[m]\), on multiplie par \(a\) : \(ax\equiv aub\equiv1\times b=b\;[m]\). La traduction de la congruence en une famille d’entiers a été rappelée au début de l’unité.

Méthode : Isoler une inconnue entière correctement

Premier geste.

Vérifier le PGCD du coefficient et du module. S’il vaut \(1\), trouver un inverse, multiplier les deux membres de la congruence par cet inverse, puis réduire le second membre. Donner enfin toute la famille d’entiers, pas seulement le reste choisi.

Contrôle.

Remplacer \(x\) par la famille obtenue et montrer que \(ax-b\) est bien un multiple du module. Ne jamais ajouter la condition \(x\ne0\) : c’est le coefficient qui doit être inversible, pas l’inconnue.

Exemple expliqué : Résoudre \(7x\equiv11\;[19]\)

L’inverse de \(7\) modulo \(19\) est \(11\). En multipliant les deux membres par \(11\), on obtient \(77x\equiv121\;[19]\). Comme \(77\equiv1\) et \(121\equiv7\;[19]\),

Exemple expliqué : Passer d’une congruence à une famille d’entiers

Résoudre \(5x\equiv3\;[17]\) ne signifie pas diviser des restes par 5. On observe \(5\times7=35=2\times17+1\) : 7 est un inverse de 5 modulo 17. En multipliant les deux membres de la congruence par 7, \(35x\equiv21\;[17]\), donc \(x\equiv4\;[17]\).

Cela signifie \(x-4=17k\) pour un entier \(k\). On ajoute 4 aux deux membres : \(x=4+17k\). Réciproquement,

Théorème : Résoudre \(ax\equiv b\;[m]\) dans tous les cas

Soient \(a,b\in\mathbb{Z}\), \(m\ge2\) et \(g=\operatorname{PGCD}(a,m)\).

1. Si \(g\) ne divise pas \(b\), il n’y a aucune solution.

2. Si \(g\mid b\) et \(g<m\), on pose \(a'=a/g\), \(b'=b/g\), \(m'=m/g\). La congruence équivaut à \(a'x\equiv b'\;[m']\) et \(\operatorname{PGCD}(a',m')=1\). On la résout donc par un inverse modulo \(m'\).

3. Si \(g=m\) et \(g\mid b\), tous les entiers \(x\) sont solutions. Ce cas comprend le coefficient \(a=0\) lorsque \(m\mid b\).

Démonstration : La bonne division porte aussi sur le module

Une solution vérifie \(ax-b=mk\), donc \(b=ax-mk\). Comme \(g\) divise \(a\) et \(m\), il divise nécessairement \(b\). Cela prouve l’impossibilité lorsque \(g\nmid b\).

Supposons désormais \(g\mid b\). Les entiers \(a',b',m'\) sont bien définis et \(g>0\). L’égalité \(ax-b=mk\) s’écrit

Réciproquement, multiplier cette dernière égalité par \(g\) redonne la première. La congruence est donc équivalente à la congruence réduite modulo \(m'\), et non modulo \(m\).

Si un entier positif \(h\) divise \(a'\) et \(m'\), alors \(gh\) divise \(a\) et \(m\). Puisque \(g\) est leur plus grand diviseur commun positif, \(gh\le g\). En divisant par \(g>0\), on obtient \(h\le1\), donc \(h=1\). Ainsi \(\operatorname{PGCD}(a',m')=1\). Lorsque \(g<m\), on a \(m'>1\) et le critère d’existence d’un inverse s’applique.

Si \(g=m\), le module divise déjà \(a\) et, par hypothèse, \(b\) ; alors \(ax-b\) est divisible par \(m\) pour tout entier \(x\). Il n’est pas nécessaire d’introduire un « inverse modulo \(1\) ».

Corollaire : Combien de représentants solutions ?

Dans le deuxième cas du théorème, si \(r\) est une solution de la congruence réduite, toutes les solutions sont \(x=r+m'k\), \(k\in\mathbb{Z}\). Elles représentent exactement \(g\) classes différentes modulo \(m=gm'\). On peut prendre \(r,r+m',\ldots,r+(g-1)m'\) et réduire ces nombres modulo \(m\).

Démonstration : Ni omission, ni doublon

La résolution par inverse modulo \(m'\) donne toute la famille annoncée. Pour tout \(k\in\mathbb{Z}\), la division de \(k\) par \(g\) donne \(k=qg+t\) avec \(0\le t<g\). Ainsi \(r+m'k=r+tm'+qgm'=r+tm'+qm\), donc chaque solution est congrue à l’un des \(g\) représentants proposés.

Si deux d’entre eux sont congrus modulo \(m\), alors \(gm'\mid(t_1-t_2)m'\). En écrivant l’égalité et en divisant par \(m'>0\), on obtient \(g\mid(t_1-t_2)\). Mais \(|t_1-t_2|<g\) ; donc \(t_1=t_2\). Les \(g\) classes sont bien distinctes.

Exemple expliqué : Même coefficient, deux comportements

Résolvons d’abord \(6x\equiv9\;[15]\). On a \(g=\operatorname{PGCD}(6,15)=3\), et \(3\mid9\). L’égalité \(6x-9=15k\) devient, après division des deux membres par \(3\), \(2x-3=5k\). La congruence réduite est donc \(2x\equiv3\;[5]\).

Comme \(2\times3=6\equiv1\;[5]\), on multiplie par \(3\) : \(x\equiv9\equiv4\;[5]\). Les solutions sont \(x=4+5k\), \(k\in\mathbb{Z}\). Les représentants entre \(0\) et \(14\) sont \(4\), \(9\) et \(14\).

Contrôle :

Pour \(6x\equiv8\;[15]\), le même PGCD \(3\) ne divise pas \(8\). Il n’y a donc aucune solution. En effet, \(6x-15k=8\) imposerait que \(3\) divise \(8\), ce qui est impossible.

Exemple expliqué : Un coefficient négatif n’empêche pas l’inversion

Pour résoudre \(-4x\equiv7\;[15]\), on observe \(-4\equiv11\;[15]\) et \(11\times11=121=8\times15+1\). Ainsi \(11\) est un inverse de \(-4\) modulo \(15\). En multipliant par \(11\), on obtient \(x\equiv77\equiv2\;[15]\) : \(x=2+15k\), \(k\in\mathbb{Z}\).

Vérification avec les signes :

À toi : Ne pas décider du nombre de solutions à l’avance

Guidé.

Détermine un inverse de \(8\) modulo \(21\) par Euclide et Bézout, puis résous \(8x\equiv5\;[21]\).

Tentatives avant correction.

Résous dans \(\mathbb{Z}\) les deux congruences \(10x\equiv6\;[14]\) et \(10x\equiv3\;[14]\). Donne, lorsqu’ils existent, les représentants solutions entre \(0\) et \(13\).

Enfin, trouve un inverse de \(4\) modulo \(11\) en utilisant Fermat.

Justifie avec tes mots.

Pourquoi « le coefficient \(a\) n’est pas nul » ne suffit-il pas pour le simplifier modulo \(m\) ?

Critères :

donner le bon critère de PGCD et un coefficient non nul sans inverse, en démontrant cette absence.

Indices progressifs : Commencer par le PGCD

Pour le guidé : \(21=2\times8+5\), \(8=5+3\), \(5=3+2\), \(3=2+1\). Remonte jusqu’à écrire \(1\) avec seulement \(8\) et \(21\). Pour les tentatives, \(\operatorname{PGCD}(10,14)=2\) ; compare ce diviseur aux deux seconds membres. Pour Fermat, l’exposant utile est \(11-2=9\).

Correction expliquée : Les familles et leurs contrôles

Les divisions du guidé aboutissent au reste \(1\), puis au reste nul : le PGCD vaut \(1\). La remontée est

Pour \(10x\equiv6\;[14]\), on divise coefficient, second membre et module par le PGCD \(2\) : \(5x\equiv3\;[7]\). Comme \(5\times3=15=2\times7+1\), on multiplie par \(3\) et l’on obtient \(x\equiv9\equiv2\;[7]\). Les solutions sont \(x=2+7k\), et les représentants modulo \(14\) sont \(2\) et \(9\).

Contrôle :

\(10(2+7k)-6=20+70k-6=14+70k=14(1+5k)\).

Pour \(10x\equiv3\;[14]\), \(2\) ne divise pas \(3\) : aucune solution.

Enfin \(11\) est premier et ne divise pas \(4\), donc \(4^9\) est un inverse de \(4\) modulo \(11\). On calcule \(4^2=16\equiv5\), \(4^4\equiv25\equiv3\), \(4^8\equiv9\), puis \(4^9\equiv9\times4=36\equiv3\;[11]\). L’inverse proposé est \(3\) ; \(4\times3=12=11+1\) le confirme.

Une justification possible est : « Il faut \(\operatorname{PGCD}(a,m)=1\), et non seulement \(a\ne0\). Par exemple \(3\) est non nul, mais n’a pas d’inverse modulo \(9\) : une égalité \(3u-9k=1\) imposerait \(3\mid1\), impossible. »

Piège à éviter : Variation : conserver le mauvais module perd des solutions

À partir de \(6x\equiv9\;[15]\), écrire \(2x\equiv3\;[15]\) n’est pas une division licite. La bonne congruence réduite est modulo \(5\). Le nombre \(x=4\) montre concrètement la différence : \(6\times4=24\) est congru à \(9\) modulo \(15\), tandis que \(2\times4=8\) n’est pas congru à \(3\) modulo \(15\). Une transformation qui exclut une solution de départ n’est pas une équivalence.

Si tu t’es trompé : Si tu as simplifié un facteur non inversible

Erreur.

« \(2x\equiv2\;[6]\) implique \(x\equiv1\;[6]\). »

Rappel.

Le facteur \(2\) n’a pas d’inverse modulo \(6\). La réduction entière doit aussi modifier le module.

Plus simple, corrigé.

\(2x\equiv0\;[4]\) signifie \(2x=4k\). En divisant les deux membres par \(2\ne0\), on obtient \(x=2k\) : les solutions sont les entiers pairs. Le représentant \(2\) convient ; il aurait été perdu avec la fausse réponse \(x\equiv0\;[4]\).

Nouvel essai.

Résous \(3x\equiv6\;[12]\).

Correction.

Le PGCD vaut \(3\) et divise \(6\). L’égalité \(3x-6=12k\) devient \(x-2=4k\), donc \(x=2+4k\). Les représentants modulo \(12\) sont \(2\), \(6\) et \(10\). Le contrôle \(3(2+4k)-6=12k\) confirme toute la famille.

Retour.

L’erreur initiale se répare en écrivant \(2x-2=6k\), puis \(x-1=3k\) : \(x=1+3k\). Les deux représentants modulo \(6\) sont \(1\) et \(4\) ; le second manquait dans la réponse erronée. La bonne condition n’est pas « diviser par un nombre non nul », mais choisir entre inversion modulo \(m\) et réduction simultanée de l’égalité entière.

Pour réparer une erreur : Demain : deux modules identiques, deux décisions

Résous \(7x\equiv5\;[20]\) puis \(12x\equiv8\;[20]\). Pour chacune, donne la famille entière et les représentants entre \(0\) et \(19\).

Aide minimale.

Calcule d’abord le PGCD du coefficient et de \(20\).

Correction à masquer pendant la recherche.

Pour la première, le PGCD vaut \(1\) et \(7\times3=21=20+1\). En multipliant par \(3\), \(x\equiv15\;[20]\) ; les solutions sont \(x=15+20k\), avec le seul représentant \(15\).

Contrôle :

\(7(15+20k)-5=105+140k-5=20(5+7k)\).

Pour la seconde, le PGCD vaut \(4\), qui divise \(8\). On réduit à \(3x\equiv2\;[5]\). L’inverse de \(3\) modulo \(5\) est \(2\) car \(3\times2=6=5+1\) ; donc \(x\equiv4\;[5]\). Les solutions sont \(x=4+5k\), avec les représentants \(4\), \(9\), \(14\) et \(19\) modulo \(20\).

Contrôle :

\(12(4+5k)-8=48+60k-8=40+60k=20(2+3k)\).

À retenir : L’inverse et la résolution ne sont pas la même question

Un inverse de \(a\) modulo \(m\) existe exactement lorsque \(\operatorname{PGCD}(a,m)=1\). Bézout le construit pour tout module ; Fermat fournit \(a^{p-2}\) lorsque le module \(p\) est premier et ne divise pas \(a\).

Pour \(ax\equiv b\;[m]\), calculer \(g=\operatorname{PGCD}(a,m)\) : si \(g\nmid b\), aucune solution ; sinon, réduire simultanément coefficient, second membre et module par \(g\), puis résoudre la congruence réduite. Si le coefficient et le second membre sont déjà des multiples du module, tout entier convient. Toujours vérifier la famille entière dans la congruence initiale.

À retenir : Ce que tu vas apprendre

Étudier une famille en utilisant sa forme, distinguer une condition nécessaire d’un véritable certificat de primalité et démontrer les premiers résultats sur les nombres de Mersenne et de Fermat. Cette unité enrichit le chapitre ; elle n’est pas un préalable aux résultats du parcours principal.

Rappel utile : Le kit de cette unité

Un entier \(n\ge2\) est premier si ses seuls diviseurs positifs sont 1 et \(n\). Il est composé s’il s’écrit \(n=ab\) avec deux entiers \(a>1\) et \(b>1\). Ni 0 ni 1 n’est premier ou composé. Pour certifier la primalité d’un entier \(n\ge2\), il suffit de vérifier qu’aucun nombre premier \(p\le\sqrt n\) ne le divise : c’est le critère démontré dans le parcours principal, rappelé ici avec sa borne inclusive.

Les règles de puissances utilisées sont \(x^u x^v=x^{u+v}\) et \((x^u)^v=x^{uv}\) pour des exposants naturels. En revanche, \(x^{u^v}\) ne signifie pas \((x^u)^v\) : on calcule d’abord l’exposant \(u^v\). Pour \(x\ne0\), \(x^0=1\).

Écrire \(a\equiv b\;[m]\), pour un entier \(m>0\), signifie que \(m\) divise \(a-b\). On peut additionner et multiplier des congruences de même module, puis les élever à une puissance naturelle. La division euclidienne par 6 donne toujours \(n=6k+r\) avec \(k\in\mathbb{Z}\) et \(r\in\{0,1,2,3,4,5\}\).

Avant de commencer : Une forme prometteuse ne suffit pas

13 et 25 s’écrivent tous deux sous la forme \(6k+1\). Sont-ils tous deux premiers ? Peut-on conclure qu’un nombre est composé en l’écrivant simplement \(1\times n\) ?

Correction.

\(3^2<13<4^2\) : seuls les premiers 2 et 3 sont à tester. Or \(13=2\times6+1=3\times4+1\) ; 13 est premier. En revanche, \(25=5\times5\) est composé, bien que \(25=6\times4+1\).

Enfin \(1\times n\) n’établit pas la composition : le facteur 1 n’est pas strictement supérieur à 1. Si ce dernier point t’a arrêté, relis d’abord la définition de composé dans le kit.

Proposition : Deux restes possibles modulo 6

Tout nombre premier \(p\ge5\) s’écrit \(6k+1\) ou \(6k-1\), avec \(k\in\mathbb{N}\). La réciproque est fausse.

Démonstration : Éliminer les autres restes

Écrivons \(p=6q+r\), où \(0\le r<6\). Si \(r\) vaut 0, 2 ou 4, alors \(p\) est pair. Comme \(p\ge5\), ce serait un multiple de 2 différent de 2, donc un composé. Si \(r=3\), alors \(p=3(2q+1)\) ; \(p>3\) serait composé. Il reste \(r=1\) ou \(r=5\). Dans le premier cas \(p=6q+1\) ; dans le second \(p=6q+5=6(q+1)-1\). Les entiers \(q\) et \(q+1\) sont naturels ici.

Enfin \(25=6\times4+1\) et \(35=6\times6-1\) sont composés : la forme obtenue n’est donc pas suffisante pour être premier. Les exceptions 2 et 3 expliquent la condition \(p\ge5\).

Représentation intuitive : Un filtre, pas une attestation

Le test « reste 1 ou 5 modulo 6 » élimine les multiples de 2 ou de 3 supérieurs à ces deux nombres. Parmi les entiers qui restent, il y a des premiers et des composés : passer le filtre ne donne pas une attestation de primalité. Cette image représente une condition nécessaire, pas un théorème supplémentaire.

Formellement, « \(p\ge5\) premier » implique « \(p\equiv1\) ou \(5\;[6]\) » ; la flèche dans l’autre sens est interdite.

Exemple expliqué : Rendre visible une combinaison entière

Supposons \(a=6r+1\) et \(b=6s-1\), où \(r,s\in\mathbb{Z}\). On distribue les quatre produits, en conservant le signe de \(-1\) :

Méthode : Exploiter une forme avant de lancer des divisions

Indices.

Le nombre donné contient une puissance, une différence de carrés, ou une expression dépendant d’un entier.

Conditions.

On cherche à classer un entier au moins égal à 2.

Premier geste.

Repérer une factorisation ou un reste simple.

1. Écrire l’identité avec les données réelles, sans confondre les exposants : par exemple \(2^{uv}=(2^u)^v\).

2. Si un produit apparaît, vérifier que chaque facteur est entier et strictement supérieur à 1. Alors seulement conclure « composé ».

3. Si l’on obtient uniquement une condition nécessaire, ne pas conclure « premier ». Pour un petit entier, revenir aux divisions jusqu’à la racine.

Contrôle.

Redévelopper le produit ou le recomposer numériquement. Cette méthode cherche une preuve courte ; elle ne garantit pas qu’une factorisation immédiatement visible existe pour tout entier.

Définition : La famille \(2^n-1\)

Pour un entier \(n\ge1\), le nombre \(M_n=2^n-1\) est appelé nombre de Mersenne. Le mot « nombre » ne signifie pas « nombre premier ». Ainsi \(M_1=1\), \(M_2=3\), \(M_3=7\) et \(M_4=15\). Dans cette liste, 3 et 7 sont premiers ; 1 n’est pas premier, et \(15=3\times5\) est composé.

Lemme : Une différence de puissances

Pour tout entier \(v\ge1\) et tout réel \(x\),

Démonstration : Faire apparaître les termes qui s’annulent

Posons \(S=1+x+x^2+\cdots+x^{v-1}\). On distribue les deux termes de \(x-1\) sur toute la somme :

Pour \(v=1\), la somme vaut 1 et l’identité devient \(x-1=(x-1)\times1\).

Théorème : Une condition nécessaire sur l’exposant

Si \(M_n=2^n-1\) est premier, alors \(n\) est premier.

Démonstration : Raisonner par contraposée, avec le cas \(n=1\)

Si \(n=1\), \(M_n=1\) n’est pas premier. Supposons maintenant \(n\) composé. On peut écrire \(n=uv\) avec \(u\ge2\) et \(v\ge2\). En prenant \(x=2^u\) dans le lemme, on obtient

Le second contient au moins les deux termes \(1+2^u\) ; il est donc au moins \(1+4=5\). Ce sont deux entiers strictement supérieurs à 1 : \(M_n\) est composé. Ainsi, chaque fois que \(n\) n’est pas premier, \(M_n\) ne l’est pas non plus. C’est la contraposée du résultat annoncé.

Exemple expliqué : Ne pas calculer une grande puissance avant de réfléchir

Pour \(M_9\), l’exposant se factorise : \(9=3\times3\). En posant \(x=2^3=8\),

Piège à éviter : Un exposant premier ne suffit pas

11 est premier, mais

On a donc bien « \(M_n\) premier \(\Rightarrow n\) premier », mais pas « \(n\) premier \(\Rightarrow M_n\) premier ».

Exemple expliqué : Une factorisation qui révèle un composé

Pour \(n\in\mathbb{N}\) avec \(n\ge2\), on reconnaît une différence de carrés :

La condition sur \(n\) est utile : pour \(n=1\), on trouve \(2^2-1=3\), qui est premier, et le premier facteur vaut seulement 1.

Définition : Une autre famille

Pour \(n\in\mathbb{N}\), on appelle nombre de Fermat l’entier

Il ne faut pas remplacer \(2^{2^3}+1=257\) par \((2^2)^3+1=65\). Ces nombres et le petit théorème de Fermat sont deux objets différents, qui portent le nom du même mathématicien.

Lemme : Une somme de puissances d’exposant impair

Pour tout réel \(x\) et tout entier impair \(q=2t+1\) avec \(t\ge1\),

Démonstration : Contrôler les signes et la taille des facteurs

Notons \(T=x^{2t}-x^{2t-1}+\cdots+x^2-x+1\). En distribuant, \((x+1)T=xT+T\). Dans ces deux sommes,

Si \(x\ge2\), alors \(x+1\ge3\). Pour l’autre facteur, regroupons les termes avec leurs signes :

Théorème : Pourquoi chercher un exposant puissance de 2 ?

Soit \(m\ge1\) un entier. Si \(2^m+1\) est premier, alors \(m\) est une puissance de 2 : il existe \(s\in\mathbb{N}\) tel que \(m=2^s\).

Démonstration : Retirer tous les facteurs 2 de l’exposant

Divisons \(m\) par 2 tant qu’il est pair. Les quotients sont des entiers positifs strictement décroissants, donc cette opération s’arrête. On obtient \(m=2^s q\) avec \(s\in\mathbb{N}\) et \(q\) impair positif. Si \(q=1\), alors \(m=2^s\) comme annoncé.

Si \(q>1\), il est impair et vaut au moins 3. Posons \(x=2^{2^s}\) ; \(x\ge2\). Les règles de puissances donnent

Exemple expliqué : Un exposant qui n’est pas une puissance de 2

Dans \(2^{12}+1\), écrivons \(12=4\times3\) et posons \(x=2^4=16\). La formule pour un cube donne

Piège à éviter : Là encore, la condition n’est pas suffisante

L’exposant 32 est une puissance de 2, mais

À toi : Un essai guidé puis une recherche personnelle

Guidé.

Étudie \(A=2^6-1\) et \(B=2^6+1\).

Pour \(A\), écris \(2^6=(2^3)^2\). Pour \(B\), écris \(2^6=(2^2)^3\). Donne un produit et justifie les deux facteurs \(>1\).

Sans méthode annoncée.

Classe ensuite les trois nombres \(C=2^{10}-1\), \(D=2^{10}+1\) et \(E=2^5-1\). Ta conclusion doit être appuyée soit par un produit, soit par un test de primalité complet. Une condition sur l’exposant seule n’est pas une réponse.

Essaie réellement avant de lire les indices.

Indices progressifs : Choisis seulement l’aide nécessaire

Pour \(A\), utilise \(x^2-1=(x-1)(x+1)\) avec \(x=8\).

Pour \(B\), utilise \(x^3+1=(x+1)(x^2-x+1)\) avec \(x=4\).

Pour \(C\), partage l’exposant 10 en \(5\times2\).

Pour \(D\), partage-le en \(2\times5\) : une somme de puissances impaires apparaît. Pour \(E\), calcule d’abord sa valeur puis borne les diviseurs à tester.

Correction expliquée : Chaque conclusion possède son certificat

Guidé.

\(A=8^2-1=(8-1)(8+1)=7\times9=63\). Puis \(B=4^3+1=(4+1)(4^2-4+1)=5(16-4+1)=5\times13=65\). Les deux produits ont leurs facteurs \(>1\) : \(A\) et \(B\) sont composés. Le signe change le facteur du milieu ; recopier la même factorisation pour les deux nombres aurait été une erreur.

Recherche personnelle.

Pour \(C\),

Pour \(D\), \(2^{10}=(2^2)^5=4^5\), donc

Enfin \(E=32-1=31\). Comme \(5^2<31<6^2\), seuls 2, 3 et 5 doivent être testés :

À toi : Justifier avec tes propres mots

Pourquoi le fait que \(M_n\) soit composé ne permet-il pas de conclure que \(n\) est composé ? Et quel détail manque dans la phrase « j’ai factorisé, donc le nombre est composé » ?

Critères.

Ta réponse doit préciser le sens de la seule implication prouvée, fournir un contre-exemple et citer la taille des deux facteurs.

Réponse possible.

Le théorème donne \(M_n\) premier \(\Rightarrow n\) premier, pas son inverse ni une équivalence. \(M_{11}=23\times89\) est composé alors que 11 est premier. Pour prouver la composition par un produit, les deux facteurs doivent être des entiers strictement supérieurs à 1 ; \(n=1\times n\) ne suffit pas.

À toi : Changer une condition, pas seulement un nombre

Dans le théorème sur \(2^m+1\), peut-on remplacer \(m\ge1\) par \(m\ge0\) sans rien modifier ? Peut-on inclure 2 et 3 dans l’affirmation « un premier est de la forme \(6k\pm1\) » ?

Correction.

Pour \(m=0\), \(2^0+1=2\) est premier, mais 0 n’est pas une puissance de 2 : la conclusion échoue. D’autre part 2 et 3 ont pour restes 2 et 3 modulo 6, pas 1 ou 5. Les conditions des deux énoncés ont donc un rôle mathématique réel.

Si tu t’es trompé : Réparer une réciproque ou un facteur égal à 1

Première erreur :

« \(35=6\times6-1\), donc 35 est premier. »

Rappel :

une condition nécessaire permet d’éliminer certains nombres, pas de certifier tous ceux qui restent.

Exemple plus simple corrigé :

\(25=6\times4+1\), mais \(25=5\times5\) ; la forme ne suffit donc pas.

Nouvel essai :

\(49=6\times8+1\) est-il premier ?

Correction :

non, \(49=7\times7\) avec deux facteurs \(>1\).

Retour :

pour 35, écrire \(35=5\times7\), puis remplacer la fausse conclusion par « composé ». Applique la même prudence à \(M_{11}\).

Autre erreur :

« \(2^2-1=(2-1)(2+1)\), donc 3 est composé. » Le premier facteur vaut 1, pas un entier \(>1\). Pour comparer, \(12=3\times4\) est un vrai certificat de composition, alors que \(7=1\times7\) n’en est pas un.

Nouvel essai :

\(2^4-1=(4-1)(4+1)=3\times5\) : les deux facteurs dépassent 1, donc 15 est composé.

Retour :

\(2^2-1=3\) reste premier ; la condition \(n\ge2\) dans la factorisation de \(2^{2n}-1\) évitait précisément cette erreur.

Pour réparer une erreur : À refaire à distance, avant de relire

À la prochaine séance, classe \(2^8-1\) et \(2^8+1\) sans consulter les exemples. Écris pour chacun un certificat complet.

Aide minimale.

L’un se factorise comme une différence de carrés. Pour l’autre, \(16^2=256\) et \(17^2=289\) bornent la racine.

Correction.

\(2^8-1=16^2-1=(16-1)(16+1)=15\times17=255\), donc composé. Pour \(2^8+1=257\), on a \(16<\sqrt{257}<17\) ; les nombres premiers à tester sont 2, 3, 5, 7, 11 et 13. Les divisions sont

À retenir : Trois conditions nécessaires, trois prudences

Pour un premier \(p\ge5\), \(p=6k\pm1\) ; cela ne rend pas 25 ou 35 premiers. Si \(2^n-1\) est premier, son exposant \(n\) est premier ; \(n=11\) montre que la réciproque est fausse. Si \(m\ge1\) et \(2^m+1\) est premier, \(m\) est une puissance de 2 ; \(F_5\) montre que cette condition n’est pas suffisante.

À chaque factorisation, vérifier les signes, recomposer et contrôler que les deux facteurs sont des entiers \(>1\).

À retenir : Ce que tu vas apprendre

Utiliser le petit théorème de Fermat pour prouver qu’un entier est composé, comprendre pourquoi un test favorable ne certifie pas la primalité et construire deux preuves sur le nombre de Carmichael 561. Les programmes servent à vérifier des tests finis, pas à inventer une probabilité de primalité.

Rappel utile : Le kit de cette unité

Un entier \(n\ge2\) est premier si ses seuls diviseurs positifs sont 1 et \(n\). Il est composé s’il possède une écriture \(n=uv\) avec \(u,v>1\). Le nombre 1 est exclu de ces deux catégories.

Deux entiers \(a,n\) sont premiers entre eux si \(\operatorname{PGCD}(a,n)=1\). La congruence \(x\equiv y\;[n]\) signifie \(n\mid x-y\). Si \(x\equiv y\;[n]\), on peut élever les deux membres à une puissance naturelle. Le petit théorème de Fermat, démontré dans le parcours principal, affirme : si \(p\) est premier et \(p\nmid a\), alors \(a^{p-1}\equiv1\;[p]\). Sa forme sans restriction sur \(a\) est \(a^p\equiv a\;[p]\).

Le lemme d’Euclide, également établi dans le parcours principal, affirme qu’un nombre premier divisant un produit d’entiers divise au moins l’un de ses facteurs. Par contraposée, s’il ne divise aucun des deux facteurs, il ne divise pas leur produit.

Autre résultat antérieur utile : si \(u\) et \(v\) sont premiers entre eux et divisent tous deux \(T\), alors \(uv\mid T\). En effet, \(T=uk\) et \(v\mid uk\) ; le théorème de Gauss donne \(v\mid k\), donc \(k=v\ell\) et \(T=uv\ell\). On ne supprime jamais la condition de coprimalité.

Avant de commencer : Quelle est la portée d’un résultat de test ?

Un calcul exact donne \(2^{14}\equiv4\;[15]\). Un autre donne \(2^6\equiv1\;[7]\). Le premier calcul prouve-t-il que 15 n’est pas premier ? Le second, à lui seul, prouve-t-il que 7 est premier ?

Correction.

Si 15 était premier, comme \(1<2<15\), Fermat imposerait \(2^{14}\equiv1\;[15]\), contradiction : 15 est composé.

Pour 7, le résultat est compatible avec la primalité, mais la réciproque de Fermat n’a pas été démontrée et est fausse. 7 est effectivement premier : \(2^2<7<3^2\) et 2 ne le divise pas. Ce dernier argument est une preuve distincte. Si tu as utilisé une équivalence, reprends ce contraste avant de poursuivre.

Définition : Témoin de Fermat

Soient un entier \(n\ge3\) et un entier \(a\) tel que \(1<a<n\). Si \(a^{n-1}\not\equiv1\;[n]\), on dit que \(a\) est un témoin de Fermat de la composition de \(n\). Ici « témoin » désigne une donnée accompagnée d’un calcul vérifiable.

Critère : Un échec permet une conclusion certaine

Sous les conditions de la définition, si \(a^{n-1}\not\equiv1\;[n]\), alors \(n\) est composé.

Démonstration : La contraposée, dans le bon sens

Supposons \(n\) premier. L’inégalité \(1<a<n\) empêche \(n\) de diviser \(a\). Le petit théorème de Fermat donne donc \(a^{n-1}\equiv1\;[n]\). Ainsi, si la congruence n’est pas vérifiée, \(n\) ne peut pas être premier.

Puisque \(n\ge3\), il est composé. Le résultat ne prétend rien dans le cas où la congruence est vérifiée.

Exemple expliqué : Produire un témoin et contrôler sa conclusion

Pour \(n=15\) et \(a=2\), on a \(2^4=16\equiv1\;[15]\) et \(14=4\times3+2\). Par conséquent,

Le produit \(15=3\times5\) fournit un second contrôle, indépendant du test. Si l’on avait choisi la base 3, le PGCD \(\operatorname{PGCD}(3,15)=3\) aurait déjà fourni un facteur : calculer une grande puissance aurait été inutile.

Méthode : Lire correctement le résultat d’un test

Indices.

On souhaite examiner un entier \(n\ge3\), et calculer un reste de puissance est plus pratique que chercher tous ses diviseurs.

Premier geste.

Choisir une base entière \(a\) avec \(1<a<n\) et vérifier ces conditions.

1. Calculer d’abord \(d=\operatorname{PGCD}(a,n)\) si cela est simple. Si \(d>1\), alors \(1<d<n\) car \(d\le a<n\) : on tient déjà un diviseur non trivial.

2. Sinon, calculer exactement le reste \(r\) de \(a^{n-1}\) modulo \(n\), par cycles, carrés successifs ou calcul modulaire entier.

3. Si \(r\ne1\), conclure « composé » en citant la contraposée de Fermat. Si \(r=1\), écrire « test non concluant pour la primalité », jamais « premier ».

Contrôle.

Vérifier \(0\le r<n\) et le calcul de l’exposant. Un résultat approché ou une notation scientifique tronquée n’est pas un calcul de reste exact.

Définition : Pseudopremier pour une base

On dit ici qu’un entier composé \(n\ge3\) est pseudopremier pour la base \(a\) si \(\operatorname{PGCD}(a,n)=1\) et \(a^{n-1}\equiv1\;[n]\). Le mot contient « premier », mais la définition exige justement que \(n\) soit composé. Il décrit un échec de ce test à détecter la composition.

Proposition : Un contre-exemple explicite à la réciproque

Le nombre 341 est composé et pseudopremier pour la base 2.

Démonstration : Deux calculs, deux rôles différents

D’abord \(341=11\times31\) : les facteurs 11 et 31 sont \(>1\), donc 341 est composé. Comme 341 est impair, il est premier avec 2. Ensuite

Exemple expliqué : Une autre base peut détecter ce que la première a manqué

Pour la base 3 et le même entier 341, calculons sans écrire tous les chiffres de \(3^{340}\) :

Définition : Nombre de Carmichael

Un nombre de Carmichael est un entier composé \(n\ge3\) tel que, pour tout entier \(a\) premier avec \(n\),

Proposition : 561 : tous les tests copremiers peuvent réussir

L’entier \(561=3\times11\times17\) est composé. Pourtant, pour tout entier \(a\) premier avec 561,

Démonstration : Trois modules, puis leur produit

Fixons un entier \(a\) tel que \(\operatorname{PGCD}(a,561)=1\). Aucun des nombres premiers 3, 11, 17 ne divise \(a\) : sinon il serait un diviseur commun de \(a\) et 561 supérieur à 1. Le petit théorème de Fermat donne donc

Comme 3 et 11 sont premiers entre eux, leur produit 33 divise \(T\). Puis 33 et 17 sont premiers entre eux : 17 ne divise ni 3 ni 11, donc ne divise pas leur produit. On obtient \(33\times17=561\mid T\). C’est exactement \(a^{560}\equiv1\;[561]\). On a utilisé le résultat suivant : si deux entiers premiers entre eux divisent un entier \(T\), alors leur produit divise \(T\).

Sans la coprimalité des modules, ce passage ne serait pas justifié.

Corollaire : La forme sans restriction sur la base

Pour tout entier \(a\), y compris lorsque \(a\) n’est pas premier avec 561,

Démonstration : Ne pas utiliser une hypothèse absente

Fixons \(p\) égal à 3, 11 ou 17. Deux cas couvrent toutes les possibilités. Si \(p\mid a\), alors \(a\equiv0\;[p]\) et \(a^{561}\equiv0\equiv a\;[p]\). Si \(p\nmid a\), le petit théorème de Fermat s’applique modulo \(p\).

Comme \(p-1\) divise 560, on a \(a^{560}\equiv1\;[p]\) ; en multipliant les deux membres par \(a\), on obtient encore \(a^{561}\equiv a\;[p]\). Les nombres 3, 11, 17 divisent donc tous \(a^{561}-a\). Ils sont deux à deux premiers entre eux ; en regroupant d’abord 3 et 11, puis 33 et 17, leur produit 561 divise \(a^{561}-a\).

Le cas \(p\mid a\) n’a pas été traité par une division par \(a\) : une telle division aurait été illégitime modulo \(p\).

Remarque : Ce que l’exemple 561 dit, et ce qu’il ne dit pas

La proposition démontre que 561 est un nombre de Carmichael. Elle ne dit pas que \(a^{560}\equiv1\;[561]\) pour toutes les bases : la condition \(\operatorname{PGCD}(a,561)=1\) doit rester présente. Par exemple \(a=3\) est exclu ; modulo 3, \(3^{560}\equiv0\), donc cette puissance ne peut pas être congrue à 1 modulo 561.

En revanche, le corollaire a bien établi \(a^{561}\equiv a\;[561]\) pour tout entier \(a\), par une preuve qui traite aussi les multiples de 3, de 11 ou de 17.

Piège à éviter : Aucune probabilité de primalité n’a été démontrée

Un test de Fermat favorable ne signifie ni « premier à 75% » ni « presque sûrement premier ». Aucun choix aléatoire d’entier ni modèle probabiliste n’a été défini ici. Pour 561, toutes les bases premières avec 561 donnent la congruence favorable, alors que 561 est composé.

Le résultat exact de notre test est donc seulement : témoin trouvé, ou pas de témoin pour les bases examinées.

Algorithme : Tester une base, sans annoncer une fausse primalité

Les arguments \(n\) et \(a\) sont des entiers. Python calcule pow(a, e, n) comme le reste exact de \(a^e\) modulo \(n\), en arithmétique entière. On évite de fabriquer d’abord toute la grande puissance.

def temoin_fermat(n, a):
    if n < 3 or not (1 < a < n):
        raise ValueError("Conditions : n >= 3, 1 < a < n")
    r = pow(a, n - 1, n)
    return r != 1

Les restes correspondants sont respectivement 4, 1 et 56.

Algorithme : Vérifier la définition de Carmichael pour un petit entier

Ce programme est un contrôle exhaustif, destiné aux petits entiers. Il commence obligatoirement par exclure les nombres premiers.

from math import gcd

def est_premier(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d = d + 1
    return True

def est_carmichael(n):
    if n < 3 or est_premier(n):
        return False
    for a in range(2, n):
        if gcd(a, n) == 1:
            r = pow(a, n - 1, n)
            if r != 1:
                return False
    return True

Pourquoi le premier test est exact.

Si un entier \(n\ge2\) est composé, il a un diviseur au plus égal à \(\sqrt n\). La boucle teste tous les entiers \(d\) de 2 à cette borne inclusive. Dès qu’un reste est nul, elle renvoie False. Sinon, la liste des diviseurs possibles est épuisée : elle renvoie True. Le compteur \(d\) augmente de 1, donc la boucle se termine. Tester aussi des diviseurs composés est redondant mais ne rend pas la réponse fausse.

Pourquoi la seconde boucle suffit.

Le reste de tout entier \(a\) modulo \(n\) est un entier \(b\) entre 0 et \(n-1\). Les diviseurs communs à \(a,n\) sont exactement ceux de \(b,n\), car \(a=qn+b\). Les puissances de \(a\) et \(b\) ont le même reste modulo \(n\). Il suffit donc de tester les représentants copremiers entre 1 et \(n-1\).

Le représentant 0 n’est pas copremier à \(n\) ; le représentant 1 vérifie toujours \(1^{n-1}=1\). La boucle commence donc à 2 et s’arrête à \(n-1\), ce que réalise range(2, n).

Exemple expliqué : Lire les états avant et après la décision

Pour \(n=341\), est_premier trouve le diviseur 11 et renvoie False : le nombre n’est donc pas rejeté par le test initial de est_carmichael. La seconde boucle commence.

Le compteur \(a\) est fixé au début de chaque tour. Le PGCD est examiné avant le calcul de \(r\) ; si le PGCD n’est pas 1, aucune puissance n’est demandée pour cette base. Un seul \(r\ne1\) autorise un arrêt négatif. En revanche, un \(r=1\) n’autorise pas à renvoyer True dans la boucle : il reste des bases à tester. La réponse positive est placée après la boucle entière.

Pour \(n=561\), le programme exclut d’abord la primalité, puis toutes les bases copremières testées donnent 1 ; il renvoie True.

Pour \(n=7\), le premier test détecte un nombre premier et renvoie False sans lancer la boucle de Carmichael. Sans cette exclusion initiale, 7 serait classé à tort « Carmichael ».

Remarque : Portée et coût

L’algorithme examine une liste finie pouvant contenir jusqu’à \(n-2\) bases. Il est exact, mais il n’est pas destiné à construire de très grands nombres premiers. Obtenir un résultat sur un entier ne prouve pas une affirmation pour toute une famille ; les démonstrations précédentes avaient justement cette autre fonction.

À toi : Un témoin, puis un nombre trompeur

Guidé.

Étudie le test de Fermat en base 2 pour \(n=65\). Calcule d’abord le reste de \(2^6\), puis de \(2^{12}\), modulo 65. Utilise ensuite \(64=12\times5+4\). Que peux-tu conclure ?

Tentative personnelle.

On donne \(1105=5\times13\times17\). Le fait que \(2^{1104}\equiv1\;[1105]\) pourrait-il prouver sa primalité ? Ce nombre est-il un nombre de Carmichael ? Justifie la réponse pour toutes les bases copremières, pas seulement pour 2.

Prépare enfin ce que devrait renvoyer est_carmichael(1105).

Indices progressifs : Deux degrés d’aide

Pour 65, \(2^6=64\equiv-1\;[65]\) : commence par élever au carré.

Pour 1105, calcule les trois quotients de 1104 par 4, 12 et 16. Vérifie ensuite les hypothèses de Fermat modulo 5, 13 et 17 et explique pourquoi tu peux regrouper ces trois modules.

Correction expliquée : Le test et la définition ne répondent pas à la même question

Guidé.

\(2^6\equiv-1\;[65]\) donne \(2^{12}=(2^6)^2\equiv(-1)^2=1\;[65]\). Comme \(64=12\times5+4\),

Tentative personnelle.

Le produit donné montre déjà que 1105 est composé ; un test favorable ne peut pas annuler cette preuve. Fixons \(a\) tel que \(\operatorname{PGCD}(a,1105)=1\). Aucun des premiers 5, 13 et 17 ne divise \(a\), donc

Puis 17 est premier avec 65, car 17 ne divise ni 5 ni 13 : le produit \(65\times17=1105\) divise \(a^{1104}-1\). La définition est vérifiée pour toute base copremière ; 1105 est un nombre de Carmichael et le programme doit renvoyer True. En particulier, la base 2 est copremière à 1105, qui est impair : la congruence donnée au départ est donc bien cohérente avec la preuve.

À toi : Une justification personnelle avec critères

Explique pourquoi la condition « composé » doit apparaître dans la définition de Carmichael et dans le programme. Explique aussi pourquoi on peut arrêter la boucle dès qu’un seul test échoue, mais pas dès qu’un seul test réussit.

Critères.

Ta réponse doit utiliser le théorème de Fermat, le mot « toutes » et un exemple où une base favorable est trompeuse.

Réponse possible.

Un nombre premier vérifie déjà les congruences pour toutes ses bases non multiples, donc il faut l’exclure explicitement de la définition de Carmichael. Pour un composé, la définition exige la réussite de toutes les bases copremières. Un seul échec réfute cette exigence ; un seul succès ne la prouve pas. 341 passe le test en base 2 mais échoue en base 3 : retourner True dès la base 2 aurait donné une réponse fausse.

À toi : Modifier la base et le domaine

Un élève trouve \(3^{560}\not\equiv1\;[561]\) et affirme que cela réfute le fait que 561 soit un nombre de Carmichael. A-t-il raison ? La congruence \(3^{561}\equiv3\;[561]\) peut-elle rester vraie ?

Correction.

\(\operatorname{PGCD}(3,561)=3\), donc la base 3 n’est pas dans le domaine « bases copremières ». L’échec ne contredit pas la définition. La forme \(a^{561}\equiv a\) a été prouvée pour tous les entiers \(a\), en séparant les cas pour chaque facteur premier : elle reste donc vraie pour \(a=3\). Les deux puissances n’ont ni le même exposant ni la même conclusion attendue.

Si tu t’es trompé : Quand une réussite de test a été prise pour une preuve

Première erreur :

« \(2^{340}\equiv1\;[341]\), donc 341 est premier. »

Rappel :

on a prouvé l’implication « premier \(\Rightarrow\) congruence », pas sa réciproque.

Exemple simple corrigé :

pour 9, \(2^8=256=9\times28+4\). Comme 4 n’est pas 1, la base 2 prouve que 9 est composé. Le test sert ici à réfuter, pas à confirmer.

Nouvel essai :

étudie 25 en base 2 avec \(2^{10}=1024=25\times41-1\).

Correction :

\(2^{10}\equiv-1\;[25]\), donc \(2^{20}\equiv1\;[25]\). Ainsi \(2^{24}=2^{20}\times2^4\equiv16\not\equiv1\;[25]\) : 25 est composé.

Retour :

pour 341, le reste 1 ne donne pas cette réfutation. Il faut écrire « test non concluant en base 2 », puis utiliser \(341=11\times31\) ou le témoin 3 pour prouver la composition.

Pour réparer une erreur : À reprendre plus tard sans relire les exemples

On donne \(1729=7\times13\times19\). À la prochaine séance, décide si 1729 est un nombre de Carmichael et justifie chaque passage. Que se passe-t-il si l’on choisit la base 7 ?

Aide.

Comparer 1728 aux nombres 6, 12 et 18 ; ne pas oublier le rôle du PGCD de la base avec 1729.

Correction.

Le produit donné a des facteurs \(>1\), donc 1729 est composé. Si \(\operatorname{PGCD}(a,1729)=1\), aucun des premiers 7, 13 et 19 ne divise \(a\). Fermat donne \(a^6\equiv1\;[7]\), \(a^{12}\equiv1\;[13]\) et \(a^{18}\equiv1\;[19]\). Or

1729 est ainsi un nombre de Carmichael. Pour la base 7, \(\operatorname{PGCD}(7,1729)=7\ne1\) : la définition n’exige pas la réussite. Effectivement \(7^{1728}\equiv0\;[7]\) ne peut pas être congru à 1 modulo 1729, puisque 7 divise 1729.

À retenir : Un résultat négatif fort, un résultat favorable limité

Avec \(n\ge3\) et \(1<a<n\), un reste différent de 1 dans le test de Fermat prouve la composition. Un reste égal à 1 ne prouve pas la primalité. 341 est trompeur en base 2, mais pas en base 3. 561 est composé et trompe toutes les bases premières avec lui : c’est un nombre de Carmichael. La définition et le programme doivent exclure explicitement les nombres premiers. Aucune probabilité de primalité n’a été déduite de ces tests.

À retenir : Ce que tu vas apprendre

Fabriquer une petite paire de clés, chiffrer et déchiffrer un entier, puis expliquer pourquoi le message revient même s’il possède un facteur commun avec le module. Ce problème réinvestit Fermat, Bézout et Gauss ; il ne constitue pas un protocole de sécurité à utiliser en pratique.

Rappel utile : Le kit de cette unité

Pour \(n>0\), \(a\equiv b\;[n]\) signifie \(n\mid(a-b)\). On peut additionner, multiplier et élever à une même puissance entière positive des congruences de même module. Chaque entier possède un unique reste dans \(\{0,\ldots,n-1\}\).

Bézout, résultat antérieur.

Si \(\operatorname{PGCD}(e,t)=1\), il existe des entiers \(u,v\) tels que \(eu+tv=1\). Le reste \(d\) de \(u\) modulo \(t\) vérifie alors \(ed\equiv1\;[t]\).

Fermat, résultat antérieur.

Si \(p\) est premier et \(p\nmid a\), alors \(a^{p-1}\equiv1\;[p]\). Si \(p\mid a\), c’est \(a^s\equiv0\;[p]\) pour \(s\ge1\) qui s’applique.

Gauss, résultat antérieur.

Si \(q\mid ph\) et \(\operatorname{PGCD}(p,q)=1\), alors \(q\mid h\). Deux nombres premiers distincts sont premiers entre eux. Ces faits seront utilisés avec leurs conditions, et non avec le seul mot « premier ».

Avant de commencer : Message ou reste ?

Les entiers 42 et 229 représentent-ils le même reste modulo 187 ? Le reste est-il 42 ou 229 ? Peut-on demander un inverse de 5 modulo 160 ?

Correction.

\(229=187+42\), donc \(229\equiv42\;[187]\). Comme \(0\le42<187\), le reste est 42 ; 229 n’est pas dans l’intervalle des restes. Ensuite, \(\operatorname{PGCD}(5,160)=5\ne1\) : un inverse de 5 n’existe pas modulo 160. En effet, \(5d=160k+1\) donnerait \(5(d-32k)=1\), impossible pour des entiers \(d,k\).

Si ces conclusions te surprennent, reprends d’abord la définition de congruence et la condition de Bézout dans le kit.

Définition : La maquette RSA

On choisit deux nombres premiers distincts \(p,q\) et on pose

La clé publique est \((n,e)\) : elle permet de chiffrer. La clé privée est \((n,d)\) : elle permet de déchiffrer. Dans cette présentation, les facteurs \(p,q\) et l’entier \(t\) ne sont pas divulgués avec la clé publique.

Un message est ici un entier \(m\) tel que \(0\le m<n\). Son chiffré \(c\) est le reste de \(m^e\) modulo \(n\). Pour le déchiffrer, on calcule le reste de \(c^d\) modulo \(n\). La proposition démontrée ci-dessous expliquera pourquoi on retrouve \(m\).

Représentation intuitive : Un cadenas accessible à tous

La clé publique joue le rôle d’un cadenas que chacun peut fermer : elle fournit l’opération qui transforme un message en chiffré. La clé privée joue le rôle du moyen de l’ouvrir : elle fournit une opération qui revient au message. Cette image distingue les deux rôles, mais ne démontre ni le retour arithmétique ni la sécurité.

Dans nos petits exemples, tout le monde peut factoriser \(n\) : le « cadenas » n’a aucune résistance réelle.

Méthode : Construire une clé et la contrôler

Quand ?

On fournit deux premiers distincts et un exposant de chiffrement.

Premier geste :

calculer séparément \(n=pq\) et \(t=(p-1)(q-1)\) ; ils n’ont pas le même rôle.

1. Vérifier \(\operatorname{PGCD}(e,t)=1\) avec Euclide.

2. Remonter les divisions pour obtenir \(eu+tv=1\).

3. Prendre pour \(d\) le reste positif de \(u\) modulo \(t\).

4. Contrôler réellement le produit : \(ed=1+kt\) pour un entier \(k\).

On cherche donc l’inverse de \(e\) modulo \(t\), pas modulo \(n\). Les puissances des messages, elles, sont calculées modulo \(n\).

Exemple expliqué : Une paire de clés calculée à la main

Prenons \(p=11\) et \(q=17\). Ils sont premiers : les seuls premiers à tester jusqu’à leur racine carrée sont 2 et 3, qui ne divisent ni 11 ni 17. Ils sont distincts. Alors

En remontant, puis en distribuant le signe « moins »,

Contrôle :

\(7\times23=161=1+160\). La clé publique est \((187,7)\) et la clé privée \((187,23)\).

Méthode : Calculer sans développer une puissance gigantesque

Pour une puissance modulo \(n\), on calcule successivement les carrés et on remplace chaque résultat par son reste. On décompose ensuite l’exposant en somme de puissances de 2 et on multiplie seulement les restes nécessaires. À chaque ligne, le contrôle est une division \(A=nq+r\) avec \(0\le r<n\).

Exemple expliqué : Chiffrer 42 avec la clé publique

Le message \(m=42\) appartient bien à \(\{0,\ldots,186\}\). Pour calculer \(42^7\), on utilise \(7=4+2+1\) :

Exemple expliqué : Déchiffrer 15 avec la clé privée

On calcule \(15^{23}\) modulo 187. Voici les carrés utiles :

Proposition : Le retour du message

Avec les conditions de la définition, pour tout entier \(m\) tel que \(0\le m<n\), le reste de \((m^e)^d\) modulo \(n\) est \(m\). Il n’est pas nécessaire que \(m\) soit premier avec \(n\).

Démonstration : Pourquoi le déchiffrement fonctionne pour chaque message

Soient \(p\) et \(q\) deux nombres premiers distincts, \(n=pq\) et \(t=(p-1)(q-1)\). Les entiers positifs \(e,d\) vérifient \(ed=1+kt\) pour un entier \(k\ge0\). Soit \(m\) un entier avec \(0\le m<n\).

Première étape : travailler modulo \(p\), en séparant deux cas.

Si \(p\mid m\), alors \(m\equiv0\;[p]\) et, puisque \(ed\ge1\), \(m^{ed}\equiv0\equiv m\;[p]\). On n’a pas utilisé \(m^{p-1}\equiv1\), qui serait faux dans ce cas.

Si \(p\nmid m\), le petit théorème de Fermat donne \(m^{p-1}\equiv1\;[p]\). On transforme l’exposant :

Deuxième étape : travailler modulo \(q\).

Si \(q\mid m\), alors \(m^{ed}\equiv0\equiv m\;[q]\). Si \(q\nmid m\), Fermat donne \(m^{q-1}\equiv1\;[q]\) et

Troisième étape : réunir les deux informations.

Posons \(X=m^{ed}-m\). Comme \(p\mid X\), il existe un entier \(h\) tel que \(X=ph\). Or \(q\mid X\), donc \(q\mid ph\). Les nombres premiers \(p\) et \(q\) étant distincts, ils sont premiers entre eux ; le théorème de Gauss donne \(q\mid h\). Écrivons \(h=qj\). Alors \(X=pqj=nj\), donc \(m^{ed}\equiv m\;[n]\).

Si le chiffré \(c\) est le reste de \(m^e\) modulo \(n\), alors \(c\equiv m^e\;[n]\). En élevant à la puissance \(d\), \(c^d\equiv(m^e)^d=m^{ed}\equiv m\;[n]\). Le reste de \(c^d\) appartient à \(\{0,1,\ldots,n-1\}\) ; \(m\) aussi. L’unicité du reste de la division euclidienne montre que ce reste est exactement le message \(m\), et pas seulement un entier qui lui est congru.

Exemple expliqué : Un message divisible par 11

Prenons \(m=22\) avec les mêmes clés. Il n’est pas premier avec 187, puisque 11 divise les deux nombres. Pourtant :

À toi : Essai guidé : changer de message, garder les clés

Avec \((n,e,d)=(187,7,23)\), prends \(m=5\).

1. Calcule les restes de \(5^2\) et de \(5^4\), puis utilise \(7=4+2+1\).

2. Le chiffré trouvé doit être 146. Calcule les restes de \(146^2,146^4,146^8,146^{16}\).

3. Avec \(23=16+4+2+1\), vérifie le retour à 5.

Écris au moins une égalité de division pour chaque réduction. Les indices et la correction restent disponibles après ton essai.

À toi : Tentative sans les restes intermédiaires

Le message est maintenant \(m=11\), avec les mêmes clés. Trouve le chiffré puis déchiffre-le par carrés successifs.

Enfin, explique pourquoi la preuve du retour reste valable alors que 11 n’a pas d’inverse modulo 187. Ne consulte la correction qu’après avoir écrit ta propre chaîne de calculs.

Indices progressifs : Pour reprendre sans dévoiler toute la solution

Pour \(m=5\), \(5^4\equiv64\;[187]\) ; pour le retour, \(146^2\equiv185\equiv-2\;[187]\) permet de vérifier les carrés suivants.

Pour \(m=11\), commence par \(11^2=121\), puis réduis \(121^2\). La preuve générale n’inverse jamais le message : elle distingue les cas où chacun des deux premiers le divise ou ne le divise pas.

Correction expliquée : Essai guidé et tentative

Avec \(m=5\).

On a \(5^2=25\) et \(5^4=625=187\times3+64\). Comme \(64\times25=1600=187\times8+104\) puis \(104\times5=520=187\times2+146\), le chiffré est 146.

Pour déchiffrer :

Avec \(m=11\).

\(11^2=121\) et \(11^4=14641=187\times78+55\). Puis \(55\times121=6655=187\times35+110\) et \(110\times11=1210=187\times6+88\) : le chiffré est 88. Les carrés nécessaires au retour sont :

À toi : Justifier personnellement

En cinq à huit lignes, explique pourquoi « le message n’est pas premier avec \(n\) » ne suffit pas à invalider le retour RSA de cette unité. Puis explique pourquoi connaître le retour modulo \(p\) et modulo \(q\) permet de conclure modulo \(pq\).

Critères d’une réponse complète :

les deux cas pour chaque premier, la condition de Fermat, le rôle de la distinction \(p\ne q\), et le passage des congruences à une divisibilité commune doivent apparaître.

Réponse possible.

Si \(p\mid m\), les deux nombres \(m^{ed}\) et \(m\) valent 0 modulo \(p\) ; sinon Fermat donne l’égalité des restes. Le même raisonnement vaut modulo \(q\). Leur différence \(X\) est donc divisible par \(p\) et \(q\). Écrivant \(X=ph\), Gauss donne \(q\mid h\) car \(\operatorname{PGCD}(p,q)=1\), donc \(pq\mid X\). L’intervalle des restes fournit ensuite le message exact.

À toi : Variation : peut-on prendre deux fois le même premier ?

Une personne prend \(p=q=11\), donc \(n=121\) et \(t=100\), puis \(e=3,d=67\). Le produit \(ed=201=1+2\times100\) est correct. Le message \(m=11\) revient-il après chiffrement et déchiffrement ?

Indice :

réduis \(11^3\) modulo 121 avant tout autre calcul.

Correction.

\(11^3=1331=121\times11\), donc le chiffré vaut 0. Le reste de \(0^{67}\) vaut encore 0, et non 11. La construction demandait deux premiers distincts. Ici, savoir que 11 divise une différence deux fois ne montre pas que \(11^2\) la divise.

Ce contre-exemple explique l’utilité de la condition ; il ne contredit pas la proposition, dont une hypothèse a été supprimée.

Si tu t’es trompé : Une base nulle n’a pas une puissance égale à 1

Première erreur possible :

écrire \(22^{10}\equiv1\;[11]\) en invoquant seulement « 11 est premier ».

Rappel ciblé :

Fermat sous cette forme exige \(11\nmid22\), condition fausse ici.

Exemple plus simple corrigé.

Modulo 5, \(10\equiv0\), donc \(10^4\equiv0\), et non 1. Pour montrer \(10^{13}\equiv10\;[5]\), il suffit de constater que les deux côtés sont congrus à 0.

Nouvel essai.

Sans calculer une grande puissance, prouve que \(55^{161}\equiv55\;[187]\).

Correction.

Modulo 11, \(55\equiv0\), donc \(55^{161}\equiv0\equiv55\). Modulo 17, \(55=3\times17+4\), donc \(55\equiv4\) et \(17\nmid4\) ; Fermat donne \(4^{16}\equiv1\). Comme \(161=1+10\times16\), \(55^{161}\equiv4(4^{16})^{10}\equiv4\equiv55\;[17]\). Les nombres 11 et 17 étant premiers entre eux, leur produit 187 divise \(55^{161}-55\) par Gauss.

Retour :

reprends la preuve générale et entoure les deux phrases qui traitent une base divisible par le premier. Si tu peux les expliquer, refais la tentative \(m=11\) sans regarder les restes fournis.

Pour réparer une erreur : Une autre petite clé, plus tard et avant relecture

Avec \(p=3,q=11\), prends \(e=3\). Calcule \(n,t\), vérifie que \(d=7\) convient, puis chiffre et déchiffre \(m=6\). Explique en une phrase pourquoi le fait que \(3\mid6\) n’est pas un obstacle.

Aide après recherche.

\(n=33\), \(t=20\) ; utilise \(7=4+2+1\) au retour.

Correction.

\(n=3\times11=33\) et \(t=2\times10=20\). \(3\times7=21=1+20\) : la clé convient. \(6^2=36\equiv3\;[33]\), donc \(6^3\equiv3\times6=18\) : \(c=18\). Puis \(18^2=324=33\times9+27\) et \(18^4\equiv27^2=729=33\times22+3\;[33]\).

Pour \(18^7\), \(3\times27=81=33\times2+15\) puis \(15\times18=270=33\times8+6\) : on retrouve 6. Modulo 3, le cas nul assure le retour ; modulo 11, le cas non nul utilise Fermat. Si tu avais oublié un carré, refais la décomposition de 7 avant de reprendre.

À retenir : Les conditions sont aussi importantes que les puissances

Dans cette maquette : \(p,q\) premiers distincts, \(n=pq\), \(t=(p-1)(q-1)\), \(\operatorname{PGCD}(e,t)=1\) et \(ed\equiv1\;[t]\). On chiffre avec \(m^e\ [n]\) et on déchiffre avec \(c^d\ [n]\). Le retour est prouvé pour tous les messages \(0\le m<n\).

Le calcul de la clé utilise le module \(t\) ; le calcul des messages utilise \(n\).

Les paramètres minuscules et l’application directe aux messages servent à comprendre les mathématiques. Ils ne protègent aucune donnée réelle ; la sécurité pratique exige d’autres précautions qui ne sont pas étudiées ici.

À retenir : Ce que tu vas apprendre

Découvrir un autre critère exact de primalité, puis utiliser la divisibilité pour limiter une recherche de racines rationnelles. Wilson est un complément non exigible ; les racines rationnelles sont un problème possible d’approfondissement. Aucun des deux parcours n’est nécessaire pour utiliser le noyau du chapitre.

Rappel utile : Le kit local pour Wilson

Pour \(n\ge1\), la factorielle \(n!\) est le produit \(1\times2\times\cdots\times n\) ; on convient que \(0!=1\). Par exemple, \(4!=1\times2\times3\times4=24\).

Dire \(a\equiv b\;[n]\) signifie \(n\mid(a-b)\), avec \(n>0\). Un inverse de \(a\) modulo \(n\) est un entier \(b\) tel que \(ab\equiv1\;[n]\) ; il ne s’agit pas du nombre réel \(1/a\).

Résultats antérieurs disponibles ici.

Bézout donne un inverse modulo \(n\) lorsque \(\operatorname{PGCD}(a,n)=1\). Si un premier \(p\) divise un produit \(uv\), il divise \(u\) ou \(v\) (lemme d’Euclide). Tout entier composé possède un diviseur premier strictement compris entre 1 et lui-même.

Avant de commencer : Trouver un partenaire

Modulo 7, quel entier de la liste \(1,2,\ldots,6\) peut être l’inverse de 3 ? L’entier 6 est-il son propre inverse ?

Correction.

\(3\times5=15=2\times7+1\), donc 5 est l’inverse cherché. \(6^2=36=5\times7+1\), donc 6 est son propre inverse. Si tu avais choisi \(1/3\), reprends la définition : on cherche un entier dont le produit avec 3 donne un reste de 1, pas un quotient réel.

Théorème : Critère de Wilson — complément

Pour tout entier \(n\ge2\),

Démonstration : Apparier chaque reste avec son inverse

Pour \(p=2\), on vérifie directement \((p-1)!=1\equiv-1\;[2]\). Supposons maintenant \(p\) premier impair.

Pour chaque entier \(a\) compris entre 1 et \(p-1\), on a \(\operatorname{PGCD}(a,p)=1\). Bézout fournit des entiers \(u,v\) tels que \(au+pv=1\), donc \(au\equiv1\;[p]\). Remplaçons \(u\) par son reste \(b\) modulo \(p\) : \(ab\equiv1\;[p]\). Ce reste n’est pas nul, sinon le produit serait congru à 0. Ainsi \(1\le b\le p-1\) : l’inverse appartient à la même liste.

Cet inverse est unique dans la liste. En effet, si \(ab\equiv ab'\equiv1 \;[p]\), alors \(p\mid a(b-b')\). Comme \(p\nmid a\), le lemme d’Euclide entraîne \(p\mid(b-b')\). Mais \(|b-b'|<p\) ; le seul multiple de \(p\) dans cet intervalle est 0, donc \(b=b'\). De plus, \(ab\equiv1\) donne aussi \(ba\equiv1\) : le partenaire de \(b\) est bien \(a\). Les termes se répartissent donc en paires disjointes, sauf ceux qui sont leur propre inverse.

Cherchons précisément ces exceptions. Être son propre inverse signifie \(a^2\equiv1\;[p]\), soit \(p\mid(a^2-1)\). La factorisation

Tous les autres termes se groupent donc une seule fois en paires distinctes dont le produit vaut 1 modulo \(p\). En multipliant ces paires et les deux termes restants, on obtient

Démonstration : Sens réciproque : éliminer tous les composés

Supposons \(n\ge2\) et \(n\mid\bigl((n-1)!+1\bigr)\). Si \(n\) était composé, il posséderait un diviseur premier \(r\) avec \(2\le r\le n-1\). Le facteur \(r\) figure donc dans le produit \((n-1)!\) ; ainsi \(r\mid(n-1)!\).

Comme \(r\mid n\) et \(n\mid\bigl((n-1)!+1\bigr)\), on a aussi \(r\mid\bigl((n-1)!+1\bigr)\). En soustrayant ces deux multiples de \(r\), on obtiendrait \(r\mid\bigl((n-1)!+1-(n-1)!\bigr)=1\), impossible puisque \(r\ge2\). Donc \(n\) est premier.

Ce raisonnement couvre aussi \(n=4\) : on prend \(r=2\). Numériquement, \(3!=6\equiv2\;[4]\), et non \(-1\equiv3\;[4]\). On n’a jamais affirmé que \((n-1)!\) était divisible par tout composé \(n\), affirmation qui serait fausse précisément pour 4.

Exemple expliqué : Voir toutes les paires, sans doublon

Modulo 7, les six facteurs de \(6!\) se répartissent ainsi :

Cette dernière divisibilité, avec le sens réciproque du critère, constitue aussi une preuve de primalité de 7.

Méthode : Tester avec Wilson, et comprendre le coût

Condition :

l’entier \(n\) à tester est au moins égal à 2.

Premier geste :

calculer \((n-1)!\) modulo \(n\), pas \(n!\). On part du reste 1 ; on multiplie successivement par \(1,2,\ldots,n-1\) en réduisant après chaque multiplication. Si le reste final vaut \(n-1\), le critère conclut « premier » ; sinon il conclut « composé ».

Par exemple, pour \(n=5\), les restes successifs sont \(1\), \(2\), \(6\equiv1\), puis \(4\). Le dernier vaut \(5-1\) : 5 est premier.

Pour \(n=6\), le produit \(5!=120\) a pour reste 0, différent de \(6-1\) : 6 est composé.

Ce critère est exact, mais la méthode directe nécessite jusqu’à \(n-1\) multiplications. Les divisions jusqu’à la racine carrée sont souvent beaucoup plus simples à la main. « Exact » ne signifie donc pas « rapide ».

À toi : Essai guidé : une certification par paires

Sans calculer le grand entier \(10!\), vérifie que 11 est premier à l’aide de Wilson. Commence par vérifier les paires \((2,6)\), \((3,4)\), \((5,9)\), \((7,8)\) modulo 11. Quels sont les deux facteurs de \(10!\) qui restent ?

Vérifie que la liste est complète avant de multiplier les restes.

À toi : Tentative : comparer deux conclusions

Utilise Wilson pour décider si 9 et 5 sont premiers.

Pour 9, cherche dans \(8!\) deux facteurs dont le produit est divisible par 9. Puis commente l’affirmation : « Si le reste de \((n-1)!\) n’est pas nul, alors \(n\) est premier. » Cherche toi-même un contre-exemple avant de lire.

Indices progressifs : Après une première recherche

Pour 11, les deux termes laissés seuls sont 1 et 10.

Pour 9, pense aux facteurs 3 et 6 du produit \(8!\). Pour la dernière affirmation, examine \(n=4\) et compare le reste obtenu au reste précis demandé par Wilson.

Correction expliquée : Ce que le reste doit réellement montrer

Guidé.

\(2\times6=12\equiv1\;[11]\), \(3\times4=12\equiv1\;[11]\), \(5\times9=45=4\times11+1\) et \(7\times8=56=5\times11+1\). Avec les facteurs 1 et 10, on a utilisé exactement \(1,2,\ldots,10\). Donc \(10!\equiv1\times10\times1^4\equiv10\equiv-1\;[11]\).

La réciproque de Wilson prouve que 11 est premier.

Tentative.

Dans \(8!\), le produit des facteurs 3 et 6 vaut \(18=2\times9\). Tous les autres facteurs étant entiers, \(9\mid8!\). Le reste est donc 0, différent de \(-1\equiv8\;[9]\) : 9 est composé.

Pour 5, \(4!=24=5\times4+4\), donc \(4!\equiv-1\;[5]\) : 5 est premier.

Enfin, \(3!=6\equiv2\;[4]\) est non nul, alors que 4 est composé. Le critère demande le reste \(n-1\), pas seulement un reste non nul.

À toi : Justifier l’appariement

Explique pourquoi, modulo un premier impair \(p\), on ne peut pas « apparier au hasard » les facteurs de \((p-1)!\). Ta réponse doit préciser l’existence et l’unicité du partenaire, la symétrie du partenariat, puis les seuls termes qui restent seuls.

Réponse possible et critères.

Bézout assure un inverse parmi les restes \(1,\ldots,p-1\). Le lemme d’Euclide prouve son unicité. Si \(ab\equiv1\), alors \(ba\equiv1\) : les partenaires se retrouvent mutuellement, sans double compte. Un terme reste seul exactement s’il vérifie \(a^2\equiv1\), soit \(p\mid(a-1)(a+1)\).

Le caractère premier de \(p\) impose \(a=1\) ou \(a=p-1\) dans la liste. Oublier l’un de ces quatre points laisse un trou dans la justification.

À toi : Variation : retirer l’hypothèse « premier »

Modulo 8, vérifie que 3 est son propre inverse. Est-il congru à 1 ou à \(-1\) modulo 8 ? Le raisonnement sur les deux seuls termes isolés fonctionne-t-il encore ?

Correction.

\(3^2=9=8+1\), mais 3 n’est congru ni à 1 ni à 7, le reste de \(-1\). De plus, 2 n’a aucun inverse modulo 8, car un produit \(2b\) reste pair alors qu’un entier congru à 1 modulo 8 est impair. L’existence de tous les partenaires et la liste des points fixes ont donc toutes deux besoin de l’hypothèse appropriée ; on ne peut pas recopier la preuve de Wilson avec un module composé quelconque.

Si tu t’es trompé : Une factorielle de trop

Erreur :

« \(n!\) est divisible par \(n\), donc \(n\) est premier. »

Rappel :

\(n\) est déjà l’un des facteurs de \(n!\) ; cette divisibilité est vraie pour tout \(n\ge1\) et ne distingue rien.

Exemple plus simple corrigé.

\(4!=24\) est divisible par 4, mais \(4=2\times2\) est composé. Wilson demande de tester \((4-1)!+1=3!+1=7\), qui n’est pas divisible par 4.

Nouvel essai.

Reprends le critère exact pour \(n=6\).

Correction.

\((6-1)!+1=120+1=121=6\times20+1\), donc 6 ne divise pas ce nombre ; 6 est composé.

Retour :

écris de mémoire « \((n-1)!+1\) » puis refais le test pour 5. Ne passe à la suite qu’après avoir distingué les deux factorielles.

Pour réparer une erreur : À refaire plus tard, sans le théorème sous les yeux

Certifie que 13 est premier sans développer \(12!\).

Aide après recherche :

utilise les paires \((2,7),(3,9),(4,10),(5,8),(6,11)\).

Correction.

Les produits sont 14, 27, 40, 40 et 66, respectivement \(13+1\), \(2\times13+1\), \(3\times13+1\), \(3\times13+1\) et \(5\times13+1\). Chacun vaut donc 1 modulo 13. Les deux autres facteurs de \(12!\) sont 1 et 12. La liste utilise tous les facteurs une seule fois, d’où \(12!\equiv1\times12\times1^5\equiv-1\;[13]\).

Wilson conclut que 13 est premier. Ce calcul de paires n’a pas supposé la primalité de 13 : leurs produits ont été vérifiés directement.

À retenir : Un critère exact, deux sens à comprendre

Pour \(n\ge2\), \(n\) est premier si et seulement si \(n\mid((n-1)!+1)\). Le sens direct utilise les inverses ; le sens réciproque exclut un diviseur premier d’un entier composé. La méthode est exacte mais n’est pas un choix efficace pour tester à la main un très grand entier.

Rappel utile : Le kit local pour les fractions et les polynômes

Un nombre rationnel s’écrit \(a/b\), avec \(a\in\mathbb{Z}\), \(b\in\mathbb{N}^*\). On peut choisir la fraction irréductible, c’est-à-dire \(\operatorname{PGCD}(|a|,b)=1\). Le dénominateur est positif et non nul.

Un polynôme à coefficients entiers est une expression \(P(x)=A_dx^d+A_{d-1}x^{d-1}+\cdots+A_1x+A_0\), où tous les \(A_i\) sont des entiers et \(A_d\ne0\). Une racine de \(P\) est un nombre \(r\) pour lequel \(P(r)=0\). On ne cherche dans ce parcours que les racines qui sont rationnelles, sauf lorsque la factorisation permet de conclure davantage.

Le théorème de Gauss, résultat antérieur, donne : si \(u\mid vw\) et \(\operatorname{PGCD}(u,v)=1\), alors \(u\mid w\). Si deux entiers sont premiers entre eux, l’un reste premier avec toute puissance positive de l’autre : un premier commun diviserait aussi la base de cette puissance, par le lemme d’Euclide.

Avant de commencer : Candidat ou solution ?

Pour \(P(x)=2x^2-3\), calcule \(P(1)\) et \(P(3/2)\). Le fait que le numérateur 3 divise le terme constant \(-3\) suffit-il à faire de \(3/2\) une racine ?

Correction.

\(P(1)=2-3=-1\ne0\). Ensuite,

Proposition : Une liste finie de candidats

Soit \(P(x)=A_dx^d+\cdots+A_1x+A_0\) un polynôme à coefficients entiers, de degré \(d\ge1\), avec \(A_d\ne0\) et \(A_0\ne0\). Si la fraction irréductible \(a/b\), avec \(b>0\), est une racine de \(P\), alors

Comme \(P(0)=A_0\ne0\), une telle racine n’est pas nulle.

Démonstration : Supprimer les dénominateurs, puis utiliser Gauss

Supposons \(P(a/b)=0\) et \(\operatorname{PGCD}(|a|,b)=1\). On remplace \(x\) par \(a/b\) dans chaque terme et on multiplie les deux membres par \(b^d\), qui est non nul puisque \(b>0\). Pour chaque indice \(j\) avec \(0\le j\le d\), le terme devient

Par exemple, pour le degré 3, elle s’écrit explicitement \(A_3a^3+A_2a^2b+A_1ab^2+A_0b^3=0\).

Chaque terme d’indice \(j\ge1\) contient un facteur \(a\). Comme la somme vaut 0, \(A_0b^d\) est l’opposé de la somme de ces multiples de \(a\) ; donc \(a\mid A_0b^d\). La fraction étant irréductible, \(\operatorname{PGCD}(|a|,b^d)=1\), donc Gauss donne \(a\mid A_0\).

Pour le dénominateur, chaque terme d’indice \(j<d\) contient au moins un facteur \(b\), car \(d-j\ge1\). Le terme \(A_da^d\) est l’opposé de la somme de ces multiples de \(b\) ; donc \(b\mid A_da^d\). Comme \(\operatorname{PGCD}(b,|a|^d)=1\), Gauss donne \(b\mid A_d\).

Pour \(d=1\), les deux égalités se lisent simplement \(A_0b=-aA_1\) et \(A_1a=-bA_0\) : aucun terme d’exposant négatif n’est à introduire.

Corollaire : Le cas d’un coefficient dominant égal à 1

Pour un polynôme à coefficients entiers dont le coefficient dominant est 1, toute racine rationnelle est un entier. Si son terme constant est non nul, cet entier divise le terme constant.

Démonstration : Un dénominateur positif qui divise 1

Si le terme constant est non nul, la proposition donne \(b\mid1\) et \(b>0\), donc \(b=1\) ; la fraction \(a/b\) est l’entier \(a\). Si le terme constant est nul, on retire le facteur \(x\) autant de fois que possible. Le nombre 0 est une racine entière ; toute racine non nulle annule le facteur restant, encore à coefficients entiers et de coefficient dominant 1, mais avec terme constant non nul. Si ce facteur a un degré au moins égal à 1, le même argument s’y applique. S’il est constant, il vaut 1 et ne possède aucune racine : le polynôme initial est alors une puissance de \(x\), dont la seule racine est 0.

Méthode : De la divisibilité à une résolution

Quand ?

Les coefficients sont entiers et l’on cherche des solutions rationnelles.

Premier geste :