Pour commencer : Pourquoi les restes donnent-ils autant d’informations ?

On peut déterminer le dernier chiffre d’une puissance immense sans écrire tous ses chiffres, prouver qu’une équation n’a aucune solution entière, ou vérifier la cohérence d’un code. L’idée commune est de regarder comment les entiers se répartissent entre multiples et restes.

Ce cours construit ces outils, démontre leurs propriétés et apprend à choisir une démarche. Il ne suppose pas déjà connus le PGCD, les théorèmes de Bézout ou de Gauss, ni le petit théorème de Fermat. Ces résultats font partie d’autres étapes du programme de mathématiques expertes.

Repérage : Qui divise qui ?

À partir de \(-35=5\times(-7)\), écrire deux phrases utilisant « divise » et une phrase utilisant « multiple ». Est-ce que \(5\) est un multiple de \(-35\) ?

Correction expliquée. \(5\) divise \(-35\) et \(-7\) divise \(-35\). Le nombre \(-35\) est un multiple de \(5\). En revanche, \(5/(-35)=-1/7\) n’est pas entier : \(5\) n’est pas un multiple de \(-35\). Si le sens des mots s’inverse, repars de l’égalité « nombre obtenu = diviseur \(\times\) entier » dans la définition qui suit.

Définition : Divisibilité, diviseur et multiple

Soient \(d\) et \(a\) deux entiers relatifs. On dit que \(d\) divise \(a\) lorsqu’il existe un entier \(k\) tel que

Le trait vertical n’est ni une barre de fraction ni un signe d’inégalité. Dans \(d\mid a\), le diviseur est à gauche. L’ordre compte : \(4\mid 20\), car \(20=4\times5\), mais \(20\nmid4\), car \(4/20=1/5\notin\mathbb{Z}\).

Analogie : Faire des paquets, puis dépasser cette image

Avec \(24\) jetons, faire des paquets de \(6\) sans reste donne \(24=6\times4\). Le nombre de jetons correspond au multiple, la taille d’un paquet au diviseur et le nombre de paquets au témoin entier. Cette image explique bien la divisibilité de deux entiers positifs.

Limite : des paquets négatifs ne sont pas des objets matériels. Dans \(\mathbb{Z}\), c’est l’égalité qui fait foi : \(-24=6\times(-4)=(-6)\times4\). L’image ne règle pas non plus le cas du diviseur zéro ; la définition, elle, le permet.

Propriété : Zéro, un et les signes

Avec la définition adoptée :

• tout entier \(d\) divise \(0\) ;

• \(0\mid a\) si et seulement si \(a=0\) ; en particulier \(0\mid0\) ;

• \(1\) et \(-1\) divisent tout entier ;

• changer le signe du diviseur ou du multiple ne change pas la divisibilité.

Démonstration complète. Pour tout \(d\), \(0=d\times0\), avec un témoin entier. Si \(0\mid a\), alors \(a=0\times k=0\) ; réciproquement \(0=0\times0\). Pour \(1\) et \(-1\), on écrit \(a=1\times a=(-1)\times(-a)\).

Enfin, si \(a=dk\), alors \(-a=d(-k)\) et \(a=(-d)(-k)\), avec des témoins encore entiers. Appliquer à nouveau un changement de signe donne les réciproques. Donc

Caractérisation : Un quotient entier, si le dénominateur existe

Pour \(a,d\in\mathbb{Z}\) et \(d\neq0\),

Démonstration complète. Si \(a=dk\), on divise les deux membres par \(d\neq0\) : \(a/d=(d/d)k=1\times k=k\in\mathbb{Z}\). Réciproquement, si \(a/d=k\in\mathbb{Z}\), multiplier par \(d\) donne \(a=dk\). La condition \(d\neq0\) porte sur le diviseur \(d\), pas sur le dividende \(a\), qui peut être nul. Non-exemple : \(12=5\times2{,}4\) ne prouve pas \(5\mid12\), car \(2{,}4\) n’est pas entier.

Lemme : Un diviseur d’un entier non nul est borné

Si \(a\neq0\) et \(d\mid a\), alors \(d\neq0\) et \(1\leq |d|\leq |a|\).

Démonstration complète. Écrivons \(a=dk\) avec \(k\in\mathbb{Z}\). Ni \(d\) ni \(k\) ne peut être nul, sinon \(a=0\). Un entier non nul a une valeur absolue au moins égale à \(1\). Ainsi \(|a|=|d|\,|k|\geq |d|\). Ce lemme garantit qu’une recherche des diviseurs d’un entier non nul peut être finie.

Propriété : Multiples : une liste infinie, sauf pour zéro

Les multiples d’un entier \(d\) dans \(\mathbb{Z}\) sont exactement les nombres \(dk\), avec \(k\in\mathbb{Z}\). Si \(d\neq0\), ils sont en nombre infini ; si \(d=0\), le seul multiple est \(0\).

Démonstration complète. La description vient de la définition de \(d\mid a\). Lorsque \(d\neq0\), deux entiers distincts \(k,\ell\) donnent des multiples distincts : \(dk=d\ell\) entraînerait, après division des deux membres par \(d\neq0\), \(k=\ell\). Les valeurs \(0,d,2d,3d,\ldots\) sont donc toutes distinctes et fournissent une infinité de multiples. Pour \(d=0\), chaque produit \(0\times k\) vaut \(0\).

Exemple. Les multiples de \(4\) sont \(\ldots,-8,-4,0,4,8,12,\ldots\). Zéro est un multiple de \(4\), mais pas un diviseur de \(4\). Les diviseurs d’un entier non nul forment une liste finie ; ses multiples, une liste infinie : ne pas intervertir les deux questions.

Propriété : Chercher les diviseurs par paires

Soit \(N\geq1\) un entier. À chaque diviseur positif \(d\) correspond le diviseur positif \(e=N/d\), et \(de=N\). Au moins un des deux nombres \(d,e\) est inférieur ou égal à \(\sqrt N\).

Démonstration complète. La définition donne \(N=de\), avec \(e\) entier positif. Si les deux facteurs étaient strictement supérieurs à \(\sqrt N\), leur produit serait strictement supérieur à \(\sqrt N\times\sqrt N=N\), contradiction. Il suffit donc de tester tous les entiers positifs jusqu’à \(\sqrt N\), puis de compléter leurs partenaires.

Méthode : Lister sans oublier ni répéter

Quand ? On demande tous les diviseurs d’un entier donné.

Conditions. Traiter zéro à part ; pour un entier non nul \(a\), travailler d’abord avec \(N=|a|\).

Premier geste. Chercher les produits \(d\times e=N\) avec \(d\geq1\) et \(d^2\leq N\).

1. Tester chaque entier de cette plage, sans sauter une valeur.

2. Pour chaque diviseur, noter son partenaire \(N/d\).

3. Réunir les valeurs, supprimer une répétition éventuelle, puis les ranger.

4. Si les diviseurs sont demandés dans \(\mathbb{Z}\), ajouter leurs opposés.

Contrôle. Vérifier chaque produit et l’exhaustivité de la plage testée. Tester seulement quelques nombres « qui ont l’air de marcher » ne prouve pas que la liste est complète.

Exemple : Tous les diviseurs de \(-84\)

Le changement de signe ne modifie pas les diviseurs. On étudie donc \(84\). Comme \(9^2=81<84<100=10^2\), il suffit de tester de \(1\) à \(9\).

Les diviseurs positifs sont donc

Contrôle. Par exemple \(-84=(-7)\times12=14\times(-6)\). Chaque signe donne bien un témoin entier. La propriété des paires garantit qu’aucun autre diviseur n’est oublié.

Corollaire : Pourquoi un carré a un nombre impair de diviseurs positifs

Un entier \(N\geq1\) possède un nombre impair de diviseurs positifs si et seulement si c’est un carré d’entier.

Démonstration complète. Par la propriété des paires, les diviseurs se regroupent en couples \(d,N/d\). Une paire comporte deux nombres distincts sauf si \(d=N/d\), c’est-à-dire \(d^2=N\). Il y a au plus une telle valeur positive. Sans elle, le nombre de diviseurs est pair ; avec elle, on a des paires et un diviseur isolé, donc un nombre impair. Cela prouve aussi la réciproque. Pour \(N=1\), l’unique diviseur positif est \(1\), et \(1=1^2\). Limite : le résultat parle des diviseurs positifs, non de tous les diviseurs relatifs ; chaque diviseur positif a un opposé distinct.

Essai guidé : Compléter des paires

Déterminer les diviseurs de \(18\) dans \(\mathbb{Z}\). Commencer par \(1\times\square\), \(2\times\square\), \(3\times\square\), puis expliquer pourquoi on s’arrête au test de \(4\).

Correction expliquée. Les paires sont \((1,18)\), \((2,9)\), \((3,6)\). Le nombre \(4\) ne convient pas car \(4\times4=16<18<20=4\times5\). Puisque \(4^2<18<5^2\), tous les petits facteurs ont été testés. Les diviseurs relatifs sont \(\{\pm1,\pm2,\pm3,\pm6,\pm9,\pm18\}\).

À toi : À tenter avant de consulter

Déterminer tous les diviseurs relatifs de \(-28\). Justifier qu’il n’en manque aucun.

Indice. Chercher les paires de facteurs de \(28\) en testant de \(1\) à \(5\).

Correction expliquée. \(5^2=25<28<36=6^2\). Les paires sont \(1\times28\), \(2\times14\), \(4\times7\). Ni \(3\) ni \(5\) ne divise \(28\) : \(3\times9<28<3\times10\) et \(5\times5<28<5\times6\). La liste complète est \(\{\pm1,\pm2,\pm4,\pm7,\pm14,\pm28\}\). Chaque petit facteur possible a été testé ; les autres sont ses partenaires.

Justifier : Zéro : deux questions différentes

Expliquer pourquoi \(0\mid0\) est vrai dans notre convention, alors que \(0/0\) n’est pas une fraction définie.

Correction expliquée. Pour la divisibilité, il suffit d’un entier \(k\) vérifiant \(0=0\times k\) ; \(k=0\) convient. Pour une division ordinaire, on devrait déterminer un quotient unique : ici tous les \(k\) conviendraient, ce qui ne définit aucun quotient unique. On ne divise donc pas par zéro.

Critères de réussite. Distinguer une relation d’existence d’une opération de division ; écrire un témoin ; ne pas utiliser \(0/0\) pour prouver une divisibilité.

Variation : Peut-on toujours faire une liste finie ?

Comparer les diviseurs de \(1\) et de \(0\) dans \(\mathbb{Z}\).

Correction expliquée. Si \(d\mid1\), le lemme impose \(|d|\leq1\) et \(d\neq0\), donc \(d=1\) ou \(d=-1\). Ces deux valeurs conviennent. En revanche, \(0=d\times0\) pour tout entier \(d\) : les diviseurs de zéro sont tous les entiers, y compris zéro, et ils sont en nombre infini. La condition « entier non nul » est donc indispensable à la recherche finie.

Réparation : « J’ai trouvé seulement les diviseurs positifs »

Première erreur : annoncer \(1,2,4,7,14,28\) comme tous les diviseurs relatifs de \(-28\). La recherche des facteurs positifs est correcte, mais la conclusion oublie les opposés.

Rappel et exemple plus simple. \(-6=2\times(-3)=(-2)\times3\) : \(2\) et \(-2\) sont tous les deux diviseurs. Les diviseurs relatifs de \(-6\) sont \(\pm1,\pm2,\pm3,\pm6\).

Nouvel essai : lister ceux de \(-10\).

Correction expliquée. \(10=1\times10=2\times5\). Les petits candidats sont \(1,2,3\), et \(3\nmid10\) puisque \(9<10<12\). On obtient \(\pm1,\pm2,\pm5,\pm10\). Reviens alors à \(-28\) : complète chacune de tes six valeurs par son opposé. Tu retrouves exactement les douze valeurs de la tentative précédente.

Reprise différée : À une prochaine séance, avant relecture

Trouver tous les diviseurs relatifs de \(45\) ; préciser pourquoi zéro n’est pas dans la liste et pourquoi elle est exhaustive.

Indice. Tester les entiers de \(1\) à \(6\), car \(6^2<45<7^2\).

Correction expliquée. Les paires sont \(1\times45\), \(3\times15\), \(5\times9\). Les autres candidats \(2,4,6\) sont pairs et leur produit par un entier serait pair, tandis que \(45\) est impair. On obtient \(\pm1,\pm3,\pm5,\pm9,\pm15,\pm45\). Zéro ne divise que zéro, donc pas \(45\). La borne des petits facteurs et les paires assurent l’exhaustivité.

Critères de réussite. Bon sens du symbole ; témoins entiers ; signes ; plage testée ; conclusion complète.

À retenir : La définition décide

\(d\mid a\) signifie \(a=dk\) pour un \(k\) entier. Ne pas confondre diviseur et multiple, ni existence d’un témoin et quotient toujours défini. Pour \(a\neq0\), les diviseurs se cherchent par paires positives puis par changement de signe.

Repérage : Fabriquer un facteur commun

Sans calculatrice, expliquer pourquoi \(7\mid(7\times8-7\times3)\).

Correction expliquée. On factorise : \(7\times8-7\times3=7(8-3)=7\times5\). Le témoin \(5\) est entier. Si ce passage bloque, lis les deux produits comme « huit fois 7 moins trois fois 7 » : il reste cinq fois 7. Le même geste, avec des lettres, sera décisif dans les preuves.

Propriété : Transitivité et multiplication

Pour des entiers \(a,b,c,d\) :

1. si \(a\mid b\) et \(b\mid c\), alors \(a\mid c\) ;

2. si \(a\mid b\), alors \(a\mid bc\) pour tout entier \(c\) ;

3. si \(a\mid b\) et \(c\mid d\), alors \(ac\mid bd\).

Démonstration complète. Pour 1, écrire \(b=au\) et \(c=bv\), avec \(u,v\in\mathbb{Z}\). Alors \(c=(au)v=a(uv)\), et \(uv\) est entier. Pour 2, \(b=au\) donne \(bc=(au)c=a(uc)\). Pour 3, \(b=au\) et \(d=cv\) donnent \(bd=(au)(cv)=(ac)(uv)\). Dans chaque cas, on a construit le témoin entier demandé par la définition, sans diviser par une variable.

Théorème : Combinaison linéaire entière

Si un entier \(d\) divise deux entiers \(a\) et \(b\), alors, pour tous entiers \(u,v\),

Démonstration complète. Les hypothèses fournissent des entiers \(r,s\) tels que \(a=dr\) et \(b=ds\). On remplace dans l’expression :

Corollaire : Ajouter ou retrancher un multiple du diviseur

Pour \(d,a,k\in\mathbb{Z}\),

Démonstration complète. Si \(d\mid a\), alors \(d\mid a+kd\) par le théorème précédent, puisque \(d\mid d\). Réciproquement, si \(d\mid a+kd\), on retranche \(kd\) :

Propriété : Divisibilité dans les deux sens

Si \(a\mid b\) et \(b\mid a\), alors \(a=b\) ou \(a=-b\). Pour des entiers naturels, cela impose \(a=b\).

Démonstration complète. Si l’un est nul, l’autre l’est aussi : zéro ne divise que zéro. Sinon, \(b=au\) et \(a=bv\) avec \(u,v\in\mathbb{Z}\). Substituer donne \(a=auv\). Comme \(a\neq0\), on divise les deux membres par \(a\) et on obtient \(1=uv\). Les seules paires d’entiers de produit \(1\) sont \((1,1)\) et \((-1,-1)\), donc \(b=a\) ou \(b=-a\). Si les deux nombres sont naturels non nuls, l’opposition est impossible.

Contre-exemple : Ce que les propriétés ne disent pas

• De \(d\mid a+b\), on ne déduit pas \(d\mid a\) et \(d\mid b\) : \(5\mid2+3\), mais \(5\nmid2\) et \(5\nmid3\).

• De \(d\mid ab\), on ne déduit pas « \(d\mid a\) ou \(d\mid b\) » : \(6\mid2\times3\), mais \(6\) ne divise ni \(2\) ni \(3\).

• Les coefficients d’une combinaison doivent être entiers. Ainsi \(2\mid2\), mais \((1/2)\times2=1\) n’est pas divisible par \(2\).

Un contre-exemple respecte les hypothèses et contredit la conclusion. Il suffit alors à réfuter l’affirmation générale ; il ne réfute pas le théorème correctement énoncé.

Méthode : Éliminer l’entier variable

Indice : le diviseur et le nombre à diviser sont des expressions affines en un même entier \(n\). On cherche à remplacer le second par une constante.

Premier geste. Écrire le nombre à diviser sous la forme « multiple entier du diviseur + constante ». La soustraction d’un multiple est légitime dans les deux sens. Étapes : transformer en divisibilité d’une constante ; lister tous ses diviseurs relatifs ; résoudre les petites équations obtenues ; vérifier le domaine et conclure. Si la constante est zéro, ne pas utiliser une liste finie : tout entier divise zéro.

Contrôle. Substituer au moins une solution et vérifier le raisonnement réciproque pour toute la liste. Pour une fraction, conserver en plus l’exclusion de son dénominateur nul.

Exemple : Déterminer tous les \(n\) tels que \(n-2\mid3n+4\)

On cherche les entiers \(n\). Pour éliminer \(n\), on retire trois fois le diviseur :

Contrôle. Pour \(n=-3\), \(n-2=-5\) et \(3n+4=-9+4=-5=(-5)\times1\). Pour la réciproque générale, \(3n+4=3(n-2)+10\) est divisible par \(n-2\) dès que \(10\) l’est.

Exemple : Réduire les diviseurs communs possibles

Soit \(n\in\mathbb{Z}\). Si \(d\) divise \(8n+3\) et \(5n+2\), il divise

Attention à la portée : avec \(5n+1\) et \(3n+2\), la combinaison \(3(5n+1)-5(3n+2)=15n+3-15n-10=-7\) donne seulement \(d\in\{\pm1,\pm7\}\). Pour \(n=0\), les nombres sont \(1\) et \(2\), donc \(7\) ne convient pas ; pour \(n=4\), ils sont \(21\) et \(14\), donc \(7\) convient. Une restriction sur les candidats n’est pas automatiquement une caractérisation.

Essai guidé : La constante cachée

Trouver tous les \(n\in\mathbb{Z}\) tels que \(n+1\mid2n+8\), en complétant \(2n+8=2(n+1)+\square\).

Correction expliquée. \(2(n+1)=2n+2\), donc la case vaut \(6\). On a \(n+1\mid2n+8\) si et seulement si \(n+1\mid6\). Les diviseurs de \(6\) sont \(-6,-3,-2,-1,1,2,3,6\). Soustraire \(1\) à chacun donne \(n\in\{-7,-4,-3,-2,0,1,2,5\}\). La réciproque résulte de \(2n+8=2(n+1)+6\).

À toi : À tenter avant la correction

Déterminer les entiers \(n\) tels que \(n-4\mid5n-13\).

Indice. Retrancher \(5(n-4)\).

Correction expliquée. \((5n-13)-5(n-4)=5n-13-5n+20=7\). La relation équivaut à \(n-4\mid7\). Donc \(n-4\) vaut \(-7,-1,1\) ou \(7\), d’où \(n=-3,3,5\) ou \(11\). Pour chacune, \(5n-13=5(n-4)+7\) est bien un multiple de \(n-4\). La valeur \(4\) ne convient pas, car elle demanderait \(0\mid7\).

Justifier : Une fraction n’est pas une simple relation de divisibilité

Pour quels entiers \(n\) le nombre \((4n+7)/(n+2)\) est-il entier ? Justifier l’exclusion et les deux sens.

Correction expliquée. Le dénominateur impose \(n\neq-2\). Or \(4n+7=4(n+2)-1\). Le quotient est entier si et seulement si \(n+2\mid4n+7\), donc si et seulement si \(n+2\mid-1\). Ainsi \(n+2=1\) ou \(-1\), soit \(n=-1\) ou \(-3\). Les vérifications donnent \(3/1=3\) et \((-5)/(-1)=5\). Les deux valeurs respectent l’exclusion.

Critères de réussite. Nommer le dénominateur ; garder \(n\neq-2\) ; utiliser une équivalence ; vérifier les valeurs, pas seulement proposer des candidats.

Variation : Une information supplémentaire change la conclusion

On sait que \(d\mid a+b\). Peut-on affirmer \(d\mid b\) ? Et si l’on sait aussi \(d\mid a\) ?

Correction expliquée. Sans l’information supplémentaire, non : \(5\mid2+3\), mais \(5\nmid3\). Avec \(d\mid a\), on écrit \(b=(a+b)-a\). C’est une combinaison entière de deux multiples de \(d\), donc \(d\mid b\). Le rôle précis de la seconde hypothèse est de permettre cette soustraction.

Réparation : « Le diviseur doit être égal à la constante »

Erreur : de \(n-4\mid7\), conclure seulement \(n-4=7\). Un diviseur n’est pas nécessairement le nombre lui-même, ni positif.

Exemple plus simple : \(x\mid2\) signifie \(x\in\{-2,-1,1,2\}\). Ainsi \(x=-1\) convient car \(2=(-1)\times(-2)\).

Nouvel essai : résoudre \(n-1\mid n+1\).

Correction expliquée. En retranchant \(n-1\), on obtient \(n-1\mid2\). Donc \(n-1=-2,-1,1\) ou \(2\), puis \(n=-1,0,2\) ou \(3\). Toutes conviennent car \(n+1=(n-1)+2\). Reviens à la ligne initiale : les quatre diviseurs de \(7\) redonnent les quatre solutions \(-3,3,5,11\), non la seule valeur \(11\).

Reprise différée : Transformer et conclure dans les deux sens

À une prochaine séance, sans relire d’abord, résoudre \(n+3\mid4n+5\) dans \(\mathbb{Z}\).

Indice. Comparer \(4n+5\) et \(4(n+3)\).

Correction expliquée. \(4n+5-4(n+3)=4n+5-4n-12=-7\). La relation équivaut à \(n+3\mid-7\), donc \(n+3\in\{-7,-1,1,7\}\). On trouve \(n\in\{-10,-4,-2,4\}\). Réciproquement, \(4n+5=4(n+3)-7\) prouve que chaque valeur convient. La valeur \(-3\) n’est pas solution puisque \(0\nmid-7\).

Critères de réussite. Montrer les signes distribués ; lister les diviseurs relatifs ; isoler \(n\) ; justifier l’exhaustivité et la réciproque.

À retenir : Une bonne transformation conserve la question

Une combinaison entière permet de fabriquer un multiple connu. Pour résoudre, distinguer implication et équivalence. Éliminer l’inconnue d’une expression ne dispense ni de vérifier le domaine ni de tester les candidats quand seule une condition nécessaire a été obtenue.

Repérage : Réel ou entier : le domaine change tout

Le couple \((4,3)\) résout-il \(xy=12\) ? Et le couple \((8,1{,}5)\) ? Les réponses changent-elles si l’on demande des entiers ?

Correction expliquée. Les deux produits valent \(12\) dans \(\mathbb{R}\), car \(4\times3=12\) et \(8\times1{,}5=12\). Dans \(\mathbb{Z}^2\), seul \((4,3)\) est autorisé : \(1{,}5\notin\mathbb{Z}\). Si cette différence bloque, encadre le domaine dès la première ligne : « Je cherche \(x,y\in\mathbb{Z}\) ». Une solution doit respecter à la fois l’équation et le domaine.

Vocabulaire : Équation diophantienne et couple ordonné

Une équation diophantienne est une équation dont on recherche les solutions entières. Un couple \((x,y)\) est ordonné : \((2,6)\) et \((6,2)\) sont deux couples distincts. Dire « toutes les solutions » demande de prouver deux choses : aucune solution n’est oubliée, et chaque couple annoncé convient.

Caractérisation : Une équation produit avec second membre non nul

Pour un entier \(N\neq0\), les solutions entières de \(uv=N\) sont exactement

Démonstration complète. Si \(uv=N\), alors \(u\neq0\) et \(u\mid N\), avec témoin \(v\). Diviser l’égalité par \(u\neq0\) donne \(v=N/u\). Réciproquement, pour tout diviseur \(d\) de \(N\), \(d\neq0\), le nombre \(N/d\) est entier et \(d(N/d)=N\). La description est donc nécessaire et suffisante.

Si \(N=0\), le résultat doit être remplacé par \(uv=0\) si et seulement si \(u=0\) ou \(v=0\). Il peut alors y avoir une infinité de solutions.

Méthode : Analyse puis vérification de tous les candidats

Indices : produit, différence de deux carrés, ou expression contenant \(xy\), \(x\) et \(y\). La contrainte d’intégralité suggère d’exploiter des diviseurs.

Premier geste. Transformer l’équation en \(uv=N\), où \(u,v\) sont des expressions entières simples. Vérifier le signe de \(N\) et traiter \(N=0\) à part.

1. Lister les paires ordonnées de facteurs de \(N\), signes compris.

2. Retrouver \(x,y\) dans chaque cas ; vérifier qu’ils sont entiers et respectent le domaine demandé.

3. Vérifier que les transformations sont réversibles, ou substituer les candidats dans l’équation initiale.

La première phase réduit toute solution possible à une liste de candidats : c’est l’analyse. La dernière vérifie que les candidats conviennent : c’est la synthèse. Une méthode correcte doit fermer les deux phases.

Exemple : Une différence de carrés

Cherchons les couples \((x,y)\in\mathbb{Z}^2\) tels que \(x^2-y^2=32\). Posons \(u=x-y\) et \(v=x+y\). On doit avoir \(uv=32\). En additionnant et en soustrayant les deux égalités :

Contrôle. \(9^2-7^2=81-49=32\) et \(6^2-2^2=36-4=32\) ; changer les signes ne change pas les carrés. Si l’on demandait \(x,y\in\mathbb{N}\), seuls \((9,7)\) et \((6,2)\) resteraient.

Exemple : Faire apparaître un produit qui n’était pas visible

Résolvons \(xy-2x+3y=11\) dans \(\mathbb{Z}^2\). Le développement

Contrôle. Pour \((-8,1)\), le membre de gauche vaut \((-8)\times1-2\times(-8)+3\times1=-8+16+3=11\). La vérification numérique confirme ce couple ; c’est l’équivalence précédente qui justifie toute la liste.

Essai guidé : Un produit négatif

Résoudre \(xy=-12\) dans \(\mathbb{Z}^2\). Commencer par les valeurs possibles de \(x\), puis écrire \(y=-12/x\).

Correction expliquée. Les diviseurs de \(-12\) sont \(\pm1,\pm2,\pm3,\pm4,\pm6,\pm12\). Pour \(x=1,2,3,4,6,12\), on obtient respectivement \(y=-12,-6,-4,-3,-2,-1\). Pour les valeurs opposées de \(x\), les valeurs de \(y\) sont opposées aussi. Les douze couples sont donc

À toi : Chercher les solutions avant de lire

Résoudre \(xy+x+y=14\) dans \(\mathbb{Z}^2\), puis dans \(\mathbb{N}^2\).

Indice. Développer \((x+1)(y+1)\), sans oublier le dernier produit.

Correction expliquée. \((x+1)(y+1)=xy+x+y+1\). Ajouter \(1\) aux deux membres donne donc \((x+1)(y+1)=15\). Les paires ordonnées positives de facteurs sont \((1,15),(3,5),(5,3),(15,1)\), ainsi que les quatre paires négatives correspondantes. On soustrait \(1\) à chaque composante :

Justifier : Pourquoi faut-il contrôler la parité ?

Dans une résolution de \(x^2-y^2=N\), expliquer pourquoi une paire \((u,v)\) de facteurs de \(N\) ne donne pas toujours une solution entière.

Correction expliquée. On doit retrouver \(x=(u+v)/2\) et \(y=(v-u)/2\). Si les facteurs n’ont pas la même parité, leur somme et leur différence sont impaires : les quotients par \(2\) ne sont pas entiers. Ainsi \((u,v)=(1,32)\) donnerait \(x=33/2\), \(y=31/2\), interdits dans \(\mathbb{Z}\).

Critères de réussite. Donner les formules de retour ; nommer l’intégralité recherchée ; relier celle-ci à la parité, pas seulement dire « cette paire ne marche pas ».

Variation : Une équation impossible

Existe-t-il \(x,y\in\mathbb{Z}\) tels que \(x^2-y^2=14\) ?

Correction expliquée. Une solution donnerait \(u=x-y\), \(v=x+y\) de même parité, avec \(uv=14\). Deux impairs ont un produit impair, impossible ici. Deux pairs s’écrivent \(u=2r\), \(v=2s\), donc \(uv=4rs\), multiple de \(4\). Or \(14\) n’est pas multiple de \(4\), car \(4\times3<14<4\times4\). Les deux cas sont impossibles ; il n’y a donc aucune solution. L’obstruction de parité évite une longue recherche.

Réparation : Une division qui fait perdre des solutions

Erreur : partir de \(xy=0\), diviser par \(x\), puis annoncer seulement \(y=0\). La première opération suppose \(x\neq0\), alors que \(x=0\) est autorisé.

Rappel et exemple simple : \(0\times7=0\), donc \((0,7)\) est une solution perdue. Il faut séparer \(x=0\) (tout \(y\) convient) et \(x\neq0\) (alors \(y=0\)).

Nouvel essai : résoudre \((x-2)(y+1)=0\) dans \(\mathbb{Z}^2\).

Correction expliquée. Le produit est nul si et seulement si \(x-2=0\) ou \(y+1=0\). Les solutions sont tous les couples \((2,y)\), \(y\in\mathbb{Z}\), et tous les couples \((x,-1)\), \(x\in\mathbb{Z}\). Le couple \((2,-1)\) appartient aux deux descriptions, ce qui n’est pas une nouvelle solution. Reviens à \(xy=0\) : la solution complète est \(x=0\) ou \(y=0\), pas seulement \(y=0\).

Reprise différée : Une autre différence de carrés

À une séance suivante, déterminer tous les couples naturels \((x,y)\) tels que \(x^2-y^2=35\), en justifiant l’exhaustivité.

Indice. Comme \(x,y\geq0\) et \(x^2>y^2\), on a \(x>y\), donc \(0<x-y\leq x+y\).

Correction expliquée. Les paires positives de produit \(35\) avec le premier facteur inférieur ou égal au second sont \((1,35)\) et \((5,7)\). Elles ont la même parité. Les formules de retour donnent \((x,y)=(18,17)\) et \((6,1)\). Vérifications : \(18^2-17^2=324-289=35\), \(6^2-1^2=36-1=35\). Les autres orientations donneraient \(y<0\), et les paires négatives donneraient \(x<0\) ; elles sont exclues dans \(\mathbb{N}^2\).

Critères de réussite. Factoriser ; utiliser le domaine pour les signes et l’ordre ; lister les facteurs ; retrouver et vérifier les inconnues.

À retenir : Une liste de candidats n’est pas encore une résolution

Factoriser transforme l’intégralité en recherche de diviseurs. Il faut ensuite revenir aux inconnues, vérifier leurs domaines et établir la réciproque. Toujours traiter le produit nul séparément.

Repérage : L’égalité seule suffit-elle ?

On a \(58=7\times8+2=7\times7+9\). Dans une division par \(7\), quel reste choisir ? Pourquoi ?

Correction expliquée. On choisit \(2\), car \(0\leq2<7\). Le nombre \(9\) contient encore un paquet de \(7\) : \(9=7+2\). En le transférant au quotient, \(7\times7+9=7\times7+7+2=7\times8+2\). Si tu ne sais pas choisir, retiens le double contrôle : égalité et reste compris entre zéro inclus et le diviseur exclu.

Intuition : Le multiple placé juste avant

Pour diviser un entier \(a\) par \(b>0\), on cherche le multiple de \(b\) immédiatement à sa gauche sur la droite graduée, ou \(a\) lui-même s’il est multiple. Le quotient donne l’indice de ce multiple ; le reste est la distance horizontale entre ce multiple et \(a\).

Lecture du schéma : \(-9\) est entre les multiples \(-14\) et \(-7\) de \(7\). Partir de \(-14\) puis avancer de \(5\) donne \(-9\). Donc \(-9=7\times(-2)+5\). Le reste est positif même si le dividende est négatif. Limite : un dessin suggère le bon encadrement ; la preuve exige les inégalités exactes. La division euclidienne étudiée ici impose un diviseur strictement positif.

Théorème : Existence et unicité de la division euclidienne

Pour tout entier \(a\in\mathbb{Z}\) et tout entier \(b\geq1\), il existe un unique couple \((q,r)\in\mathbb{Z}^2\) tel que

Démonstration : Construire le couple : l’existence

Premier cas : \(a\geq0\). Parmi les entiers \(j\) de la liste finie \(0,1,\ldots,a\) pour lesquels \(bj\leq a\), il y en a au moins un : \(j=0\). Cette sous-liste finie non vide possède un plus grand élément, noté \(q\). Ainsi \(bq\leq a\).

On a aussi \(a<b(q+1)\). Sinon \(b(q+1)\leq a\) ; comme \(b\geq1\), cela donnerait \(q+1\leq a\), donc \(q+1\) appartiendrait à la même liste admissible, contrairement au choix maximal de \(q\).

En soustrayant \(bq\) aux trois membres de \(bq\leq a<b(q+1)=bq+b\), on obtient

Deuxième cas : \(a<0\). Posons \(A=-a>0\). Le premier cas fournit \(A=bQ+R\) avec \(0\leq R<b\).

• Si \(R=0\), alors \(a=-A=b(-Q)+0\) : choisir \(q=-Q\), \(r=0\).

• Si \(R>0\), alors \(0<R<b\) et

  \[a=-A=-bQ-R=b(-Q-1)+(b-R).\]
  En effet, développer le dernier membre donne \(-bQ-b+b-R=-bQ-R\). De \(0<R<b\), on déduit \(0<b-R<b\). On peut donc choisir \(q=-Q-1\), \(r=b-R\).

Dans tous les cas, un couple existe. On n’a pas supposé qu’un reste négatif était autorisé.

Lemme : Un petit multiple doit être nul

Si \(b\geq1\), \(b\mid t\) et \(-b<t<b\), alors \(t=0\).

Démonstration complète. Écrivons \(t=bk\), \(k\in\mathbb{Z}\). Si \(k\geq1\), alors \(t\geq b\), impossible. Si \(k\leq-1\), alors \(t\leq-b\), impossible. Le seul entier restant est \(k=0\), donc \(t=0\). Ce lemme sert maintenant à prouver l’unicité.

Démonstration : Pourquoi le couple est unique

Supposons que \((q,r)\) et \((q',r')\) conviennent. Les deux égalités donnent

Corollaire : Reconnaître la divisibilité par le reste

Pour \(a\in\mathbb{Z}\) et \(b\geq1\), \(b\mid a\) si et seulement si le reste de la division de \(a\) par \(b\) est nul.

Démonstration complète. Un reste nul donne \(a=bq\), donc \(b\mid a\). Réciproquement, si \(a=bk\), le couple \((k,0)\) satisfait \(0\leq0<b\). Par unicité, c’est le couple de la division euclidienne. Le reste vaut donc zéro.

Méthode : Calculer et contrôler un couple

Indice : on demande le quotient, le reste ou une égalité de division.

Premier geste. Vérifier \(b>0\), puis chercher \(q\) tel que \(bq\leq a<b(q+1)\). Calculer ensuite \(r=a-bq\). Pour \(a<0\), on peut diviser \(-a\), puis appliquer les deux cas de la preuve : reste initial nul, ou reste strictement positif. Ne pas arrondir le quotient vers zéro.

Contrôle. Vérifier \(a=bq+r\) et \(0\leq r<b\). Ces deux contrôles, avec l’unicité, suffisent à certifier le couple.

Exemple : Le signe du dividende ne donne pas le signe du reste

Divisons \(173\), puis \(-173\), par \(12\). On a \(12\times14=168\) et \(12\times15=180\), donc

Si le nombre est un multiple exact, le reste ne devient pas \(12\) : \(-180=12\times(-15)+0\). Le couple \((-16,12)\) vérifie l’égalité mais pas la borne \(r<12\).

Notation : Lien avec la partie entière

Pour un réel \(x\), \(\lfloor x\rfloor\) désigne le plus grand entier inférieur ou égal à \(x\), c’est-à-dire l’entier \(m\) tel que \(m\leq x<m+1\). Par exemple \(\lfloor3{,}4\rfloor=3\), mais \(\lfloor-3{,}4\rfloor=-4\), non \(-3\). En divisant l’encadrement \(bq\leq a<b(q+1)\) par \(b>0\), le sens est conservé et l’on obtient \(q\leq a/b<q+1\). Ainsi

Méthode : Utiliser des contraintes sur le quotient ou le reste

Indice : un énoncé relie \(a,b,q,r\), ou demande les valeurs possibles de l’un d’eux.

Premier geste. Écrire \(a=bq+r\) avec \(b\geq1\) et \(0\leq r<b\), puis ajouter les autres contraintes.

• Un diviseur fixé donne une liste finie de restes : \(0,1,\ldots,b-1\).

• Un quotient connu donne l’encadrement \(bq\leq a<b(q+1)\). Si l’on divise une inégalité par \(q\) ou \(q+1\), vérifier leur signe ; traiter les zéros à part.

• Deux divisions du même nombre permettent souvent d’éliminer ce nombre par soustraction.

Contrôle. Reconstituer les divisions pour chaque candidat et revérifier les bornes. Une équation sans ces bornes peut fournir de faux candidats.

Exemple : Le quotient dépend du reste

Cherchons les entiers naturels \(a\) dont la division par \(6\) donne \(q=2r+1\). On écrit

Exemple : Retrouver un diviseur inconnu

On divise \(257\) par un entier \(b>0\) et l’on obtient le quotient \(12\). Alors

Si \(b=20\), \(r=257-20\times12=257-240=17<20\). Si \(b=21\), \(r=257-21\times12=257-252=5<21\). Les deux possibilités sont \((b,r)=(20,17)\) et \((21,5)\).

Exemple : Comparer deux divisions

Un entier \(a\) laisse le reste \(9\) dans la division par \(b>0\), et \(2a\) laisse le reste \(4\) dans la division par le même \(b\). Cherchons \(b\).

On a \(a=bq+9\), \(2a=bq'+4\), avec \(b>9\). Doubler la première égalité puis comparer donne

Essai guidé : Réparer un reste négatif

Diviser \(-94\) par \(8\). Partir de \(94=8\times11+6\), puis compléter \(-94=8\times(-12)+\square\).

Correction expliquée. \(-94=-8\times11-6=8(-11-1)+(8-6)=8\times(-12)+2\). Donc \(q=-12\), \(r=2\). Le contrôle donne \(-96+2=-94\) et \(0\leq2<8\).

À toi : Deux cas à traiter sans consulter

Déterminer quotient et reste de la division par \(9\) de \(-101\), puis de \(-108\). Écrire les deux contrôles.

Indice. Le premier n’est pas multiple de \(9\), le second l’est.

Correction expliquée. \(101=9\times11+2\), donc \(-101=9\times(-12)+(9-2)=9\times(-12)+7\). Ainsi \(q=-12\), \(r=7\), car \(-108+7=-101\) et \(0\leq7<9\). Pour \(-108\), on a directement \(-108=9\times(-12)+0\), avec \(0\leq0<9\). Le quotient est le même, mais les restes diffèrent.

Justifier : Pourquoi exclure la borne supérieure ?

Pourquoi impose-t-on \(r<b\), et non seulement \(r\leq b\) ?

Correction expliquée. Avec \(r=b\), on pourrait écrire \(a=bq+b=b(q+1)+0\). Deux couples différents représenteraient la même division. Par exemple \(24=6\times3+6=6\times4+0\). La borne stricte exclut le premier et conserve le second.

Critères de réussite. Montrer deux couples distincts ; expliquer le transfert d’un paquet ; relier la borne à l’unicité, pas seulement à une règle apprise.

Variation : Quand le quotient vaut zéro

Quels sont les entiers \(a\) dont la division par \(5\) donne \(q=0\) ? Peut-on inclure \(-1\) ?

Correction expliquée. \(a=5\times0+r=r\), avec \(0\leq r<5\), donc \(a\in\{0,1,2,3,4\}\). On ne peut pas inclure \(-1\) : \(-1=5\times(-1)+4\), donc son quotient vaut \(-1\). La partie entière n’est pas une troncature vers zéro. Pour \(b=1\), cas limite différent, tout \(a\) s’écrit \(1\times a+0\) : le reste est toujours nul.

Réparation : « Une égalité vraie suffit »

Première erreur : annoncer \(q=-14,r=-5\) pour la division de \(-173\) par \(12\). L’égalité est vraie ; la borne du reste est fausse.

Exemple plus simple : \(-1=5\times0-1\) n’est pas une division euclidienne. En remplaçant \(-1\) par \(-5+4\), on obtient \(-1=5\times(-1)+4\).

Nouvel essai : diviser \(-17\) par \(5\).

Correction expliquée. \(-17=5\times(-3)-2=5\times(-4)+(5-2)=5\times(-4)+3\). On vérifie \(-20+3=-17\) et \(0\leq3<5\). Reviens à \(-173\) : le même transfert d’un paquet donne \(q=-15,r=7\). Ne change pas seulement le signe du reste sans adapter le quotient.

Reprise différée : Restes et contraintes

À une prochaine séance : (1) diviser \(-146\) par \(11\) ; (2) trouver les entiers naturels \(a\) dont la division par \(4\) a un quotient égal au reste.

Indice. Pour (1), partir de \(146=11\times13+3\). Pour (2), remplacer \(q\) par \(r\) dans \(a=4q+r\).

Correction expliquée. (1) \(-146=11\times(-14)+(11-3)=11\times(-14)+8\). Contrôles : \(-154+8=-146\), \(0\leq8<11\). (2) \(a=4r+r=5r\), avec \(r\in\{0,1,2,3\}\). Donc \(a\in\{0,5,10,15\}\). Pour chaque valeur, \(q=r\) et le reste est bien inférieur à \(4\).

Critères de réussite. Domaine du diviseur ; égalité recomposée ; bornes ; tous les cas possibles ; réciproque pour la liste.

À retenir : Deux vérifications inséparables

Une division euclidienne est une égalité \(a=bq+r\) accompagnée de \(b>0\) et \(0\leq r<b\). Le dividende et le quotient peuvent être négatifs, pas le reste. Quand une inconnue intervient, les bornes font partie du problème, pas d’une décoration finale.

Repérage : As-tu identifié le vrai reste ?

Avant de lire la réponse, choisir le reste de \(-17\) dans la division par \(5\) : \(-2\), \(3\) ou \(17\). Dire aussi si \(5\) divise \(-20\).

Correction expliquée. Les égalités \(-17=5\times(-3)-2\) et \(-17=5\times(-4)+3\) sont toutes deux exactes. La première ne convient pas comme division euclidienne, car \(-2<0\). La seconde satisfait \(0\leq3<5\) : le reste est donc \(3\). Enfin \(-20=5\times(-4)\) avec \(-4\in\mathbb{Z}\) : oui, \(5\mid-20\). Si le signe du multiplicateur ou la borne du reste t’a posé problème, reprends le point de départ local avant de continuer. La réparation de cette unité retravaillera précisément ce geste.

Définition : Être congrus modulo un entier

Soit \(n\) un entier fixé tel que \(n\geq2\). Deux entiers relatifs \(a\) et \(b\) sont congrus modulo \(n\) lorsque \(n\) divise \(a-b\).

Ce symbole ne dit pas que \(a=b\). Il dit que l’écart entre \(a\) et \(b\) est un nombre entier de paquets de taille \(n\). Le module fait partie de l’énoncé : il ne faut pas l’effacer.

Exemple et non-exemple : Un entier négatif convient tout à fait

\(-11\equiv 10\pmod{7}\), car

Les deux nombres peuvent aussi être égaux : \(a-a=0=n\times0\), donc \(a\equiv a\pmod{n}\) pour tout entier \(a\).

Théorème de caractérisation : Congruence et même reste

Soient \(a,b\in\mathbb{Z}\) et \(n\geq2\). Les entiers \(a\) et \(b\) sont congrus modulo \(n\) si et seulement si ils ont le même reste dans la division euclidienne par \(n\).

Démonstration complète. Écrivons les deux divisions, en donnant un nom distinct à chaque quotient et à chaque reste :

Sens réciproque : une congruence impose le même reste. Supposons \(a\equiv b\pmod{n}\). Il existe \(k\in\mathbb{Z}\) tel que \(a-b=nk\). En remplaçant \(a\) et \(b\) par leurs expressions,

Représentation intuitive : Une même position dans des paquets successifs

Voici quelques entiers congrus à \(5\) modulo \(9\) :

Description : la ligne porte \(-22,-13,-4,5,14,23\) ; chaque flèche ajoute \(9\). Tous ces nombres ont pour reste \(5\) lorsqu’on les divise par \(9\).

La comparaison avec des paquets aide à comprendre ce que la congruence conserve : la position restante, et non le nombre de paquets. Sa limite est importante : \(-4\) n’est pas un reste euclidien modulo \(9\), même s’il peut remplacer \(5\) dans une congruence. En effet \(-4=9\times(-1)+5\) ; son reste est \(5\). La définition formelle reste la divisibilité de la différence.

Propriété : Trois règles qui organisent la relation

Pour tous \(a,b,c\in\mathbb{Z}\), avec le même module \(n\geq2\) :

1. \(a\equiv a\pmod{n}\) : réflexivité ;

2. si \(a\equiv b\pmod{n}\), alors \(b\equiv a\pmod{n}\) : symétrie ;

3. si \(a\equiv b\pmod{n}\) et \(b\equiv c\pmod{n}\), alors \(a\equiv c\pmod{n}\) : transitivité.

Démonstration complète. Pour la première règle, \(a-a=n\times0\). Pour la deuxième, écrivons \(a-b=nk\) avec \(k\in\mathbb{Z}\) ; alors \(b-a=-nk=n(-k)\), avec \(-k\in\mathbb{Z}\). Pour la troisième, écrivons \(a-b=nk\) et \(b-c=n\ell\) ; leur somme donne

Vocabulaire. Ces trois propriétés font de la congruence une relation d’équivalence. Connaître ce nom n’ajoute aucune règle de calcul : celles dont tu as besoin viennent d’être énoncées et prouvées.

Corollaire : Tous les représentants, un seul reste

Si \(r\) est le reste de \(a\) dans la division par \(n\geq2\), les entiers \(x\) congrus à \(a\) modulo \(n\) sont exactement

Démonstration complète. D’après la caractérisation précédente, \(a\equiv r\pmod{n}\). Par symétrie et transitivité, \(x\equiv a\pmod{n}\) équivaut à \(x\equiv r\pmod{n}\). La définition donne alors \(x-r=nk\), donc \(x=r+nk\). Réciproquement, chaque écriture \(x=r+nk\) fournit bien \(x-r=nk\) ; elle entraîne la congruence. L’unicité dans l’intervalle \(0\leq r<n\) est celle du reste euclidien.

Remarque : Pourquoi choisir un module au moins égal à 2 ?

La même définition a un sens pour \(n=1\) : tous les entiers sont congrus entre eux, puisque \(a-b=1\times(a-b)\). Leur reste dans la division par \(1\) est toujours \(0\). Le cas est exact mais ne distingue aucun entier d’un autre. Dans cette unité, on travaille donc avec \(n\geq2\). Un module nul n’est pas admis dans nos calculs de congruences.

Méthode : Choisir entre différence et reste

Quand ? Pour vérifier une congruence, trouver un représentant commode ou décrire tous les entiers qui conviennent.

Premier geste. Écrire le module et vérifier qu’il est le même dans toute la question.

1. Pour comparer deux entiers donnés, calculer \(a-b\), puis chercher un entier \(k\) tel que \(a-b=nk\). Cette voie est souvent la plus courte.

2. Pour demander explicitement un reste, écrire \(a=nq+r\) et contrôler \(0\leq r<n\). Un représentant négatif ne suffit pas comme réponse finale.

3. Pour chercher tous les entiers congrus à \(a\), trouver son reste \(r\), puis écrire \(x=r+nk\), \(k\in\mathbb{Z}\). Traduire ensuite toute borne imposée à \(x\).

Pourquoi ? La première voie applique la définition ; les deux autres utilisent la caractérisation démontrée. Ce sont des descriptions du même fait, non trois règles indépendantes à mémoriser.

Contrôle. Vérifier une différence multiple de \(n\) et, lorsqu’un reste est demandé, vérifier aussi son intervalle. L’essai d’une seule valeur ne prouve pas que la liste des représentants est complète.

Exemple de référence : Comparer puis décrire toutes les possibilités

Vérifions \(-58\equiv 23\pmod{9}\), puis cherchons les entiers \(x\) compris entre \(-20\) et \(20\) congrus à \(-58\) modulo \(9\).

1. Comparer. La différence est \(-58-23=-81=9\times(-9)\). Le multiplicateur \(-9\) est entier : la congruence est vraie. On peut la contrôler par les divisions

2. Décrire, puis restreindre. Toutes les possibilités sont \(x=5+9k\), \(k\in\mathbb{Z}\). La condition sur \(x\) devient

Essai guidé : Faire apparaître le témoin entier

Les entiers \(-26\) et \(22\) sont-ils congrus modulo \(8\) ? Complète d’abord \(-26-22=8\times\ldots\), puis trouve leur reste commun.

Correction expliquée. On calcule \(-26-22=-48=8\times(-6)\). Le témoin \(-6\) est entier, donc \(-26\equiv 22\pmod{8}\). Les divisions sont

À toi : Produire avant de consulter

Vérifie si \(-37\) et \(29\) sont congrus modulo \(11\). Cherche ensuite tous les entiers \(x\) entre \(0\) et \(30\) congrus à \(-37\) modulo \(11\). Écris un argument d’exhaustivité.

Indice. Une différence donne une première réponse ; une division euclidienne donne ensuite le représentant entre \(0\) et \(10\).

Correction expliquée. \(-37-29=-66=11\times(-6)\), donc la congruence est vraie. De plus,

Critères de réussite. Différence et multiplicateur justes ; reste dans \([0,11[\) ; \(k\) explicitement entier ; borne et liste complète.

Justifier : Dire exactement ce que l’on conserve

Explique avec tes mots pourquoi deux nombres congrus modulo \(9\) peuvent avoir des quotients différents dans la division par \(9\).

Correction expliquée. Une réponse possible est : « La congruence conserve le reste, pas le quotient. Si \(a=9q+r\) et \(b=9q'+r\), leur différence vaut \(9(q-q')\) ; elle est divisible par \(9\) même si \(q\neq q'\). Par exemple \(-58=9\times(-7)+5\) et \(23=9\times2+5\) ont le même reste, mais les quotients sont \(-7\) et \(2\). »

Critères de réussite. Nommer ce qui est commun ; ne pas confondre égalité et congruence ; donner soit les écritures générales, soit un exemple dont les deux divisions et les bornes du reste sont vérifiées.

Variation : Changer la condition, pas seulement les nombres

La phrase « \(24\) et \(6\) sont congrus » est-elle complète ? Étudie-la modulo \(9\), puis modulo \(7\). Peut-on en déduire que \(24=6\) ?

Correction expliquée. La phrase doit préciser un module. Modulo \(9\), \(24-6=18=9\times2\) : oui. Modulo \(7\), \(18=7\times2+4\) avec \(4\neq0\) : non. Les nombres étudiés sont identiques ; c’est la condition qui a changé. Aucune congruence obtenue ne donne l’égalité \(24=6\).

Réparation : Un représentant négatif n’est pas le reste

Première erreur. « \(-26=8\times(-3)-2\), donc le reste de \(-26\) modulo \(8\) est \(-2\). » L’égalité est vraie ; la conclusion ne respecte pas \(0\leq r<8\).

Rappel utile. Enlever \(1\) au quotient retire un paquet de taille \(8\) dans le produit. Pour garder le total inchangé, on ajoute \(8\) au reste :

Nouvel essai. Trouve le reste de \(-19\) modulo \(6\) avant de poursuivre.

Correction expliquée. \(-19=6\times(-3)-1=6\times(-4)+(6-1)=6\times(-4)+5\) ; le reste est \(5\), qui vérifie \(0\leq5<6\).

Retour à l’erreur. Pour \(-26\) modulo \(8\), le reste est bien \(6\). Les deux écritures \(-26\equiv -2\pmod{8}\) et \(-26\equiv 6\pmod{8}\) sont vraies, mais seule la seconde donne le représentant situé dans l’intervalle des restes. Refais maintenant l’essai guidé en écrivant les deux bornes.

Reprise différée : Sans relire la méthode

Lors d’une prochaine séance, avant toute relecture, décide si \(-73\) et \(14\) sont congrus modulo \(29\). Donne le reste de \(-73\), puis la forme de tous les entiers qui lui sont congrus. Tu peux cacher la suite avec une feuille.

Indice. Calcule \(-73-14\), puis cherche une écriture \(-73=29q+r\) avec \(0\leq r<29\).

Correction expliquée. \(-73-14=-87=29\times(-3)\), donc \(-73\equiv 14\pmod{29}\). L’égalité \(-73=29\times(-3)+14\), avec \(0\leq14<29\), montre que le reste est \(14\). Tous les entiers correspondants s’écrivent \(x=14+29k\), \(k\in\mathbb{Z}\). Réciproquement, \(x-14=29k\) prouve que chaque valeur ainsi obtenue convient.

Critères de réussite. Trouver un témoin entier ; donner un reste non négatif inférieur au module ; écrire une famille, pas seulement quelques exemples ; savoir expliquer pourquoi toutes ses valeurs conviennent.

À retenir : Trois écritures du même fait

Pour \(n\geq2\), « \(a\equiv b\pmod{n}\) », « \(n\mid(a-b)\) » et « \(a\) et \(b\) ont le même reste modulo \(n\) » sont équivalents. Un reste est unique et appartient à \(\{0,\ldots,n-1\}\) ; ses représentants sont en nombre infini. Le module, le caractère entier du multiplicateur et les bornes du reste sont trois contrôles distincts.

Repérage : Ce que signifie réellement le symbole

Avant de continuer, vérifie \(17\equiv 2\pmod{5}\) et \(13\equiv 3\pmod{5}\) à l’aide de différences. Devine ensuite les restes de \(17+13\) et de \(17\times13\) modulo \(5\).

Correction expliquée. \(17-2=15=5\times3\) et \(13-3=10=5\times2\), donc les deux congruences sont vraies. La somme vaut \(30=5\times6\) : son reste est \(0\). Le produit vaut \(221=5\times44+1\) : son reste est \(1\). Le calcul avec les petits représentants donne \(2+3=5\) et \(2\times3=6\), dont les restes sont bien \(0\) et \(1\). Ces essais suggèrent des règles ; ils ne les démontrent pas pour tous les entiers. Si les différences ne t’ont pas convaincu, reprends la définition dans le rappel local.

Théorème : Addition, soustraction et multiplication

Soient \(a,a',b,b'\in\mathbb{Z}\). Si \(a\equiv a'\pmod{n}\) et \(b\equiv b'\pmod{n}\), alors

Démonstration complète. Les hypothèses donnent deux entiers \(u,v\) tels que \(a=a'+nu\) et \(b=b'+nv\).

Pour la somme,

Pour la différence, on distribue le signe moins :

Pour le produit, on écrit les quatre produits avant de regrouper :

Corollaire : Multiplier par un entier, prendre l’opposé

Si \(a\equiv b\pmod{n}\) et \(c\in\mathbb{Z}\), alors \(ca\equiv cb\pmod{n}\). En particulier, \(-a\equiv -b\pmod{n}\).

Démonstration complète. On a \(c\equiv c\pmod{n}\) car \(c-c=0\). Le théorème sur les produits donne donc \(ca\equiv cb\pmod n\). Prendre \(c=-1\) fournit la propriété des opposés. On peut aussi partir de \(a-b=nk\) et écrire \(ca-cb=n(ck)\), avec \(ck\in\mathbb{Z}\).

Théorème : Puissances entières strictement positives

Si \(a,b\in\mathbb{Z}\), \(a\equiv b\pmod{n}\) et \(p\in\mathbb{N}^*\), alors

Démonstration complète. On raisonne par récurrence sur \(p\geq1\). Le principe utilisé est le suivant : on prouve le premier cas, puis que la vérité d’un cas entraîne celle du suivant.

Initialisation. Pour \(p=1\), l’énoncé est exactement l’hypothèse \(a\equiv b\pmod{n}\).

Hérédité. Soit \(p\geq1\). Supposons \(a^p\equiv b^p\pmod{n}\). On dispose aussi de \(a\equiv b\pmod{n}\). En appliquant le théorème sur les produits à ces deux congruences,

Portée. Cette règle ne donne pas une règle sur les exposants négatifs ou les racines. Pour \(p=0\), on doit d’abord s’assurer que les expressions sont définies : nous utilisons \(a^0=1\) pour \(a\neq0\), sans attribuer ici de valeur à \(0^0\).

Représentation intuitive : Changer les étiquettes, garder le reste

Un représentant plus petit est une étiquette de calcul : \(21\) peut être remplacé par \(1\) modulo \(5\), et \(13\) par \(3\). Les opérations prouvées transportent correctement ces étiquettes.

Description : une paire de congruences de même module conduit à une congruence de sommes et à une congruence de produits. Numériquement, \(34=5\times6+4\) et \(273=5\times54+3\).

Limite de l’image. L’étiquette oublie le quotient. Il serait faux de croire que toutes les opérations sur les nombres se transmettent à leurs étiquettes : la division et la prise de racines ne sont pas autorisées sans justification supplémentaire. La preuve du théorème, et non l’image, fixe les opérations permises.

Méthode : Réduire avant les gros calculs

Indices. L’expression comporte des sommes, différences, produits ou puissances positives de grands entiers ; on demande un reste modulo un entier fixé \(n\geq2\).

Premier geste. Écrire séparément un petit représentant de chaque entier, avec le même module. Le reste euclidien est toujours possible ; un représentant négatif proche de \(0\) peut être plus pratique.

1. Remplacer les entiers par ces représentants en utilisant une opération autorisée.

2. Calculer l’expression réduite. On peut réduire de nouveau après chaque multiplication, sans attendre un très grand résultat.

3. Transformer le résultat final en un entier \(r\) tel que \(0\leq r<n\). Une réponse \(-1\) doit devenir \(n-1\) si l’on demande un reste.

Raison. Les théorèmes garantissent que chaque remplacement conserve le reste, puis la transitivité permet d’enchaîner.

Contrôle. Vérifier les signes et le module de chaque ligne. Si le calcul exact reste raisonnable, vérifier ensuite que l’expression initiale moins \(r\) est un multiple de \(n\). Un exemple ne permet pas de conclure à une divisibilité pour une variable entière quelconque.

Exemple de référence : Un reste obtenu sans développer les grands nombres

Déterminons le reste de \(E=47\times83-19^2\) modulo \(12\).

Les égalités \(47=12\times4-1\), \(83=12\times7-1\) et \(19=12+7\) donnent

Contrôle. Ici le calcul exact est possible : \(47\times83=47\times80+47\times3=3760+141=3901\), puis \(E=3901-361=3540=12\times295\). Il confirme le résultat modulaire, sans remplacer la justification des règles employées.

Propriété : Passer à un module diviseur

Soient \(n,d\geq2\) des entiers tels que \(d\mid n\). Alors

Démonstration complète. Il existe un entier \(q\) tel que \(n=dq\). La congruence initiale fournit un entier \(k\) tel que \(a-b=nk\). Ainsi \(a-b=d(qk)\), avec \(qk\in\mathbb{Z}\), donc \(d\) divise \(a-b\).

La réciproque est fausse. Par exemple \(5\equiv 1\pmod{4}\) car \(5-1=4\), mais \(5\) n’est pas congru à \(1\) modulo \(12\) : \(4\) n’est pas un multiple de \(12\). Passer à un module plus grand n’est donc pas une opération automatique.

Théorème de simplification : Diviser simultanément les deux nombres et le module

Pour \(c\in\mathbb{N}^*\), \(m\geq2\) et \(a,b\in\mathbb{Z}\),

Démonstration complète. La congruence de gauche signifie qu’il existe \(k\in\mathbb{Z}\) tel que

Exemple. \(6x\equiv 18\pmod{24}\) équivaut à \(x\equiv 3\pmod{4}\) : on a divisé \(6x\), \(18\) et \(24\) par \(6\). On n’a pas conservé le module \(24\).

Propriété : Une simplification au même module sous condition vérifiée

Si l’on connaît un entier \(u\) tel que \(uc\equiv 1\pmod{n}\), alors

Démonstration complète. À partir de \(ca\equiv cb\pmod n\), on multiplie par \(u\) : \(uca\equiv ucb\pmod n\). Comme \(uc\equiv1\pmod n\), les règles du produit donnent \(uca\equiv a\pmod n\) et \(ucb\equiv b\pmod n\). Par symétrie et transitivité, \(a\equiv b\pmod n\). L’autre sens vient de la multiplication par \(c\), toujours autorisée.

Exemple. Modulo \(8\), on peut simplifier par \(5\) parce que \(5\times5=25=8\times3+1\). Ainsi \(5a\equiv5b\pmod8\) implique bien \(a\equiv b\pmod8\). L’entier \(u=5\) a été trouvé et vérifié ; on ne suppose pas qu’un tel entier existe pour n’importe quel \(c\). La recherche de ces inverses est approfondie dans l’unité sur les équations, mais tout ce qui justifie cette simplification est déjà écrit ici.

Contre-exemples : Trois règles ordinaires qui ne se transportent pas

1. Produit nul. \(2\times3=6\equiv0\pmod6\), mais ni \(2\) ni \(3\) n’est congru à \(0\) modulo \(6\). « Produit congru à zéro » n’impose donc pas « l’un des facteurs congru à zéro ».

2. Division sans condition. \(3\times1\equiv3\times3\pmod6\), puisque \(3-9=-6\) est divisible par \(6\). Pourtant \(1\not\equiv3\pmod6\), puisque \(1-3=-2\) ne l’est pas. La non-nullité ordinaire de \(3\) ne suffit pas pour le simplifier en conservant le module.

3. Retour depuis les carrés. \(2^2=4\equiv9=3^2\pmod5\), mais \(2\not\equiv3\pmod5\). Le théorème sur les puissances va de la base vers la puissance, pas automatiquement en sens inverse.

Dans chaque cas, un seul exemple autorisé suffit à réfuter la règle générale proposée. Il ne réfute pas les théorèmes démontrés : leurs conclusions sont différentes ou leurs conditions ne sont pas satisfaites.

Essai guidé : Réduire une différence

Trouve le reste de \(39^2-4\times17\) modulo \(7\). Commence par \(39\equiv\ldots\pmod7\) et \(17\equiv\ldots\pmod7\).

Correction expliquée. \(39=7\times5+4\) et \(17=7\times2+3\). Donc

À toi : Choisir tes représentants

Calcule le reste de \(F=31\times46+22^3\) modulo \(9\). Indique les règles utilisées ; ne commence pas par calculer \(22^3\) en écriture décimale.

Indice. Les représentants \(4\), \(1\) et \(4\) simplifient les trois nombres. Le résultat réduit doit encore être ramené entre \(0\) et \(8\).

Correction expliquée. \(31=9\times3+4\), \(46=9\times5+1\) et \(22=9\times2+4\). Par compatibilité avec le produit, la puissance positive et la somme,

Critères de réussite. Même module à chaque étape ; trois réductions justifiées ; aucune modification de l’exposant \(3\) ; reste final dans l’intervalle autorisé.

Justifier : Pourquoi ne peut-on pas simplement barrer le facteur ?

Un élève écrit : « \(3x\equiv3y\pmod6\), donc \(x\equiv y\pmod6\), car \(3\neq0\). » Explique l’erreur et donne une conclusion toujours correcte.

Correction expliquée. La non-nullité permet de diviser une égalité par \(3\), mais la congruence signifie \(3x-3y=6k\), pour un entier \(k\). En divisant cette égalité par \(3\neq0\), on obtient \(x-y=2k\), donc \(x\equiv y\pmod2\). Le module devient \(2\), pas \(6\). Le choix \(x=1,y=3\) est un contre-exemple à la conclusion de l’élève : \(3-9=-6\) est divisible par \(6\), mais \(1-3=-2\) ne l’est pas.

Critères de réussite. Distinguer égalité et congruence ; afficher le témoin entier ; simplifier le coefficient et le module ; donner un contre-exemple vérifié si l’on réfute l’affirmation initiale.

Variation : Choisir le module auquel on peut conclure

De \(18\equiv6\pmod{12}\), peut-on déduire une congruence modulo \(4\) ? Modulo \(8\) ? Peut-on affirmer que deux congruences modulo \(2\) et modulo \(6\) se combinent toujours en une congruence modulo \(12\) ?

Correction expliquée. \(4\mid12\), donc la première déduction est valide ; directement, \(18-6=12=4\times3\). En revanche \(8\) ne divise pas \(12\) et, ici, \(18-6=12\) n’est pas divisible par \(8\) : la deuxième est fausse. Enfin \(7\equiv1\pmod2\) et \(7\equiv1\pmod6\), car \(7-1=6\) est divisible par \(2\) et \(6\). Mais \(7\not\equiv1\pmod{12}\). Multiplier les modules n’est donc pas une règle générale. Nous n’en avons énoncé aucune.

Réparation : Une simplification qui a perdu des solutions

Première erreur. À partir de \(4x\equiv8\pmod{12}\), on annonce \(x\equiv2\pmod{12}\). Or \(x=5\) vérifie la première congruence, car \(4\times5-8=12\), mais pas la seconde, car \(5-2=3\) n’est pas un multiple de \(12\).

Rappel. On doit traduire la congruence en égalité : \(4x-8=12k\), \(k\in\mathbb{Z}\). En divisant toute l’égalité par \(4\neq0\), on obtient \(x-2=3k\), donc \(x\equiv2\pmod3\).

Exemple plus simple corrigé. \(2x\equiv0\pmod4\) signifie \(2x=4k\). La division par \(2\) donne \(x=2k\), soit \(x\equiv0\pmod2\). Tous les entiers pairs conviennent, pas seulement les multiples de \(4\).

Nouvel essai. Simplifie correctement \(3x\equiv6\pmod{15}\).

Correction expliquée. On a successivement \(3x-6=15k\), \(3(x-2)=15k\), puis \(x-2=5k\) après division par \(3\neq0\). La réponse est \(x\equiv2\pmod5\), c’est-à-dire \(x=2+5k\), \(k\in\mathbb{Z}\).

Retour. La question initiale a pour solutions \(x=2+3k\), \(k\in\mathbb{Z}\). En effet \(4(2+3k)-8=8+12k-8=12k\). Cette substitution contrôle le sens réciproque. Reprends ensuite la justification précédente sans regarder sa réponse.

Reprise différée : Calculer et contrôler une condition

À reprendre lors d’une autre séance, avant relecture : déterminer le reste de \((-16)\times35+11^2\) modulo \(9\), puis simplifier correctement \(6x\equiv12\pmod{30}\).

Indice. Pour le calcul, \(-16\equiv2\pmod9\) et \(35\equiv-1\pmod9\). Pour la seconde question, traduis en une égalité avec un témoin entier.

Correction expliquée. \(11\equiv2\pmod9\), donc

Critères de réussite. Vérifier séparément les réductions et le reste ; conserver les exposants ; dire quel nombre non nul est divisé ; changer le module lorsqu’il faut le changer ; contrôler la réciproque par substitution.

À retenir : Les opérations permises ont des conditions

Au même module, on peut additionner, soustraire, multiplier et élever à une puissance entière strictement positive. Un représentant peut être négatif ; un reste final ne l’est pas. On peut passer à un module diviseur. On ne divise ni n’extrait une racine automatiquement. Une simplification est justifiée soit par un changement simultané du module, soit par un multiplicateur vérifié qui ramène le coefficient à \(1\) modulo le module.

Repérage : La même opération sur la base et l’exposant ?

Sans lire la correction, répondre aux deux questions :

1. \(29\equiv1\pmod7\) permet-il de calculer le reste de \(29^5\) modulo \(7\) ?

2. Puisque \(6\equiv1\pmod5\), peut-on affirmer que \(2^6\equiv2^1\pmod5\) ?

Correction expliquée. Pour la première question, la compatibilité avec la puissance d’exposant \(5\) donne \(29^5\equiv1^5=1\pmod7\) : le reste est \(1\). Pour la seconde, calculons : \(2^6=64=5\times12+4\), tandis que \(2^1=2\) a pour reste \(2\). L’affirmation est fausse. Le théorème permet de remplacer la base par un entier congru, mais il ne permet pas de remplacer l’exposant par un entier congru au même module. Si tu as appliqué indistinctement la même règle aux deux, garde cette distinction à l’esprit : la réparation finale y revient.

Propriété : Trois bases particulièrement simples

Soit \(m\geq2\). Pour un entier \(a\) et un exposant \(p\geq1\) :

• si \(a\equiv0\pmod m\), alors \(a^p\equiv0\pmod m\) ;

• si \(a\equiv1\pmod m\), alors \(a^p\equiv1\pmod m\) ;

• si \(a\equiv-1\pmod m\), alors \(a^p\equiv1\pmod m\) pour \(p\) pair et \(a^p\equiv-1\pmod m\) pour \(p\) impair.

Démonstration complète. La compatibilité avec la puissance positive ramène aux puissances de \(0\), \(1\) et \(-1\). Les deux premières valent respectivement \(0\) et \(1\). Pour la troisième, si \(p=2q\), alors \((-1)^p=\bigl((-1)^2\bigr)^q=1\). Si \(p=2q+1\), alors \((-1)^p=\bigl((-1)^2\bigr)^q(-1)=-1\). Ici \(q\) est un entier naturel. Le représentant \(-1\) correspond au reste \(m-1\), car \(-1=m\times(-1)+(m-1)\) et \(0\leq m-1<m\).

Exemple. \(2029=7\times290-1\), donc \(2029\equiv-1\pmod7\). L’exposant \(2031=2\times1015+1\) est impair :

Théorème : Réduire l’exposant grâce à un retour à 1

Soient \(a\in\mathbb{Z}\setminus\{0\}\), \(m\geq2\) et \(T\in\mathbb{N}^*\). Supposons que l’on a établi \(a^T\equiv1\pmod m\). Pour tout \(p\in\mathbb{N}\), si

Démonstration complète. Les lois des puissances donnent

Si \(r=0\), le dernier facteur est \(a^0=1\) ; ce cas n’est ni omis ni remplacé par \(0\). La base \(a\) est non nulle, donc cette écriture est définie.

Point décisif. On réduit la base modulo \(m\), mais on réduit l’exposant modulo \(T\), dont le rôle vient de \(a^T\equiv1\pmod m\). Les nombres \(m\) et \(T\) sont généralement différents. Le théorème ne demande pas que \(T\) soit le plus petit retour possible.

Lemme : Comment passer d’un reste au suivant

Soit \(a\neq0\) un entier, et \(R_p\) le reste de \(a^p\) modulo \(m\geq2\), pour \(p\in\mathbb{N}\). Le reste \(R_{p+1}\) s’obtient en multipliant \(R_p\) par \(a\), puis en prenant le reste modulo \(m\).

Démonstration complète. Écrivons \(a^p=mq+R_p\), puis la division de \(aR_p\) : \(aR_p=ms+t\), avec \(0\leq t<m\). On obtient

Ce lemme justifie la construction d’un tableau de restes sans calculer toutes les puissances et explique pourquoi un même reste retrouvé donne ensuite les mêmes suivants.

Représentation intuitive : Un circuit de restes, pas un circuit de nombres

Pour multiplier successivement par \(3\) modulo \(11\), les restes suivent le circuit ci-dessous.

Description : en partant du reste de \(3^0\), soit \(1\), les cinq étapes donnent \(1,3,9,5,4\), puis reviennent à \(1\). Les produits \(9\times3=27\), \(5\times3=15\) et \(4\times3=12\) sont remplacés par leurs restes \(5\), \(4\) et \(1\) modulo \(11\).

L’image permet de compter une position dans un cycle de longueur \(5\). Elle ne dit pas que les puissances elles-mêmes se répètent : \(3^5=243\) n’est pas égal à \(1\). Elle ne prouve pas non plus que toute autre base reviendra à \(1\). Ces conditions doivent être vérifiées dans chaque situation.

Méthode : Un grand exposant, un petit tableau

Indices. On demande le reste d’une puissance entière très grande ; la base n’est pas directement congrue à \(0\), \(1\) ou \(-1\).

Premier geste. Réduire la base au module demandé et noter celui-ci. Traiter l’exposant \(0\) séparément avant de remplacer une base par \(0\).

1. Construire les restes des premières puissances, par multiplication et réduction à chaque étape.

2. Si un retour à \(1\) est obtenu à un exposant \(T>0\), écrire l’égalité ou le calcul qui prouve \(a^T\equiv1\pmod m\). Cela justifie l’utilisation d’un cycle, au-delà des quelques lignes observées.

3. Diviser l’exposant \(p\) par \(T\) : \(p=Tq+r\), \(0\leq r<T\). Ne pas le diviser automatiquement par \(m\).

4. Utiliser \(a^p\equiv a^r\pmod m\), puis lire le reste de \(a^r\). Pour \(r=0\), il vaut \(1\).

Raison. Le théorème du retour à \(1\) transforme un exposant immense en un exposant borné ; le tableau localise ensuite le bon reste.

Contrôle. Vérifier le retour, la division de l’exposant et le rang lu. Si aucun retour à \(1\) n’est obtenu, ne pas inventer de période : un autre type de répétition peut apparaître, comme on le verra ci-dessous. Les carrés successifs offrent également une autre voie.

Exemple de référence : Deux réductions qui n’ont pas le même module

Cherchons le reste de \(36^{2027}\) modulo \(11\).

1. Réduction de la base. \(36=11\times3+3\), donc \(36\equiv3\pmod{11}\). Puisque \(2027\geq1\), on en déduit \(36^{2027}\equiv3^{2027}\pmod{11}\).

2. Recherche d’un retour. On multiplie le reste précédent par \(3\) :

Ainsi \(3^5\equiv1\pmod{11}\) ; on peut aussi le vérifier par \(3^5=243=11\times22+1\).

3. Réduction de l’exposant. On divise \(2027\) par \(5\), et non par \(11\) :

Contrôle. Le schéma à retenir n’est pas « prendre deux fois le reste modulo \(11\) ». Il est : base \(36\) modulo \(11\) ; exposant \(2027\) modulo \(5\) ; réponse finale modulo \(11\). Pour un exposant \(2025=5\times405\), on aurait obtenu \(1\), pas \(0\).

Propriété : Une répétition peut commencer après quelques termes

Soit \(a\neq0\) un entier. Si \(a^i\equiv a^j\pmod m\) pour deux entiers \(0\leq i<j\), alors, pour tout entier \(p\geq i\),

Démonstration complète. On a \(p-i\geq0\). Multiplions la congruence initiale par l’entier \(a^{p-i}\) :

Pourquoi une répétition finit-elle par arriver ? Chaque reste appartient à la liste de \(m\) nombres \(0,1,\ldots,m-1\). Parmi les \(m+1\) restes de \(a^0,a^1,\ldots,a^m\), deux au moins sont égaux : sinon on aurait \(m+1\) valeurs distinctes dans une liste qui n’en contient que \(m\). La propriété précédente établit alors une répétition à partir d’un certain rang.

Exemple et vocabulaire : La prépériode des puissances de 2 modulo 8

Les restes de \(2^p\) modulo \(8\) sont

On ne doit donc pas chercher à tout prix un entier \(T>0\) tel que \(2^T\equiv1\pmod8\) : il n’en existe pas. En effet les exposants \(1\) et \(2\) donnent les restes \(2\) et \(4\) ; tous les exposants suivants donnent \(0\).

Méthode : Les carrés successifs, même sans période connue

Quand ? Si l’exposant est grand et qu’aucune courte période n’est connue. On peut travailler à la main sur quelques étapes, puis programmer la même idée.

Premier geste. Décomposer l’exposant en somme de puissances de \(2\), puis préparer les restes de \(a,a^2,a^4,a^8,\ldots\) en élevant chaque reste au carré.

Pourquoi ? Si \(a^{2^j}\equiv r_j\pmod m\), alors \(a^{2^{j+1}}=(a^{2^j})^2\equiv r_j^2\pmod m\). Et une somme d’exposants correspond à un produit de puissances. Tous les gestes sont donc couverts par les règles démontrées.

Exemple complet : \(7^{117}\) modulo \(13\). L’exposant se décompose en

On ne multiplie que les lignes correspondant aux exposants retenus :

Contrôle. Une autre voie confirme ce calcul : \(7^3\equiv10\times7=70\equiv5\pmod{13}\) ; donc \(7^6\equiv25\equiv-1\pmod{13}\). Comme \(117=6\times19+3\), on obtient \(7^{117}\equiv(-1)^{19}\times5=-5\equiv8\pmod{13}\). La méthode des carrés n’avait pas besoin de connaître ce raccourci à l’avance.

Essai guidé : Un carré qui donne moins un

Trouve le reste de \(5^{2026}\) modulo \(13\). Commence par \(5^2\), puis \(5^4\). Quel entier doit diviser l’exposant ?

Correction expliquée. \(5^2=25=13\times2-1\), donc \(5^2\equiv-1\pmod{13}\). En élevant au carré, \(5^4\equiv(-1)^2=1\pmod{13}\). On divise alors \(2026\) par \(4\) : \(2026=4\times506+2\). Ainsi

À toi : Construire puis utiliser le cycle

Détermine le reste de \(14^{1001}\) modulo \(9\). Justifie un retour à \(1\) et explique quel reste de l’exposant tu utilises.

Indice. La base se réduit à \(5\). Ses premières puissances conduisent à \(5^3\equiv-1\pmod9\).

Correction expliquée. \(14\equiv5\pmod9\), donc \(14^{1001}\equiv5^{1001}\pmod9\). On calcule \(5^2=25\equiv7\pmod9\), puis \(5^3\equiv7\times5=35\equiv8\equiv-1\pmod9\). En élevant au carré, \(5^6\equiv1\pmod9\).

La division de l’exposant par \(6\) donne \(1001=6\times166+5\). Ainsi

Critères de réussite. Réduire la base modulo \(9\) ; établir le retour à \(1\) ; réduire l’exposant modulo \(6\), pas modulo \(9\) ; traiter les produits et le représentant négatif ; conclure avec le reste euclidien.

Justifier : Ce qui prouve la répétition

Un tableau de six premières puissances suffit-il, à lui seul, à garantir que la suite des restes se répétera toujours selon le motif observé ? Explique ce qu’il faut ajouter.

Correction expliquée. Une réponse possible est : « Un nombre fini d’essais ne prouve pas une propriété à tous les rangs. Si le tableau donne \(a^T\equiv1\pmod m\), je dois le vérifier puis écrire, pour chaque \(p=Tq+r\), \(a^p=(a^T)^q a^r\equiv a^r\pmod m\). Cette identité prouve la répétition pour tous les exposants. Si la répétition commence plus tard, il faut repérer deux rangs \(i<j\) de même reste, puis multiplier leur congruence par \(a^{p-i}\) pour les rangs \(p\geq i\). »

Critères de réussite. Distinguer observation finie et preuve générale ; citer un retour vérifié ou une répétition de deux états ; indiquer le domaine des rangs où la conclusion est valable ; ne pas utiliser un théorème de Fermat ou de Gauss non enseigné ici.

Variation : Exposant zéro et régime qui commence plus tard

1. Un élève remplace \(11\) par \(0\) modulo \(11\) et annonce que \(11^0\) a pour reste \(0\). Où est l’erreur ?

2. Un autre voit les trois premiers restes \(1,2,4\) des puissances de \(2\) modulo \(8\), puis suppose que ces trois valeurs forment un cycle. Quel calcul réfute sa conjecture ? Que vaut le reste de \(2^{2026}\) ?

Correction expliquée. Pour la première question, \(11\neq0\), donc \(11^0=1\) et son reste modulo \(11\) est \(1\). Le remplacement aurait produit \(0^0\), qui n’est pas défini dans notre convention ; le théorème de compatibilité utilisé pour réduire une base était formulé pour un exposant strictement positif. Il fallait traiter \(p=0\) avant cette réduction.

Pour la seconde, \(2^3=8\) a pour reste \(0\), et non \(1\) : le cycle conjecturé est faux. Comme \(2026\geq3\), \(2^{2026}=8\times2^{2023}\) est divisible par \(8\) ; son reste est \(0\). Ce changement de situation oblige à vérifier où commence la répétition, et pas seulement à changer les nombres d’un même calcul.

Réparation : L’exposant n’a pas le module de la base

Première erreur. « Pour calculer \(3^{17}\) modulo \(7\), je réduis \(17\) modulo \(7\). Comme \(17=7\times2+3\), le reste est celui de \(3^3\), soit \(6\). » Aucune règle démontrée n’autorise cette réduction de l’exposant.

Rappel. Une réduction de l’exposant utilise une période établie. Le module de la puissance et cette période n’ont pas le même rôle.

Exemple plus simple corrigé. Pour \(2^5\) modulo \(3\), \(2\equiv-1\pmod3\) et \(5\) est impair. Ainsi \(2^5\equiv-1\equiv2\pmod3\). Réduire \(5\) modulo \(3\) donnerait abusivement \(2^2\), de reste \(1\) ; c’est une erreur. La parité, c’est-à-dire le reste modulo \(2\), était ici pertinente parce que \((-1)^2=1\).

Nouvel essai. Calcule \(2^8\) modulo \(5\) en justifiant la réduction de l’exposant.

Correction expliquée. \(2^4=16\equiv1\pmod5\) et \(8=4\times2+0\). Donc \(2^8=(2^4)^2\equiv1\pmod5\). Le reste nul de l’exposant modulo \(4\) conduit à la puissance \(2^0=1\), pas à un reste final nul.

Retour à la première erreur. On calcule \(3^3=27\equiv-1\pmod7\), donc \(3^6\equiv1\pmod7\). L’exposant doit être réduit modulo \(6\) : \(17=6\times2+5\). Ainsi

Reprise différée : Le bon module au bon endroit

Lors d’une prochaine séance, sans relire l’exemple, détermine le reste de \(18^{123}\) modulo \(7\). Justifie une période utilisable et explique ce que signifie un reste nul lors de la division de l’exposant.

Indice. La base \(18\) est congrue à \(4\) modulo \(7\) ; calcule \(4^3\).

Correction expliquée. \(18=7\times2+4\), donc \(18^{123}\equiv4^{123}\pmod7\). Or \(4^3=64=7\times9+1\), d’où \(4^3\equiv1\pmod7\). La division \(123=3\times41+0\) donne

Critères de réussite. Identifier les deux modules de calcul ; prouver le retour à \(1\) ; détailler la décomposition de l’exposant ; contrôler le cas \(r=0\) ; fournir un reste entre \(0\) et \(6\).

À retenir : Une période doit être prouvée

Commence par réduire la base. Pour \(p\geq1\), les représentants \(0\), \(1\) et \(-1\) sont immédiatement utiles. Si \(a^T\equiv1\pmod m\), on réduit l’exposant modulo \(T\) ; si la répétition commence plus tard, on respecte son rang de départ. Un tableau doit être accompagné d’un argument de répétition. Les carrés successifs sont une alternative qui ne nécessite pas de connaître une période. Enfin, l’exposant \(0\) se traite avant toute opération risquant de faire apparaître \(0^0\).

Repérage : Tester n’est pas encore tout résoudre

Sans consulter la réponse, indique si \(x=2\) puis \(x=3\) vérifient \(3x\equiv 1\pmod{5}\). La valeur \(x=7\) convient-elle aussi ?

Correction expliquée. Pour \(x=2\), \(3x-1=6-1=5=5\times1\) : oui. Pour \(x=3\), \(3x-1=9-1=8\), qui n’est pas multiple de \(5\) : non. Pour \(x=7\), \(21-1=20=5\times4\) : oui. Les solutions ne se limitent donc pas à un entier. Si tu avais divisé \(1\) par \(3\) comme dans une équation réelle, reprends le rappel : on demande ici que la différence soit multiple de \(5\), pas qu’elle soit nulle.

Définition : Solution et classe de solutions

Résoudre dans \(\mathbb{Z}\) une congruence, c’est décrire tous les entiers qui la vérifient. Une écriture comme \(x\equiv r\pmod{m}\) désigne tous les nombres

Théorème : Un tableau fini peut donner toutes les solutions

Soient \(a,b\in\mathbb{Z}\) et \(m\geq2\). Pour résoudre \(ax\equiv b\pmod{m}\), il suffit de tester les \(m\) restes \(r=0,1,\ldots,m-1\). Si les restes retenus sont \(r_1,\ldots,r_s\), les solutions sont exactement les entiers de la forme \(x=r_i+mk\), avec \(k\in\mathbb{Z}\) et l’un des restes retenus \(r_i\).

Démonstration complète. Pour un entier \(x\), écrivons \(x=mq+r\) avec \(0\leq r<m\). Alors

Le même principe fonctionne pour \(x^2\) : si \(x=mq+r\), alors

Méthode : La voie de référence : un tableau exhaustif

Quand ? Pour un petit module, notamment si aucune simplification sûre n’apparaît.

Premier geste. Écrire le module et le reste recherché ; ramener le second membre à un reste entre \(0\) et \(m-1\) si nécessaire.

1. Placer tous les restes \(0,1,\ldots,m-1\) sur la première ligne.

2. Calculer le reste de l’expression pour chaque colonne : par exemple celui de \(ar\) pour une congruence linéaire.

3. Retenir toutes les colonnes qui donnent le reste demandé.

4. Écrire les solutions \(x=r+mk\), \(k\in\mathbb{Z}\), pour chaque reste retenu. Traduire ensuite une éventuelle borne imposée à \(x\).

Pourquoi ? Le théorème précédent transforme une recherche sur une infinité d’entiers en une recherche finie, sans perdre d’information.

Contrôle. Substituer un représentant de chaque classe dans l’énoncé initial et vérifier que le tableau a bien \(m\) colonnes de restes. Une seule valeur trouvée ne suffit pas.

Exemple de référence : Deux classes, une infinité de solutions

Résolvons \(4x\equiv 6\pmod{10}\) dans \(\mathbb{Z}\).

Par exemple, pour \(r=3\), \(4r=12=10\times1+2\) ; pour \(r=4\), \(16=10\times1+6\) ; pour \(r=9\), \(36=10\times3+6\). La dernière ligne prend la valeur \(6\) exactement sous \(4\) et \(9\). Ainsi

On peut aussi décrire la réunion par \(x=4+5k\), \(k\in\mathbb{Z}\) : si \(k\) est pair, on retrouve la première classe ; s’il est impair, la seconde. C’est une classe modulo \(5\), et toujours deux classes modulo \(10\).

Définition : Inverse modulo un entier

Soient \(a\in\mathbb{Z}\) et \(m\geq2\). Un entier \(c\) est un inverse de \(a\) modulo \(m\) lorsque

Propriété : Un inverse, quand il existe, est unique modulo le module

Si \(c\) et \(d\) sont deux inverses de \(a\) modulo \(m\), alors \(c\equiv d\pmod{m}\). Il y a donc un unique inverse parmi les restes \(0,\ldots,m-1\).

Démonstration complète. Les hypothèses donnent \(ac\equiv 1\pmod{m}\) et \(ad\equiv 1\pmod{m}\). En multipliant la deuxième congruence par \(c\), puis la première par \(d\), on obtient

Théorème : Résoudre grâce à un inverse vérifié

Supposons que \(c\) soit un inverse de \(a\) modulo \(m\). Alors, pour tout \(x\in\mathbb{Z}\),

Démonstration complète. Sens direct. De \(ax\equiv b\pmod{m}\), on déduit, en multipliant par \(c\), \(cax\equiv cb\pmod{m}\). Comme \(ca\equiv 1\pmod{m}\), on a aussi \(cax\equiv x\pmod{m}\) ; ainsi \(x\equiv cb\pmod{m}\).

Réciproque. De \(x\equiv cb\pmod{m}\), on déduit \(ax\equiv acb\pmod{m}\) en multipliant par \(a\). Or \(acb\equiv b\pmod{m}\), puisque \(ac\equiv 1\pmod{m}\). On retrouve \(ax\equiv b\pmod{m}\).

On a multiplié par un entier dont le produit avec \(a\) vaut \(1\) modulo \(m\). On n’a pas appliqué une division ordinaire à une congruence.

Méthode : La voie rapide : chercher puis contrôler un inverse

Conditions : le coefficient \(a\) possède un inverse modulo \(m\) ; ici on doit le trouver et le vérifier, sans supposer un théorème de chapitre ultérieur.

Premier geste. Calculer les restes de \(a\times0,a\times1,\ldots,a\times(m-1)\) jusqu’à trouver \(1\), ou constater après la liste complète que \(1\) n’apparaît pas.

1. Nommer l’inverse \(c\) et écrire \(ac=1+mh\) avec \(h\in\mathbb{Z}\).

2. Multiplier les deux membres de la congruence par \(c\).

3. Réduire \(cb\) à son reste \(r\), puis conclure \(x=r+mk\), \(k\in\mathbb{Z}\).

Contrôle. Vérifier dans la congruence de départ. Si aucun inverse n’existe, ne pas déclarer automatiquement l’équation impossible : l’exemple \(4x\equiv6\pmod{10}\) possède deux classes de solutions alors que \(4\) n’a pas d’inverse modulo \(10\). Revenir à la méthode du tableau.

Exemple de référence : Un inverse justifie les deux sens

Résolvons \(3x\equiv 4\pmod{7}\). Le produit \(3\times5=15=1+7\times2\) vérifie que \(5\) est un inverse de \(3\) modulo \(7\). Alors

Exemple : Une congruence non linéaire et une impossibilité

Résolvons successivement \(x^2\equiv 1\pmod{8}\) et \(x^2\equiv 3\pmod{8}\). Le tableau est exhaustif :

Par exemple, \(5^2=25=8\times3+1\) et \(6^2=36=8\times4+4\). Les restes \(1,3,5,7\) conviennent pour la première congruence : ses solutions sont tous les entiers impairs. Pour la seconde, aucun reste de carré ne vaut \(3\), donc il n’y a aucune solution entière.

Piège. Écrire \(x^2-1=(x-1)(x+1)\) ne permet pas d’affirmer que \(x\equiv1\pmod8\) ou \(x\equiv-1\pmod8\). Pour \(x=3\), on a \((x-1)(x+1)=2\times4=8\), divisible par \(8\), bien que ni \(2\) ni \(4\) ne soit divisible par \(8\). Le tableau garde correctement la solution \(x=3\).

Essai guidé : Un inverse puis toutes les solutions

Résous \(5x\equiv 3\pmod{8}\). Commence par calculer \(5\times5\) ; réduis ensuite \(5\times3\) modulo \(8\) et écris une formule pour toutes les solutions.

Correction expliquée. \(5\times5=25=1+8\times3\) : \(5\) est son propre inverse modulo \(8\). En multipliant par cet inverse,

À toi : Deux recherches, sans méthode annoncée

Produis une solution rédigée avant de consulter l’aide.

1. Trouve les entiers \(x\) tels que \(0\leq x\leq50\) et \(7x\equiv 5\pmod{12}\).

2. Existe-t-il un entier \(y\) tel que \(6y\equiv 5\pmod{9}\) ? Justifie sans te contenter de quelques essais.

Indice. Pour la première question, calcule \(7\times7\). Pour la seconde, une table des neuf restes suffit ; on peut aussi comparer la divisibilité par \(3\) des deux membres d’une égalité entière.

Correction expliquée. 1. \(7\times7=49=1+12\times4\), donc \(7\) est un inverse de \(7\) modulo \(12\). La congruence équivaut à

2. Si une solution existait, on aurait \(6y-5=9k\) pour un entier \(k\). Alors \(5=6y-9k=3(2y-3k)\) serait divisible par \(3\), ce qui est faux. Il n’existe donc aucune solution. On peut vérifier l’exhaustivité par les restes de \(6r\) pour \(r=0,\ldots,8\) : \(0,6,3,0,6,3,0,6,3\) ; aucun n’est \(5\).

Critères de réussite. Inverse vérifié ou autre voie complète ; paramètre entier et bornes effectivement traitées ; impossibilité prouvée pour tous les entiers ; contrôle dans la congruence initiale.

Justification personnelle : Pourquoi le tableau ne laisse-t-il rien de côté ?

Explique, en trois à cinq phrases, pourquoi tester seulement les dix restes a permis de résoudre \(4x\equiv6\pmod{10}\) pour tous les entiers, y compris négatifs. Ta réponse doit citer la division euclidienne, la dépendance au reste et le retour vers les entiers.

Correction expliquée. Une réponse possible est : « Tout entier \(x\), même négatif, s’écrit \(x=10q+r\) avec \(0\leq r<10\). Alors \(4x=40q+4r\), donc \(4x\) et \(4r\) ont le même reste modulo \(10\). Le tableau teste tous les \(r\) possibles et retient seulement \(4\) et \(9\). Réciproquement, tout entier \(4+10q\) ou \(9+10q\) vérifie la congruence, puisque le terme ajouté apporte un multiple de \(10\). »

Critères de réussite. Mention des dix restes et pas seulement « on a essayé » ; prise en compte des négatifs ; justification du calcul de l’expression ; les deux sens, pas la seule nécessité.

Variation : Le second membre change la réponse

Compare les congruences \(6x\equiv 3\pmod{8}\) et \(6x\equiv 4\pmod{8}\). On cherche bien des entiers dans les deux cas.

Correction expliquée. Dans la première, \(6x-3\) est impair, alors qu’un multiple de \(8\) est pair : aucune solution.

Dans la deuxième, il existe \(k\in\mathbb{Z}\) tel que \(6x-4=8k\). En divisant cette égalité entière par \(2\), on obtient \(3x-2=4k\). Réciproquement, multiplier cette dernière égalité par \(2\) redonne la première. Ainsi

Pour vérifier : \(6(2+4k)-4=8+24k=8(1+3k)\). Un coefficient sans inverse modulo \(8\) peut donc conduire soit à aucune classe, soit à plusieurs classes, suivant le second membre.

Réparation : Ne pas perdre des solutions en simplifiant

Première erreur. Pour \(4x\equiv6\pmod{10}\), Noah écrit \(2x\equiv3\pmod{10}\), puis annonce « impossible : un nombre pair ne peut pas être congru à \(3\) modulo \(10\) ». L’erreur est la première transformation : le module est resté inchangé alors que l’égalité qui définit la divisibilité a été divisée.

Rappel. Pour simplifier sûrement, revenir à \(A=mk\) avec \(k\) entier. Diviser tous les termes de cette égalité par un même facteur non nul, puis réinterpréter la nouvelle égalité.

Exemple plus simple corrigé. \(2x\equiv2\pmod4\) signifie \(2x-2=4k\), donc \(x-1=2k\). Les solutions sont \(x=1+2k\) : tous les impairs. Garder le module \(4\) aurait perdu la solution \(x=3\), pourtant \(2\times3-2=4\).

Nouvel essai. Résous \(6x\equiv6\pmod9\) en revenant à une égalité entière avant de simplifier.

Correction expliquée. \(6x-6=9k\) équivaut à \(2x-2=3k\), en divisant les deux membres par \(3\ne0\). Ainsi \(2x\equiv2\pmod3\). Comme \(2\times2=4\equiv1\pmod3\), on obtient \(x\equiv4\equiv1\pmod3\), donc \(x=1+3k\), \(k\in\mathbb{Z}\). Contrôle : \(6(1+3k)-6=18k=9(2k)\). Il y a trois classes modulo \(9\) : \(1,4,7\).

Retour à la question initiale. \(4x-6=10k\) équivaut à \(2x-3=5k\), donc à \(2x\equiv3\pmod5\). L’inverse de \(2\) modulo \(5\) est \(3\), car \(2\times3=6\equiv1\pmod5\). D’où \(x\equiv9\equiv4\pmod5\) : on retrouve exactement \(x=4+5k\), et les deux classes \(4,9\) modulo \(10\). Refais ce retour sans aide.

Reprise différée : À refaire sans relire la méthode

Plus tard, sur une feuille vierge, résous \(5x\equiv2\pmod9\), puis garde les solutions comprises entre \(-12\) et \(15\). Explique pourquoi ta liste est complète.

Indice. Cherche un petit multiplicateur de \(5\) dont le produit donne le reste \(1\) modulo \(9\).

Correction expliquée. \(5\times2=10=1+9\), donc \(2\) est un inverse vérifié de \(5\). La congruence équivaut à \(x\equiv2\times2\equiv4\pmod9\), soit \(x=4+9k\), \(k\in\mathbb{Z}\). Ensuite

Si tu n’as trouvé que \(4\), reprends la définition d’une classe. Si tu as divisé directement par \(5\), refais la réparation. Une reprise prévue n’est pas une réussite acquise : garde ta production pour comparer les étapes réellement maîtrisées.

À retenir : Résoudre, c’est produire un ensemble exact

• Tableau complet : toutes les classes possibles, puis toutes les solutions \(x=r+mk\).

• Inverse : vérifier \(ac\equiv1\pmod m\) avant de multiplier ; alors \(ax\equiv b\pmod m\) équivaut à \(x\equiv cb\pmod m\).

• Un inverse est unique modulo \(m\), pas comme entier sans borne.

• Sans inverse, une congruence peut avoir aucune ou plusieurs classes : revenir au tableau ou à l’égalité entière.

• Un produit nul modulo un entier ne donne pas automatiquement un facteur nul ; une simplification peut changer le module.

• Une condition d’intervalle se traite après la classe, par un encadrement du paramètre entier.

Repérage : Quel rôle joue chaque chiffre ?

Écris \(2016\) comme « cent fois un entier plus un entier entre \(0\) et \(99\) ». Est-il divisible par \(4\) ? Par \(9\) ? Justifie avant de lire.

Correction expliquée. \(2016=100\times20+16\). Le nombre \(100\times20\) est divisible par \(4\), et \(16=4\times4\) aussi : leur somme est divisible par \(4\). Pour \(9\), la somme des chiffres est \(2+0+1+6=9\) ; le test connu donne une réponse positive. Nous allons démontrer pourquoi ce dernier test fonctionne. Si tu avais écrit \(2016=2\times0\times1\times6\), reprends immédiatement l’écriture de position ci-dessous : une suite de chiffres ne désigne pas leur produit.

Définition et notation : L’écriture décimale est une somme de positions

Un chiffre est l’un des entiers \(0,1,\ldots,9\). Si l’écriture d’un entier naturel est \(N=\overline{a_s a_{s-1}\ldots a_1a_0}\), cela signifie

Par exemple

Théorème : Quand les derniers chiffres suffisent

Soient \(s\geq1\) et \(d\geq2\) deux entiers tels que \(d\mid10^s\). Décomposons \(N\) sous la forme

Démonstration complète. Puisque \(d\mid10^s\), il existe un entier \(h\) tel que \(10^s=dh\). Ainsi \(N-B=dhA\) est divisible par \(d\). Si \(d\mid B\), la somme \(N=dhA+B\) est divisible par \(d\). Réciproquement, si \(d\mid N\), la différence \(B=N-dhA\) est divisible par \(d\). Les deux sens sont établis.

Nous avons même \(N\equiv B\pmod d\) : ce test conserve ici le reste. L’hypothèse \(d\mid10^s\) est essentielle ; garder seulement le chiffre des unités ne permet pas de tester la divisibilité par \(3\).

Corollaire : Les critères des derniers chiffres

Le théorème donne les critères suivants, car chaque diviseur indiqué divise la puissance de \(10\) de sa ligne.

Démonstration complète. \(2,5,10\) divisent \(10\) ; \(4,25,100\) divisent \(100\) ; \(8,125,1000\) divisent \(1000\). On applique le théorème avec respectivement \(s=1,2,3\). Les listes sont celles des multiples du diviseur compris entre \(0\) et \(9\), entre \(0\) et \(99\), ou entre \(0\) et \(999\).

Un nombre plus court que le bloc demandé n’est pas un cas interdit : tester \(8\) avec trois chiffres revient à tester \(008\), donc \(8\). Le nombre \(0\) est divisible par tous ces diviseurs, car \(0=d\times0\).

Théorème : Somme des chiffres : critères de 3 et de 9

Notons \(S=a_0+a_1+\cdots+a_s\) la somme des chiffres de \(N\). On a

Démonstration complète. On a \(10\equiv1\pmod9\). Les compatibilités avec les puissances et les produits donnent \(a_j10^j\equiv a_j\pmod9\) pour chaque position \(j\geq1\) ; pour les unités, le terme est déjà \(a_0\). En additionnant,

On peut recommencer avec les chiffres de \(S\) : chaque étape conserve la congruence, donc le test de divisibilité. Il ne faut pas confondre cette somme avec le reste canonique si elle dépasse le module.

Exemple de référence : Un test expliqué, pas seulement récité

Testons \(N=583146\) avec le diviseur \(9\). La décomposition de position donne

Contrôle indépendant par une multiplication :

Théorème : Le critère de 11 : une somme alternée

Pour \(N=\overline{a_s\ldots a_1a_0}\), notons

Démonstration complète. \(10=11-1\), donc \(10\equiv-1\pmod{11}\). Pour \(j\geq1\), \(10^j\equiv(-1)^j\pmod{11}\) : les puissances paires donnent \(1\), les impaires \(-1\). En revenant à l’écriture de position,

On peut commencer l’alternance à gauche au lieu des unités : on obtient soit \(A\), soit \(-A\). Cela change éventuellement le représentant, mais pas la divisibilité par \(11\). La somme alternée peut être nulle ou négative ; \(0\) est bien un multiple de \(11\).

Exemple : Ne pas mélanger somme simple et somme alternée

Pour \(604879\), en partant des unités,

Sa somme simple vaut \(6+0+4+8+7+9=34\), donc ce nombre n’est divisible ni par \(3\) ni par \(9\). Les deux tests ne répondent pas à la même question.

Critère : Tester la divisibilité par 7

Écrivons \(N=10a+b\) avec \(a\in\mathbb{N}\) et \(b\in\{0,\ldots,9\}\). Ainsi \(b\) est le chiffre des unités et \(a\) le nombre obtenu en l’enlevant. Alors

Démonstration complète. Posons \(T=a-2b\). Les deux identités suivantes permettent de passer dans les deux sens :

Utilité et limite. On remplace un grand nombre par un nombre plus court, souvent plus facile à tester. On peut répéter si c’est utile, mais ce procédé conserve la réponse divisible ou non, pas nécessairement le reste. Par exemple \(13\) donne \(1-2\times3=-5\) ; les restes de \(13\) et de \(-5\) modulo \(7\) sont respectivement \(6\) et \(2\), différents.

Critère : Tester la divisibilité par 13

Avec la même écriture \(N=10a+b\), on a

Démonstration complète. Posons \(T=a+4b\). Cette fois,

Ce critère n’autorise pas à choisir librement les coefficients : \(-2\) pour le test de \(7\) et \(+4\) pour celui de \(13\) viennent des identités démontrées. Une fois un petit multiple reconnu, il est inutile de continuer les transformations.

Méthode : Choisir un critère, puis contrôler ce qu’il dit

Premier geste. Identifier le diviseur demandé ; ne pas partir d’un test simplement parce qu’il est familier.

1. Pour \(2,5,10\), regarder les unités ; pour \(4,25,100\), deux chiffres ; pour \(8,125,1000\), trois chiffres.

2. Pour \(3\) ou \(9\), calculer la somme simple. Pour \(11\), alterner les signes en écrivant tous les chiffres, y compris les zéros.

3. Pour \(7\) ou \(13\), écrire explicitement \(a\) et \(b\), puis calculer \(a-2b\) ou \(a+4b\) ; recommencer seulement si cela simplifie la décision.

4. Conclure par une phrase : le nombre est divisible, ou ne l’est pas, par le diviseur fixé. Si un reste est demandé, utiliser une congruence qui conserve réellement ce reste.

Pourquoi ? Chaque test repose sur une équivalence prouvée ; on peut donc remonter au nombre de départ. Un test qui ne donnerait qu’une implication ne permettrait pas automatiquement ce retour.

Contrôle. Quand c’est raisonnable, fournir un quotient entier ou encadrer entre deux multiples consécutifs. Ne pas confondre un contrôle numérique et la preuve générale du critère.

Exemple de référence : Appliquer deux critères de transformation

Test de \(2478\) par \(7\). On écrit \(2478=10\times247+8\). Le nombre transformé est

Test de \(4641\) par \(13\). On écrit \(4641=10\times464+1\). Le nombre transformé est \(464+4\times1=468\). Puis \(468=10\times46+8\), donc

Si un nombre négatif apparaît. Pour \(106\) avec le test de \(7\), on obtient \(10-2\times6=-2\). Il n’est pas divisible par \(7\), donc \(106\) ne l’est pas. On n’impose pas au nombre transformé d’être un reste euclidien.

Propriété : Combiner certains tests exige une raison

Un entier \(N\) est divisible par \(6\) si et seulement s’il est divisible par \(2\) et par \(3\). De même, il est divisible par \(18\) si et seulement s’il est divisible par \(2\) et par \(9\).

Démonstration complète. Si \(N=6\ell\), alors \(N=2(3\ell)=3(2\ell)\), donc les deux divisibilités sont vérifiées. Réciproquement, supposons \(N\) divisible par \(3\) et pair. Écrivons \(N=3k\). Puisque \(N\) et \(2k\) sont pairs, leur différence \(k=N-2k\) est paire : il existe \(\ell\in\mathbb{Z}\) tel que \(k=2\ell\). Ainsi \(N=3\times2\ell=6\ell\).

Pour \(18\), le sens direct vient de \(18=2\times9\). Au retour, écrivons \(N=9k\) avec \(N\) pair. La différence \(k=N-8k\) est paire ; donc \(k=2\ell\) et \(N=18\ell\). Cela prouve les deux équivalences sans supposer de théorème général sur des diviseurs premiers entre eux.

Contre-exemple : On ne multiplie pas librement les diviseurs

Le nombre \(12\) est divisible par \(4\) et par \(6\), puisque \(12=4\times3=6\times2\). Il n’est pas divisible par \(24\), car \(12=24\times0+12\) avec reste non nul. La conclusion « divisible par \(4\) et \(6\), donc par \(24\) » est fausse.

De même, \(18\) est divisible par \(6\) et par \(9\), mais pas par \(54\). Les preuves de la propriété précédente sont donc utiles : elles ne peuvent pas être remplacées par une règle automatique « multiplier les tests ».

Essai guidé : Choisir la bonne portion d’un nombre

Pour \(37125\), teste la divisibilité par \(125\), par \(25\), par \(9\), puis par \(4\). Écris à chaque fois le bloc ou la somme que tu utilises.

Correction expliquée. Les trois derniers chiffres forment \(125=125\times1\), donc \(125\mid37125\). Les deux derniers forment \(25\), donc \(25\mid37125\). La somme est \(3+7+1+2+5=18=9\times2\), donc \(9\mid37125\). En revanche, le nombre formé par les deux derniers chiffres est \(25=4\times6+1\) : il n’est pas multiple de \(4\), donc \(37125\) non plus.

Contrôles indépendants : \(125\times297=37125\), \(25\times1485=37125\) et \(9\times4125=37125\). Un même nombre peut réussir plusieurs tests et échouer à un autre ; chaque conclusion garde son diviseur.

À toi : Une décision argumentée pour chaque diviseur

Sans division posée au départ, décide si \(6732\) est divisible par \(9\), par \(11\) et par \(7\). Justifie les trois réponses avant de lire la correction.

Indice. Les deux premiers tests portent sur des sommes différentes ; pour le troisième, commence par \(a=673\), \(b=2\).

Correction expliquée. Pour \(9\), la somme des chiffres est \(6+7+3+2=18\), donc le nombre est divisible. Pour \(11\), la somme alternée en partant des unités est \(2-3+7-6=-1+7-6=0\) : le nombre est aussi divisible par \(11\).

Pour \(7\), le premier nombre transformé est \(673-2\times2=673-4=669\). Le deuxième est \(66-2\times9=66-18=48\). Or \(48=7\times6+6\), donc \(48\) n’est pas divisible par \(7\) ; les deux équivalences permettent de remonter : \(669\), puis \(6732\), ne sont pas divisibles par \(7\).

Contrôles : \(6732=9\times748=11\times612\), mais \(6732=7\times961+5\). Le reste final \(5\) n’est pas le reste \(6\) du nombre transformé \(48\) : le critère de \(7\) conserve la divisibilité, pas le reste.

Critères de réussite. Diviseur annoncé pour chaque test ; zéros acceptés dans la somme alternée ; transformations \(a-2b\) exactes ; conclusion négative justifiée ; absence de confusion entre reste et nombre transformé.

Justification personnelle : Pourquoi la somme des chiffres ne marche-t-elle pas pour tout diviseur ?

Explique pourquoi la somme simple donne un critère pour \(9\) ; fournis ensuite un contre-exemple montrant que la même règle ne teste pas la divisibilité par \(7\).

Correction expliquée. Une réponse possible : « Dans l’écriture décimale, chaque chiffre est multiplié par une puissance de \(10\). Comme \(10\equiv1\pmod9\), ces puissances peuvent toutes être remplacées par \(1\) modulo \(9\) ; le nombre et la somme ont donc le même reste. En revanche, \(14\) est divisible par \(7\) alors que la somme \(1+4=5\) ne l’est pas. On ne peut pas transposer le test de \(9\) au diviseur \(7\). »

Critères de réussite. Écriture de position mentionnée ; rôle de \(10\equiv1\) ; un contre-exemple avec vérification des deux divisibilités ; aucune généralisation tirée d’un seul essai favorable.

Variation : Des chiffres inconnus sous deux contraintes

Cherche tous les nombres à quatre chiffres de la forme \(\overline{2a3b}\) qui sont divisibles à la fois par \(5\) et par \(9\). Ici \(a\) et \(b\) sont des chiffres, donc appartiennent à \(\{0,\ldots,9\}\).

Correction expliquée. Le test de \(5\) impose \(b=0\) ou \(b=5\). Le test de \(9\) impose que \(2+a+3+b=5+a+b\) soit multiple de \(9\).

Si \(b=0\), alors \(5\leq5+a\leq14\) : le seul multiple de \(9\) possible est \(9\). L’égalité \(5+a=9\) donne \(a=4\), donc \(2430\).

Si \(b=5\), alors \(10\leq10+a\leq19\) : le seul multiple de \(9\) possible est \(18\). L’égalité \(10+a=18\) donne \(a=8\), donc \(2835\).

Réciproquement, \(2430\) finit par \(0\) et sa somme de chiffres vaut \(9\) ; \(2835\) finit par \(5\) et sa somme vaut \(18\). Les deux nombres conviennent. Les deux valeurs possibles de \(b\) et les bornes sur \(a\) garantissent que la liste est complète. Il ne suffisait pas de trouver un seul exemple.

Réparation : Rétablir le bon test et les bons signes

Première erreur. Emma affirme : « \(638\) n’est pas divisible par \(11\), car \(6+3+8=17\) n’est pas multiple de \(11\). » Son calcul est juste, mais le test choisi est faux : pour \(11\), il faut alterner les signes.

Rappel local. \(10\equiv-1\pmod{11}\), donc centaines, dizaines et unités portent respectivement les poids \(+1,-1,+1\). Une somme alternée égale à \(0\) donne bien une divisibilité, car \(0=11\times0\).

Exemple plus simple corrigé. Pour \(121\), on calcule \(1-2+1=0\), donc \(121\) est divisible par \(11\) ; contrôle \(11\times11=121\). La somme simple \(4\) n’est pas celle du test.

Nouvel essai. Teste \(341\) par \(11\) en écrivant d’abord ses poids de position.

Correction expliquée. \(341=3\times100+4\times10+1\). Modulo \(11\), cela donne \(3\times1+4\times(-1)+1=3-4+1=0\). Donc \(341\) est divisible par \(11\) ; contrôle \(11\times31=341\).

Retour à l’erreur. Pour \(638\), \(6-3+8=11\), multiple de \(11\). Le nombre est donc divisible, et \(11\times58=638\). Refais le test initial puis explique, sans lire, quelle ligne du raisonnement d’Emma devait être remplacée.

Reprise différée : Deux transformations à reprendre sur feuille vierge

Sans relire les critères, teste \(7826\) par \(7\) puis par \(13\). Si tu as oublié un coefficient, consulte seulement l’indice, puis produis le calcul avant la correction.

Indice. Avec \(N=10a+b\), les nombres transformés sont \(a-2b\) pour \(7\) et \(a+4b\) pour \(13\). Chaque test est une équivalence de divisibilité.

Correction expliquée. Pour \(7\) : \(782-2\times6=782-12=770\), puis \(77-2\times0=77=7\times11\). Donc \(7\mid7826\).

Pour \(13\) : \(782+4\times6=782+24=806\), puis \(80+4\times6=80+24=104\), puis \(10+4\times4=10+16=26=13\times2\). Donc \(13\mid7826\).

Contrôles : \(7\times1118=7826\) et \(13\times602=7826\). Si tu as confondu le signe ou le coefficient, réécris une des identités des preuves avant de refaire le test : elle explique la règle au lieu de la remplacer par une récitation.

À retenir : Un critère doit être choisi et justifié

• Derniers chiffres : choisir une puissance de \(10\) divisible par le diviseur étudié.

• Somme simple pour \(3\) et \(9\) ; somme alternée pour \(11\).

• Avec \(N=10a+b\), tester \(a-2b\) pour \(7\), \(a+4b\) pour \(13\) ; ces transformations conservent la divisibilité mais pas nécessairement le reste.

• Les deux sens d’un critère autorisent le retour au nombre de départ.

• Des tests combinés ne donnent pas automatiquement le produit des diviseurs : il faut une preuve ou un résultat déjà établi.

• Pour des chiffres inconnus, leurs bornes \(0\leq a,b\leq9\) rendent les recherches finies ; vérifier ensuite tous les nombres annoncés.

Repérage : Vérifier dix valeurs, est-ce démontrer ?

On calcule \(n(n+1)\) pour \(n=0,1,\ldots,9\) et on obtient toujours un nombre pair. A-t-on prouvé que \(n(n+1)\) est pair pour tout entier \(n\) ?

Correction expliquée. Non : il reste une infinité d’entiers non testés, notamment les entiers négatifs. Les essais suggèrent une conjecture. Une preuve doit expliquer pourquoi chaque entier vérifie la propriété. Ici, distinguer \(n\) pair et \(n\) impair ferme tous les cas. Si tu confonds ces deux étapes, commence par le vocabulaire ci-dessous.

Vocabulaire : Affirmation universelle, exemple et contre-exemple

Une proposition universelle affirme une propriété pour tous les éléments d’un ensemble précisé. Un exemple favorable ne la prouve pas. Un seul contre-exemple dans cet ensemble la réfute.

Une implication \(P\Rightarrow Q\) dit : chaque fois que \(P\) est vraie, \(Q\) est vraie. Sa réciproque \(Q\Rightarrow P\) est une autre affirmation. Une équivalence \(P\Leftrightarrow Q\) exige les deux sens. Une condition nécessaire doit être satisfaite par une solution ; une condition suffisante garantit qu’on a une solution.

Ainsi \(4\mid n\) entraîne \(2\mid n\), car \(n=4k=2(2k)\). La réciproque est fausse : \(n=2\) est un contre-exemple. Dire « \(n\) est pair » est nécessaire mais pas suffisant pour dire « \(n\) est multiple de \(4\) ».

Méthode : Cinq portes d’entrée dans une preuve

1. Une expression se factorise : chercher directement un facteur égal au diviseur demandé. Pour prouver \(d\mid A\), viser \(A=dK\) avec \(K\) entier.

2. Peu de restes sont possibles : travailler modulo un petit entier ; annoncer tous les cas, pas seulement ceux qui réussissent.

3. Une équation entière semble impossible : tirer une condition nécessaire, puis montrer qu’aucun reste ne peut la satisfaire.

4. L’exposant ou le rang augmente : essayer une récurrence, surtout si l’expression au rang suivant se relie à celle du rang présent.

5. Une affirmation est douteuse : chercher d’abord un contre-exemple ; ne pas fabriquer une démonstration d’un énoncé faux.

Premier geste. Écrire le domaine et ce qu’il faut réellement obtenir. Une conclusion « le reste est \(0\) » ne répond pas encore à une question sur l’existence de solutions d’une équation : il faut vérifier l’équation elle-même.

Contrôle. Relire les quantificateurs, les hypothèses, l’exhaustivité des cas et le sens de chaque implication.

Proposition : Le produit de deux entiers consécutifs est pair

Pour tout \(n\in\mathbb{Z}\), \(2\mid n(n+1)\).

Démonstration complète. Tout entier est pair ou impair, y compris s’il est négatif.

• Si \(n=2k\), alors \(n(n+1)=2k(2k+1)=2\bigl(k(2k+1)\bigr)\).

• Si \(n=2k+1\), alors \(n+1=2k+2=2(k+1)\) et \(n(n+1)=2\bigl((2k+1)(k+1)\bigr)\).

Dans chaque cas, le facteur entre parenthèses est entier. Les deux cas épuisent \(\mathbb{Z}\) : la propriété est démontrée.

Lemme : Combiner les divisibilités par deux et par trois

Pour tout entier \(A\), si \(2\mid A\) et \(3\mid A\), alors \(6\mid A\).

Démonstration complète. Écrivons \(A=3k\) avec \(k\in\mathbb{Z}\). Si \(k\) était impair, \(k=2h+1\) donnerait \(A=3(2h+1)=6h+3=2(3h+1)+1\), impair, contrairement à \(2\mid A\). Donc \(k=2h\) pour un entier \(h\) et \(A=3\times2h=6h\).

Ce lemme ne dit pas que l’on peut multiplier n’importe quels diviseurs : \(4\mid12\) et \(6\mid12\), mais \(24\nmid12\).

Exemple de référence : Une propriété valable sur tout \(\mathbb{Z}\)

But : démontrer que \(6\mid n^3-n\) pour tout \(n\in\mathbb{Z}\).

Premier geste : factoriser en montrant l’identité utilisée :

Par ailleurs, écrivons \(n=3q+r\), où \(r\in\{0,1,2\}\).

• Si \(r=0\), le facteur \(n\) est divisible par \(3\).

• Si \(r=1\), \(n-1=3q\) est divisible par \(3\).

• Si \(r=2\), \(n+1=3q+3=3(q+1)\) est divisible par \(3\).

Ainsi \(3\mid n(n-1)(n+1)\). Le lemme précédent permet de conclure \(6\mid n^3-n\).

Autre voie, par congruences : modulo \(6\), les six restes de \(n\) donnent les valeurs suivantes pour \(r^3-r\) :

Puisque \(n^3-n\equiv r^3-r\pmod6\), ces six cas démontrent aussi le résultat. Ce tableau est une preuve générale, contrairement à six essais sur des valeurs isolées : chaque entier possède l’un de ces restes.

Contrôle. Pour \(n=-2\), \(n^3-n=-8+2=-6\) est bien un multiple de \(6\). Ce calcul vérifie un exemple, mais ne remplace aucune des deux preuves.

Proposition : Une obstruction par les carrés modulo quatre

Un carré entier est congru à \(0\) ou à \(1\) modulo \(4\). En conséquence, pour tout \(k\in\mathbb{Z}\), l’équation \(x^2+y^2=4k+3\) n’a pas de solution \((x,y)\in\mathbb{Z}^2\).

Démonstration complète. Si \(x=2h\), alors \(x^2=4h^2\equiv0\pmod4\). Si \(x=2h+1\), alors

Limite : ne pas trouver de contradiction ne prouve pas l’existence d’une solution. Par exemple, le reste de \(6\) modulo \(4\) vaut \(2\), mais \(x^2+y^2=6\) n’a pas de solution entière : les carrés possibles inférieurs ou égaux à \(6\) sont \(0\), \(1\), \(4\), et aucune paire n’a pour somme \(6\).

Résultat antérieur : Le principe de récurrence

Principe utilisé en terminale spécialité. Pour démontrer une propriété \(P(n)\) pour tout entier \(n\geqslant n_0\), on établit :

1. l’initialisation : \(P(n_0)\) est vraie ;

2. l’hérédité : pour un entier arbitraire \(n\geqslant n_0\), si \(P(n)\) est vraie, alors \(P(n+1)\) est vraie.

On peut alors conclure que \(P(n)\) est vraie pour tout \(n\geqslant n_0\). Ce principe sur les entiers naturels est un résultat antérieur, utilisé ici sans reconstruction axiomatique de \(\mathbb{N}\).

Image utile : une échelle dont on peut atteindre le premier barreau et passer de chaque barreau au suivant. Le premier barreau représente l’initialisation ; le passage représente l’implication d’hérédité. L’image explique les deux obligations, mais n’est pas une démonstration du principe et ne permet pas de sauter un barreau.

Exemple de référence : Une preuve par récurrence, puis un contrôle modulaire

Montrons que, pour tout \(n\in\mathbb{N}\), \(6\mid7^n-1\).

Initialisation au rang \(0\). \(7^0-1=1-1=0=6\times0\) : la propriété est vraie.

Hérédité. Soit \(n\in\mathbb{N}\). Supposons \(6\mid7^n-1\). Cela signifie qu’il existe \(k\in\mathbb{Z}\) tel que \(7^n-1=6k\). Nous devons obtenir un multiple de \(6\) au rang \(n+1\) :

Contrôle par une autre méthode. Comme \(7\equiv1\pmod6\), on a \(7^n\equiv1\pmod6\) pour tout \(n\geqslant1\) par compatibilité avec les puissances. Le cas \(n=0\) est vérifié séparément. Cette seconde preuve est plus courte ; la première montre comment exploiter une hypothèse de récurrence.

Essai guidé : Construire l’hérédité

Démontrer que \(3\mid4^n-1\) pour tout \(n\in\mathbb{N}\). Vérifier le rang \(0\), écrire \(4^n-1=3k\), puis compléter \(4^{n+1}-1=4(4^n-1)+\ldots\).

Indice. Le terme manquant est \(4-1\), et non \(-1\).

Correction expliquée. Au rang \(0\), \(4^0-1=0=3\times0\). Soit \(n\in\mathbb{N}\) tel que \(4^n-1=3k\) avec \(k\in\mathbb{Z}\). Alors

À toi : Deux affirmations à examiner avant consultation

1. Démontrer que \(8\mid9^n-1\) pour tout \(n\in\mathbb{N}\). Choisir une méthode et la justifier.

2. « Si \(n^2\equiv1\pmod8\), alors \(n\equiv1\pmod8\). » Cette affirmation est-elle vraie ?

Indice. Pour 1, comparer \(9\) à \(1\) modulo \(8\), ou relier les rangs \(n+1\) et \(n\). Pour 2, tester un petit entier impair différent de \(1\).

Correction expliquée. 1. Comme \(9=8+1\), \(9\equiv1\pmod8\). Pour \(n\geqslant1\), \(9^n\equiv1^n=1\pmod8\), donc \(8\mid9^n-1\). Pour \(n=0\), \(9^0-1=0\) est aussi divisible par \(8\). La voie modulaire est adaptée car la base se réduit immédiatement à \(1\).

Une récurrence fonctionnerait également : initialisation \(9^0-1=0\) ; si \(9^n-1=8k\), alors \(9^{n+1}-1=9(9^n-1)+8=8(9k+1)\). Cela donne explicitement le nouveau témoin.

2. Prendre \(n=3\) : \(3^2=9\equiv1\pmod8\), mais \(3\not\equiv1\pmod8\) puisque \(8\nmid3-1=2\). L’affirmation est fausse. Il ne faut pas « prendre une racine carrée » d’une congruence comme si son reste déterminait la racine.

Justification personnelle : Pourquoi un tableau de restes peut-il être une preuve ?

Expliquer la différence entre tester \(n=0,1,2\) dans une expression \(F(n)\) et démontrer que, si \(n\equiv r\pmod3\), alors \(F(n)\equiv F(r)\pmod3\), puis traiter \(r=0,1,2\).

Correction expliquée. Les trois essais isolés ne disent rien sur les autres entiers. La seconde démarche regroupe tous les entiers par leur reste. Il faut justifier que la transformation de l’expression respecte la congruence, puis traiter les trois restes possibles. Pour les expressions obtenues par sommes et produits d’entiers et de puissances entières positives, cette justification vient des règles de calcul modulaire.

Critères de réussite. La réponse doit citer l’exhaustivité des restes, la compatibilité des opérations effectivement utilisées et l’interdiction de conclure à partir de simples essais. Elle ne doit pas étendre cette compatibilité à une division non justifiée.

Variation : Un rang initial qui change tout

L’affirmation « \(2\mid2^n\) pour tout \(n\in\mathbb{N}\) » est-elle exacte ? Si nécessaire, corriger son domaine puis démontrer l’énoncé corrigé.

Indice. Tester d’abord le premier rang autorisé.

Correction expliquée. L’affirmation est fausse, car au rang \(0\), \(2^0=1\) et \(2\nmid1\). L’énoncé correct est « pour tout \(n\geqslant1\) ». Sa preuve directe est \(2^n=2\times2^{n-1}\), où \(2^{n-1}\) est bien un entier parce que \(n-1\geqslant0\).

On ne corrige donc pas seulement la preuve : on corrige d’abord le domaine de l’énoncé. Au rang \(0\), écrire \(2^0=2\times2^{-1}\) ne prouve aucune divisibilité dans \(\mathbb{Z}\), puisque \(2^{-1}=1/2\) n’est pas entier.

Réparation : L’hypothèse de récurrence utilisée au mauvais rang

Première erreur : pour prouver \(6\mid7^{n+1}-1\), écrire d’emblée \(7^{n+1}-1=6K\) « par hypothèse ». C’est justement ce qu’il faut démontrer : le raisonnement est circulaire.

Rappel : l’hypothèse donne uniquement le rang \(n\), \(7^n-1=6k\). On doit transformer le rang \(n+1\) pour faire apparaître cette expression.

Exemple plus simple corrigé : si \(u=5k\), alors \(3u+10=3\times5k+5\times2=5(3k+2)\). On part de l’information disponible et on construit le témoin du résultat demandé.

Nouvel essai : sachant que \(5^n-1=4k\), montrer que \(4\mid5^{n+1}-1\).

Correction expliquée. \(5^{n+1}-1=5(5^n-1)+5-1=5\times4k+4=4(5k+1)\). Le témoin \(5k+1\) est entier. Cette étape est une hérédité ; pour une preuve complète par récurrence, ajouter l’initialisation \(5^0-1=0\) puis conclure.

Retour : reprendre l’exemple sur \(7^n-1\) et entourer uniquement l’égalité fournie par l’hypothèse, puis l’égalité qui prouve le rang suivant. Les deux rangs ne doivent pas être confondus.

Reprise différée : Une nouvelle rédaction sans relire les preuves

À une séance suivante, démontrer que \(8\mid3^{2n}-1\) pour tout \(n\in\mathbb{N}\). Écrire une preuve générale et vérifier séparément son premier rang. Expliquer ensuite pourquoi \(x^2+y^2=103\) n’a pas de solution entière.

Indice. Pour la première question, \(3^{2n}=(3^2)^n=9^n\). Pour la seconde, regarder les carrés modulo \(4\).

Correction expliquée. Comme \(9\equiv1\pmod8\), pour \(n\geqslant1\) on a \(3^{2n}=9^n\equiv1\pmod8\). Pour \(n=0\), \(3^0-1=0\). Le résultat vaut donc pour tout \(n\in\mathbb{N}\).

Pour la seconde question, un entier pair a son carré congru à \(0\) modulo \(4\), un entier impair à \(1\) puisque \((2h+1)^2=4(h^2+h)+1\). La somme de deux carrés a pour reste \(0\), \(1\) ou \(2\). Or \(103=4\times25+3\) a pour reste \(3\). L’égalité est impossible.

À retenir : Une preuve doit fermer ses portes de sortie

Annoncer le domaine ; distinguer conjecture et preuve ; justifier tous les cas ; ne pas confondre condition nécessaire et suffisante ; ne pas utiliser la conclusion dans les hypothèses. Dans une récurrence, écrire le premier rang, l’hypothèse au rang \(n\), le passage au rang \(n+1\) et la conclusion. Une méthode courte et démontrée vaut mieux qu’une méthode longue qui tourne en rond.

Repérage : Quelle information faut-il conserver ?

Une organisation fictive appelle jour \(0\) un mardi. Le jour \(3\) et le jour \(10\) sont-ils des jours de même nom ? Et les jours \(3\) et \(11\) ?

Correction expliquée. \(10-3=7\) correspond à une semaine complète, donc les jours \(3\) et \(10\) ont le même nom. \(11-3=8=7+1\) correspond à une semaine plus un jour : ils ont des noms différents. Ce qui compte est le reste de l’écart modulo \(7\), pas la taille de cet écart. Si tu as compté le mardi comme « jour \(1\) », reprends la convention : ici le mardi de référence porte le numéro \(0\).

Méthode : Modéliser un cycle de longueur 7

Dans notre calendrier fictif, les correspondances sont les suivantes :

Premier geste. Fixer le numéro et le nom du jour de référence. Pour un autre jour de référence \(j_0\), calculer d’abord l’écart \(j-j_0\).

1. Faire la division euclidienne du numéro, ou de l’écart, par \(7\).

2. Ignorer les semaines complètes ; lire le nom correspondant au reste \(0,\ldots,6\).

3. Pour chercher tous les jours d’un certain nom, écrire \(j=r+7k\), \(k\in\mathbb{Z}\), puis imposer l’intervalle éventuel.

Pourquoi ? Dans l’écriture \(j=7q+r\), chaque paquet de sept pas ramène au même nom. Il reste exactement \(r\) pas à effectuer depuis le jour \(0\). Pour des numéros négatifs, on recule ; la division euclidienne fournit tout de même un reste positif ou nul.

Contrôle. Vérifier la convention initiale, le sens du déplacement et \(0\leq r<7\). Le quotient compte des semaines, le reste repère un jour : ce ne sont pas les mêmes objets.

Représentation : Sept positions, puis le même cycle

Description : en tournant dans le sens de la flèche, les restes \(0,1,2,3,4,5,6\) correspondent à mardi, mercredi, jeudi, vendredi, samedi, dimanche et lundi. Après \(6\), on revient à \(0\) : \(6+1=7\equiv0\pmod7\).

Le cercle représente le nom du jour, pas sa date : les jours \(0\) et \(7\) sont deux journées différentes, placées au même endroit dans le cycle. Il aide à visualiser la congruence ; la justification reste la décomposition en semaines complètes et jours restants.

Exemple de référence : Aller du numéro au nom, puis du nom aux numéros

Quel nom pour le jour \(202\) ? La division donne \(202=7\times28+6\). Le reste \(6\) correspond à un lundi.

Quel nom pour le jour \(-10\) ? On écrit \(-10=7\times(-2)+4\). Le reste \(4\) correspond à un samedi. Ce jour précède bien le mardi de référence de dix jours ; le quotient négatif n’autorise pas un reste négatif.

Quels samedis entre les jours \(0\) et \(30\), bornes incluses ? On cherche \(j\equiv4\pmod7\), donc \(j=4+7k\), \(k\in\mathbb{Z}\). Les bornes donnent

Essai guidé : Une date fictive avant l’origine

Dans la même convention, trouve le nom du jour \(-17\). Commence par compléter \(-17=7\times(-3)+\ldots\).

Correction expliquée. \(-17=-21+4=7\times(-3)+4\), avec \(0\leq4<7\). Le reste est \(4\), donc c’est un samedi. Contrôle par la différence : \(4-(-17)=21=3\times7\) ; les jours \(-17\) et \(4\) sont séparés par trois semaines.

Définition : Une clé de contrôle pédagogique

On veut transmettre quatre chiffres \(d_1,d_2,d_3,d_4\), chacun compris entre \(0\) et \(9\). On leur ajoute un cinquième chiffre \(c\), appelé clé. Notre règle de contrôle, inventée pour ce cours, est

Propriété : Une unique clé parmi les dix chiffres

Pour tous les quatre premiers chiffres, il existe une unique clé \(c\in\{0,\ldots,9\}\). Si \(S=d_1+3d_2+d_3+3d_4\) et si \(r\) est le reste de \(S\) modulo \(10\), alors

Démonstration complète. La règle équivaut à \(c\equiv-S\pmod{10}\). Or tout entier possède un unique reste entre \(0\) et \(9\), donc une unique valeur de \(c\) dans cet intervalle. Plus explicitement, si \(S=10q\), prendre \(c=0\) convient. Si \(S=10q+r\) avec \(1\leq r\leq9\), alors \(1\leq10-r\leq9\) et

Méthode : Fabriquer ou vérifier une clé

Premier geste. Écrire les chiffres dans leur ordre et placer les poids \(1,3,1,3,1\) sous les positions ; ne pas appliquer le même poids à tous les chiffres.

1. Pour fabriquer la clé, calculer \(S=d_1+3d_2+d_3+3d_4\), puis son reste \(r\) dans la division par \(10\).

2. Choisir le chiffre qui complète ce reste à un multiple de \(10\) : \(0\) si \(r=0\), sinon \(10-r\).

3. Pour vérifier un code déjà complet, calculer la somme des cinq termes et vérifier que son reste est \(0\).

Pourquoi ? La proposition donne existence et unicité de la clé ; elle explique aussi pourquoi recopier le reste \(r\) comme clé serait généralement faux.

Contrôle. La clé doit être un chiffre de \(0\) à \(9\), pas le nombre \(10\). Un code refusé est incohérent avec cette règle ; un code accepté n’est pas pour autant authentifié.

Exemple de référence : La clé complète la somme pondérée

Pour les quatre chiffres \(4,2,7,5\), on calcule

Vérification dans la règle de départ :

Théorème : Ce contrôle détecte tout changement d’un seul chiffre

Supposons qu’un code satisfasse notre règle et qu’on remplace exactement un de ses cinq chiffres par un autre chiffre, sans changer les autres positions. Alors le nouveau code ne satisfait plus la règle.

Démonstration complète. Notons \(\delta\) la différence « nouveau chiffre moins ancien chiffre ». Comme il s’agit de deux chiffres différents, \(\delta\ne0\) et \(-9\leq\delta\leq9\). Le poids \(w\) de la position modifiée vaut \(1\) ou \(3\) ; la somme totale change donc de \(w\delta\).

Si le nouveau code était encore accepté, l’ancienne somme et la nouvelle seraient deux multiples de \(10\). Leur différence \(w\delta\) serait donc multiple de \(10\).

• Si \(w=1\), on aurait directement \(\delta\equiv0\pmod{10}\).

• Si \(w=3\), on aurait \(3\delta\equiv0\pmod{10}\). On multiplie par \(7\) : \(21\delta\equiv0\pmod{10}\). Or \(21\equiv1\pmod{10}\), donc là encore \(\delta\equiv0\pmod{10}\).

Le seul multiple de \(10\) compris entre \(-9\) et \(9\) est \(0\). On obtiendrait \(\delta=0\), contrairement à l’hypothèse. Le changement est donc toujours détecté, même s’il porte sur la clé elle-même.

Les hypothèses sont importantes : la longueur et les autres chiffres doivent rester inchangés. Le théorème ne parle ni de deux changements simultanés ni de toutes les permutations possibles.

Contre-exemple : Un contrôle réussi ne prouve pas l’absence d’erreur

Partons du code accepté \(42758\) et échangeons les chiffres \(2\) et \(7\) des deuxième et troisième positions. On obtient \(47258\). Sa somme pondérée vaut

La somme a augmenté de \((3\times7+2)-(3\times2+7)=23-13=10\). Un changement d’un seul chiffre était impossible à cacher ; deux changements peuvent se compenser modulo \(10\). Il ne faut donc pas écrire « le code est exact » mais « le code satisfait la règle de contrôle ».

Essai guidé : Construire puis contrôler une nouvelle clé

On veut transmettre les quatre chiffres \(1,4,0,2\). Calcule la somme pondérée, son reste, puis la clé et le code complet.

Correction expliquée. \(S=1+3\times4+0+3\times2=1+12+0+6=19\). Ainsi \(r=9\) et \(c=10-9=1\). Le code complet est \(\boxed{14021}\) ; sa somme pondérée vaut \(19+1=20\), multiple de \(10\). Le zéro de troisième position reste présent dans le code, même si son terme dans la somme vaut \(0\).

Définition : Un chiffrement affine de lettres

On associe aux lettres non accentuées leur rang en commençant à \(0\) : \(A\leftrightarrow0\), \(B\leftrightarrow1\), jusqu’à \(Z\leftrightarrow25\). Pour ce modèle, on supprime les espaces et l’on remplace les lettres accentuées par leur lettre non accentuée avant de coder. Ce traitement préalable ne permet donc pas de retrouver les accents ou les espaces.

Pour chiffrer une lettre de rang \(x\), on choisit comme rang chiffré \(y\) l’unique reste de \(5x+7\) modulo \(26\) :

Théorème : Une formule de déchiffrement et un retour unique

Pour ce chiffrement, le rang initial \(x\) est l’unique reste de \(21(y-7)\) modulo \(26\) :

Démonstration complète. On vérifie d’abord l’inverse : \(5\times21=105=26\times4+1\). Ainsi \(5\times21\equiv1\pmod{26}\).

Retrouver une lettre chiffrée. Si \(y\equiv5x+7\pmod{26}\), alors \(y-7\equiv5x\pmod{26}\). En multipliant par \(21\),

Vérifier le sens inverse. Si l’on choisit \(x\) comme reste de \(21(y-7)\), alors

La soustraction de \(7\) doit précéder la multiplication par \(21\). L’expression \(21y-7\) n’est pas égale à \(21(y-7)=21y-147\) et ne réalise pas la même opération.

Méthode : Chiffrer puis déchiffrer une lettre

Premier geste. Traduire la lettre en un rang entre \(0\) et \(25\) et identifier le sens demandé : aller vers le message chiffré ou revenir au message initial.

1. Pour chiffrer, calculer \(5x+7\), prendre son reste \(y\) modulo \(26\), puis convertir \(y\) en lettre.

2. Pour déchiffrer, calculer d’abord \(y-7\), puis \(21(y-7)\) ; prendre son reste \(x\) modulo \(26\), puis convertir \(x\) en lettre.

3. Si le calcul est négatif, chercher un multiple de \(26\) qui donne un reste dans \([0,26[\). Un résultat négatif n’est pas un rang de lettre.

Pourquoi ? La formule de retour vient de l’inverse vérifié \(21\) de \(5\), et les bornes sur les rangs rendent le résultat unique.

Contrôle. Rechiffrer la lettre obtenue. Le décodage ne restaure pas les espaces ou accents supprimés ; la règle n’assure aucune sécurité cryptographique réelle. Elle est connue de tout lecteur de ce cours, qui peut donc l’inverser.

Exemple de référence : Un aller-retour complet sur MATH

Les rangs de \(M,A,T,H\) sont \(12,0,19,7\). Pour chiffrer :

Le mot chiffré est donc \(\boxed{PHYQ}\). Vérifions le retour sur les quatre lettres, pas seulement sur la première :

Essai guidé : Déchiffrer malgré un résultat intermédiaire négatif

Déchiffre la lettre \(F\), de rang \(y=5\). Commence par \(y-7\), puis multiplie par \(21\) ; écris enfin une division euclidienne par \(26\).

Correction expliquée. \(5-7=-2\), puis \(21\times(-2)=-42\). On écrit

À toi : Trois informations à produire

Conserve les règles de cette unité, puis cherche sans regarder les réponses.

1. Dans le calendrier fictif où le jour \(0\) est un mardi, quels sont les vendredis entre les jours \(31\) et \(60\), bornes incluses ?

2. Quelle clé complète les chiffres \(3,4,0,6\) ? Le code \(34061\) satisfait-il le contrôle ?

3. Chiffre la lettre \(S\), de rang \(18\), puis déchiffre la lettre \(Z\), de rang \(25\).

Indice. Un nom de jour donne un reste ; une clé complète une somme pondérée ; pour le chiffrement, choisis la formule correspondant au sens de la question.

Correction expliquée. 1. Le vendredi correspond au reste \(3\), donc \(j=3+7k\) avec \(k\in\mathbb{Z}\). Les bornes donnent

2. \(S=3+3\times4+0+3\times6=3+12+0+18=33\). Le reste est \(3\), donc la clé vaut \(7\) et le code correct pour cette règle est \(\boxed{34067}\). Le code proposé \(34061\) donne \(33+1=34\), non multiple de \(10\) : il est refusé.

3. Pour chiffrer \(S\), \(5\times18+7=90+7=97=26\times3+19\) ; le reste \(19\) correspond à \(\boxed{T}\). Pour déchiffrer \(Z\),

Critères de réussite. Sens du calcul choisi ; bornes du reste contrôlées ; toutes les positions pondérées ; conversion finale vers jour, code ou lettre ; exhaustivité lorsque plusieurs jours sont demandés.

Justification personnelle : Détecter n’est pas authentifier

Explique pourquoi notre clé détecte tout changement d’un seul chiffre, mais pourquoi il serait faux d’affirmer qu’un code accepté est forcément celui qui a été envoyé. Cite les conditions et utilise un exemple de cette unité.

Correction expliquée. Une réponse possible : « Un seul changement modifie la somme de \(w\delta\), avec \(w=1\) ou \(3\), et \(\delta\) non nul entre \(-9\) et \(9\). Comme \(1\) et \(3\) ont un inverse modulo \(10\), cette variation ne peut pas être multiple de \(10\) : l’erreur est détectée. Mais le code \(42758\) et le code \(47258\), obtenu par une permutation, donnent des sommes \(40\) et \(50\), donc sont tous deux acceptés. Le contrôle ne prouve donc ni l’absence de toute erreur ni l’authenticité d’un identifiant. »

Critères de réussite. Changement d’exactement un chiffre ; rôle des poids et de la borne sur \(\delta\) ; limitation appuyée sur un vrai contre-exemple ; distinction contrôle de cohérence/authentification.

Variation : Changer le coefficient peut empêcher le déchiffrement

On remplace le chiffrement par \(y\equiv2x+7\pmod{26}\). Les rangs restent entre \(0\) et \(25\). Peut-on retrouver une unique lettre initiale à partir de chaque lettre chiffrée ?

Correction expliquée. Non. Pour \(A\), de rang \(0\), on obtient \(2\times0+7=7\), donc \(H\). Pour \(N\), de rang \(13\), on obtient \(2\times13+7=33=26+7\), donc encore \(H\). Deux lettres différentes ont la même image : si l’on reçoit \(H\), impossible de choisir entre ces deux antécédents à partir de cette seule règle.

On comprend aussi pourquoi on ne peut pas inventer un inverse de \(2\) modulo \(26\) : \(2c-1\) est impair pour tout entier \(c\), donc ne peut pas être multiple de \(26\), qui est pair. La vérification de l’inverse dans le chiffrement initial était une condition indispensable, pas une formalité.

Réparation : La clé n’est pas le reste de la somme

Première erreur. Lucas calcule \(S=32\) et prend la clé \(2\), parce que \(32\) a pour reste \(2\) modulo \(10\).

Rappel. On demande \(S+c\equiv0\pmod{10}\). La clé doit compléter la somme à un multiple de \(10\) ; elle n’est pas censée recopier son reste.

Exemple plus simple corrigé. Si \(S=8\), on choisit \(c=2\), car \(8+2=10\). Choisir \(8\) donnerait \(16\), non divisible par \(10\).

Nouvel essai. Trouve la clé si \(S=14\), puis si \(S=20\).

Correction expliquée. Pour \(14\), le reste est \(4\) et la clé vaut \(10-4=6\) ; \(14+6=20\). Pour \(20\), le reste est déjà \(0\), donc la clé est \(0\), pas \(10\) : \(20+0=20\) et la clé doit être un chiffre.

Retour. Pour \(S=32\), la clé est \(8\) ; \(32+8=40\). Refais le calcul du code \(42758\) en écrivant toi-même la condition \(S+c\equiv0\pmod{10}\) avant de choisir \(c\).

Réparation : Un rang de lettre ne peut pas être négatif

Première erreur. Pour déchiffrer \(F\), Sarah trouve \(-42=26\times(-1)-16\) et veut conserver \(-16\). L’égalité est correcte, mais \(-16\) n’est pas dans l’intervalle des rangs \(0,\ldots,25\).

Rappel. On doit produire la division euclidienne, pas une décomposition quelconque. Pour un entier négatif, on peut ajouter suffisamment de multiples de \(26\) pour obtenir un représentant entre \(0\) et \(25\).

Exemple plus simple corrigé. \(-3=26\times(-1)+23\) : le reste est \(23\), et non \(-3\).

Nouvel essai. Déchiffre \(A\), de rang \(y=0\).

Correction expliquée. \(21(0-7)=21\times(-7)=-147\). Comme \(26\times(-6)=-156\), on a \(-147=-156+9=26\times(-6)+9\). Le rang \(9\) correspond à \(J\). Contrôle : \(5\times9+7=52=26\times2+0\), qui chiffre \(J\) en \(A\).

Retour. \(-42=26\times(-2)+10\), donc \(F\) se déchiffre en \(K\), de rang \(10\). Reprends la question guidée en contrôlant explicitement les deux bornes du reste.

Reprise différée : Trois retours au sens du résultat

À reprendre plus tard, avant relecture : quel est le nom du jour \(100\) dans notre calendrier ? Quelle clé complète \(8,0,8,1\) ? Quelle lettre initiale a été chiffrée en \(V\), de rang \(21\) ? Écris la condition modulaire dans chaque cas.

Indice. Les modules sont respectivement \(7\), \(10\) et \(26\) ; pour le dernier calcul, revenir par \(21(y-7)\).

Correction expliquée. Le jour \(100\) vérifie \(100=7\times14+2\) ; le reste \(2\) correspond au jeudi. Pour la clé,

Si tu as trouvé le bon nombre mais oublié le nom du jour ou la lettre, termine la traduction : le contexte fait partie de la réponse. Si tu as confondu clé et reste, reprends la première réparation ; si le représentant est négatif, la seconde.

À retenir : Même calcul modulaire, informations différentes

• Dans un cycle, le reste donne une position ; un nombre de tours ne change pas cette position. Une date de référence doit être fixée.

• Une clé est construite pour satisfaire une relation précise. Notre clé détecte tous les changements d’un seul chiffre, mais pas toutes les erreurs de plusieurs chiffres.

• Pour chiffrer, on réduit \(5x+7\) modulo \(26\) ; pour déchiffrer, on réduit \(21(y-7)\), grâce à \(5\times21\equiv1\pmod{26}\).

• Le reste \(0\leq r<m\) est unique : on le retraduit en jour, chiffre ou lettre.

• Cette clé ne prouve pas l’authenticité ; ce chiffrement scolaire n’est pas sûr.

Repérage : Que fait réellement une instruction ?

On part de \(q=2\), \(r=9\) et \(b=4\). On exécute successivement q = q + 1, puis r = r - b. Quelles sont les valeurs finales ? L’égalité \(17=4q+r\) est-elle vraie avant, entre et après les deux instructions ?

Correction expliquée. Au départ, \(4\times2+9=17\). Après la première instruction, \(q=3\) mais \(r=9\), donc \(4q+r=21\). Après la seconde, \(r=9-4=5\), et \(4\times3+5=17\). L’égalité est conservée à la fin du groupe de deux instructions, pas entre elles. Si tu as écrit \(q=q+1\) comme une équation impossible, lis le rappel d’affectation qui suit : en programmation, on calcule à droite avec les anciennes valeurs, puis on remplace la valeur à gauche.

Vocabulaire : Variables, affectation, invariant et terminaison

Une variable conserve une valeur pendant l’exécution. L’affectation r = r - b lit l’ancienne valeur de r, lui soustrait b, puis range le résultat dans r. Elle ne pose pas une équation à résoudre.

Un invariant de boucle est une affirmation vraie à l’entrée de la boucle et encore vraie après chaque passage complet. Pour établir la correction d’un algorithme, on vérifie :

1. les préconditions : quelles entrées sont autorisées ?

2. l’initialisation et la conservation de l’invariant ;

3. la terminaison : pourquoi la boucle finit-elle ?

4. la conclusion obtenue avec l’invariant et le test d’arrêt.

Un entier naturel qui diminue strictement à chaque passage fournit une preuve de terminaison. Justification : une diminution entière enlève au moins 1. En partant d’une valeur \(r_0\), après \(j\) diminutions on a donc \(r_j\leq r_0-j\). Cela se vérifie de proche en proche : de \(r_j\leq r_0-j\) et \(r_{j+1}\leq r_j-1\), on tire \(r_{j+1}\leq r_0-(j+1)\). Plus de \(r_0\) diminutions rendraient la valeur négative, alors qu’elle reste naturelle. La descente finit donc nécessairement.

Notation : Les opérations entières de Python

Avec des entiers a et b, et b > 0, Python fournit :

Dans le code, == compare deux valeurs et renvoie True ou False ; = affecte une valeur. ** désigne une puissance. Une ligne indentée appartient au bloc annoncé par if, for ou while.

Algorithme : Tester une divisibilité et obtenir quotient et reste

Les arguments des deux fonctions sont des entiers. La première respecte la convention de divisibilité adoptée, y compris si le diviseur est nul. La seconde exige un diviseur strictement positif.

def divise(d, a):
    if d == 0:
        return a == 0
    return a % d == 0

def euclidienne(a, b):
    if b <= 0:
        raise ValueError("b doit etre strictement positif")
    q = a // b
    r = a % b
    return q, r

Pourquoi ? Si \(d\neq0\), un reste nul signifie exactement que \(a\) est un multiple de \(d\), même si \(d\) est négatif. Si \(d=0\), on ne calcule jamais a % d : la définition impose alors \(a=0\). Pour la seconde fonction, les opérations entières donnent le quotient et le reste ; le contrôle final est l’égalité \(a=bq+r\) avec les deux bornes du reste.

Exemples commentés. divise(-7, 42) renvoie True, car \(42=(-7)\times(-6)\). divise(0, 5) renvoie False, car \(5\neq0\). divise(0, 0) renvoie True sans diviser par zéro. euclidienne(-47, 6) renvoie (-8, 1), que l’égalité précédente vérifie.

Piège : Un entier exact n’est pas un nombre flottant

Pour les calculs de ce chapitre, garder les données et les opérations sous forme entière. Les entiers Python ne sont pas remplacés automatiquement par des flottants dans +, -, *, //, % et les puissances d’exposant entier naturel. Les limites de mémoire et de temps demeurent, bien sûr.

La conversion en flottant peut perdre une unité. Par exemple, pour

Bon réflexe : tester N % d == 0, pas l’apparence « entière » d’un quotient affiché. Les résultats numériques ci-dessus constituent un exemple réel de perte de précision, pas une preuve que tout calcul flottant serait faux.

Méthode : Lire une boucle avant de la lancer

Quand ? Une consigne demande d’exécuter, compléter, expliquer ou corriger un algorithme.

Premier geste. Écrire les préconditions, le sens de chaque variable, puis une ligne de tableau avec l’état initial. Ne pas commencer par recopier des valeurs au hasard.

1. Évaluer le test avec les valeurs présentes.

2. Si le test est vrai, exécuter les instructions dans l’ordre, en notant les nouvelles valeurs.

3. Revenir au test : il est évalué à nouveau, pas une seule fois.

4. Relier une égalité conservée au résultat recherché ; justifier que la boucle s’arrête.

Contrôle. Tester un cas ordinaire, un cas limite et un cas qui doit être refusé. Les tests peuvent révéler un défaut ; leur succès sur quelques entrées ne prouve pas la validité pour toutes les entrées.

Algorithme : Division par soustractions successives

Entrées : \(a\geq0\) et \(b\geq1\), entiers. Sortie : le quotient \(q\) et le reste \(r\). Le nombre \(a\) reste fixe ; \(r\) est ce qui n’a pas encore été retiré, et \(q\) compte les soustractions de \(b\).

def division_soustractions(a, b):
    if a < 0 or b <= 0:
        raise ValueError("il faut a >= 0 et b > 0")
    q, r = 0, a
    while r >= b:
        q = q + 1
        r = r - b
    return q, r

Invariant : au test de la boucle, \(a=bq+r\), \(q\geq0\) et \(r\geq0\).

Démonstration complète. Au départ, \(a=b\times0+a\) : l’invariant est vrai. Si \(r\geq b\), les nouvelles valeurs sont \(q'=q+1\) et \(r'=r-b\). Elles vérifient

À chaque passage, l’entier naturel \(r\) diminue d’au moins \(1\), puisque \(b\geq1\). La boucle finit. À l’arrêt, le test \(r\geq b\) est faux, donc \(r<b\). Avec l’invariant, on a exactement \(a=bq+r\) et \(0\leq r<b\), les conditions de la division euclidienne.

Limite : cet algorithme peut effectuer beaucoup de passages. Pour un grand quotient, // et % conviennent mieux. La version écrite n’accepte pas un dividende négatif ; la fonction euclidienne, elle, le permet.

Exemple de référence : Suivre exactement la division de 29 par 6

Au troisième passage, par exemple, l’état d’entrée est \((q,r)=(2,17)\). D’abord \(q\) devient \(3\), puis \(r\) devient \(17-6=11\). Les deux changements se compensent dans \(6q+r\). C’est pourquoi il faut conserver les deux affectations, même si le résultat final semble facile à deviner.

Algorithme : Lister les diviseurs positifs par paires

Entrée : un entier \(N\geq1\). Pour chaque diviseur \(d\), son partenaire est \(N/d\). Si les deux partenaires étaient strictement supérieurs à \(\sqrt N\), leur produit serait supérieur à \(N\). Il suffit donc de tester \(d^2\leq N\), sans calculer une racine approchée.

def diviseurs_positifs(n):
    if n < 1:
        raise ValueError("n doit etre strictement positif")
    liste = []
    d = 1
    while d * d <= n:
        if n % d == 0:
            e = n // d
            liste.append(d)
            if e != d:
                liste.append(e)
        d = d + 1
    return sorted(liste)

append ajoute un élément à la liste ; sorted renvoie les éléments dans l’ordre croissant. Le test e != d évite de répéter la racine entière lorsque \(N\) est un carré.

Invariant et correction. Au début du test de \(d\), tous les candidats de \(1\) à \(d-1\) ont été examinés. La liste contient exactement les diviseurs qu’ils ont révélés et leurs partenaires. Un ajout n’est effectué que si le reste est nul : chaque nombre ajouté divise \(N\). La nouvelle valeur \(d+1\) conserve cette description. À l’arrêt, tous les petits facteurs possibles sont examinés ; la propriété des paires garantit l’exhaustivité. Aucun grand partenaire n’est ajouté deux fois : des petits facteurs différents ont des quotients \(N/d\) différents. Le seul chevauchement possible est \(d=e\), traité par le test.

Terminaison. Le candidat \(d\) augmente d’une unité, et la boucle s’arrête dès que \(d^2>N\). Il n’y a donc qu’un nombre fini de tests.

Exemple. Pour \(N=63\), on teste \(d=1,2,3,4,5,6,7\), puis \(8^2>63\). Les restes sont respectivement \(0,1,0,3,3,3,0\). Les paires retenues sont \((1,63)\), \((3,21)\) et \((7,9)\). La liste finale est \([1,3,7,9,21,63]\).

Algorithme : Multiplier en réduisant à chaque étape

Pour trouver le reste d’une grande puissance, il n’est pas nécessaire de construire d’abord l’entier gigantesque. Les entrées sont \(a\in\mathbb{Z}\), \(e\in\mathbb{N}\) et \(m\geq1\). Un exposant nul correspond, dans cet algorithme, au produit vide, de valeur \(1\). Si la base et l’exposant sont tous les deux nuls, le programme renvoie donc le reste de 1 par convention. Cela ne définit pas l’expression mathématique \(0^0\), laissée non définie dans le reste du cours : les preuves ci-dessous décrivent des produits de facteurs, y compris le produit vide.

def puissance_modulaire(a, exposant, module):
    if exposant < 0 or module < 1:
        raise ValueError("exposant >= 0 et module >= 1 requis")
    produit = 1 % module
    base = a % module
    for _ in range(exposant):
        produit = (produit * base) % module
    return produit

range(exposant) organise exactement \(e\) passages. Le symbole _ signifie ici que l’indice de boucle n’est pas utilisé.

Démonstration complète. Après \(j\) passages, produit est le reste du produit de \(j\) facteurs égaux à \(a\). C’est vrai pour \(j=0\), car l’initialisation donne le reste de \(1\). Si c’est vrai au rang \(j\), multiplier par \(\texttt{base}\equiv a\pmod m\), puis prendre le reste, donne celui de \(j+1\) facteurs. Après \(e\) passages, on obtient donc le résultat voulu. Chaque valeur stockée est entre \(0\) et \(m-1\).

Trace courte : pour \(5^4\) modulo \(17\), les produits stockés sont

Algorithme : Puissance modulaire par carrés successifs

Le programme précédent fait \(e\) passages. On peut faire beaucoup moins en divisant l’exposant restant par deux à chaque passage. produit accumule les facteurs déjà sélectionnés ; base est le facteur courant ; k est l’exposant qu’il reste à traiter. Les mêmes préconditions que précédemment s’appliquent.

def puissance_rapide(a, exposant, module):
    if exposant < 0 or module < 1:
        raise ValueError("exposant >= 0 et module >= 1 requis")
    produit = 1 % module
    base = a % module
    k = exposant
    while k > 0:
        if k % 2 == 1:
            produit = (produit * base) % module
        base = (base * base) % module
        k = k // 2
    return produit

Invariant. Si les valeurs courantes sont \(P,A,k\) et si l’exposant initial vaut \(e\), on décrit par l’écriture suivante le produit accumulé suivi des facteurs restant à traiter :

Démonstration complète. Initialement, \(P\equiv1\), \(A\equiv a\) et \(k=e\), donc l’invariant est vrai. Écrivons l’ancien exposant \(k=2h+s\), où \(s=0\) ou \(s=1\).

• S’il est pair, \(s=0\). On conserve \(P\), puis on remplace \(A\) par \(A^2\) et \(k\) par \(h\). Le produit représenté devient \(P(A^2)^h=PA^{2h}=PA^k\).

• S’il est impair, \(s=1\). On remplace d’abord \(P\) par \(PA\), puis \(A\) par \(A^2\) et \(k\) par \(h\). Le produit représenté devient \((PA)(A^2)^h=PA^{2h+1}=PA^k\).

Les prises de reste conservent chaque congruence. L’invariant est donc vrai après un passage complet. Si \(k>0\), alors \(0\leq k\mathbin{//}2<k\) : l’entier naturel \(k\) diminue strictement et atteint \(0\). À cet instant, il n’y a plus de facteur à traiter : \(P\equiv a^e\pmod m\). Comme \(0\leq P<m\), \(P\) est le reste demandé.

Pourquoi cet ordre ? Le produit doit éventuellement recevoir l’ancienne base. Si l’on élève la base au carré avant cette multiplication, on sélectionne un mauvais facteur. Le test de parité doit également utiliser l’ancien \(k\), avant sa division par deux.

Exemple de référence : Calculer le reste de \(5^{13}\) modulo \(17\)

Chaque ligne donne l’état avant un test ou à la sortie. Les nombres intermédiaires sont volontairement conservés dans la colonne d’explication.

Contrôle. Une vérification indépendante utilise \(13=8+4+1\). On trouve \(5^2\equiv8\), \(5^4\equiv13\), \(5^8\equiv16\pmod{17}\), donc

Essai guidé : Du test à une trace complète

1. Prévoir euclidienne(-47, 6) à l’aide de deux multiples consécutifs de \(6\).

2. Pour diviseurs_positifs(49), quel test évite de placer deux fois \(7\) ?

3. Compléter les états \((k,A,P)\) de la puissance rapide pour \(7^{10}\) modulo \(11\), en partant de \((10,7,1)\).

Correction expliquée.

1. \(6\times(-8)=-48\leq-47<-42=6\times(-7)\). Donc \(q=-8\) et \(r=-47-(-48)=1\).

2. Au candidat \(d=7\), le partenaire est \(e=49\mathbin{//}7=7\). Le test e != d est faux : on n’ajoute pas une seconde fois le partenaire. Le résultat est \([1,7,49]\).

3. Les états sont \((10,7,1)\), \((5,5,1)\), \((2,3,5)\), \((1,9,5)\), \((0,4,1)\). Détails : \(49\equiv5\), \(25\equiv3\), \(9\equiv9\), puis \(5\times9=45\equiv1\) et \(9^2=81\equiv4\pmod{11}\). Le reste final est \(1\).

À toi : Prévoir avant d’exécuter

Faire la trace de la division par soustractions de \(31\) par \(7\). Puis trouver avec la puissance rapide le reste de \(3^{11}\) modulo \(7\). Vérifier les deux résultats par un calcul indépendant.

Indice. Pour la première trace, commencer par \((q,r)=(0,31)\). Pour la seconde, écrire les trois colonnes \(k,A,P\) et ne modifier \(P\) que si l’ancien \(k\) est impair.

Correction expliquée. La division donne successivement \((0,31)\), \((1,24)\), \((2,17)\), \((3,10)\), \((4,3)\). Comme \(3<7\), on s’arrête ; \(31=7\times4+3\) confirme quotient et reste.

Pour la puissance, les états sont

Justifier : Pourquoi un résultat correct ne suffit-il pas ?

Un programme de division réussit pour \((a,b)=(29,6)\). Un élève en conclut : « Il est correct pour toute entrée. » Rédiger une réponse qui distingue test, preuve de correction et preuve de terminaison.

Correction expliquée. Un test vérifie une seule entrée. Un programme qui utilise le mauvais test \(r>b\) au lieu de \(r\geq b\) réussit pour \(29,6\), car il arrive au reste \(5\), mais échoue si le reste intermédiaire devient exactement \(b\). Pour une preuve générale, on établit l’égalité invariante \(a=bq+r\), les bornes, la conservation après chaque passage, puis l’arrêt grâce à la décroissance d’un entier naturel. Enfin, le test d’arrêt doit donner \(r<b\), pas seulement \(r\leq b\).

Critères de réussite. Citer une limite des tests ; identifier l’invariant ; justifier l’arrêt ; utiliser la négation exacte de la condition de boucle. Dire seulement « il faut tester plus de nombres » ne constitue pas une preuve générale.

Variation : Trois conditions qu’une trace ordinaire ne montre pas

Que doivent renvoyer les fonctions dans les situations suivantes ?

1. division_soustractions(0, 5) ;

2. puissance_rapide(12, 0, 7) puis puissance_rapide(12, 0, 1) ;

3. diviseurs_positifs(0).

Correction expliquée. Dans le premier cas, l’état initial est \((0,0)\) et le test \(0\geq5\) est faux : résultat \((0,0)\), conforme à \(0=5\times0+0\). Dans le deuxième, \(k=0\) dès le départ : aucune multiplication ; le reste du produit vide \(1\) vaut \(1\) modulo 7 mais \(0\) modulo 1. D’où l’initialisation 1 % module, et non toujours 1. Dans le troisième, l’entrée doit être refusée : zéro a une infinité de diviseurs positifs, donc aucune liste finie ne peut en contenir tous les éléments.

Réparation : « J’ai un reste égal au diviseur »

Première erreur : remplacer while r >= b par while r > b. Pour \(a=18\), \(b=6\), la version fautive donne \((0,18)\), \((1,12)\), \((2,6)\), puis s’arrête. L’égalité \(18=6\times2+6\) est vraie, mais ce n’est pas une division euclidienne : le reste doit être strictement inférieur à \(6\).

Rappel et exemple plus simple. Pour \(a=b=4\), il faut encore retirer une fois \(4\). Le résultat correct est \(q=1,r=0\), pas \(q=0,r=4\). Le test doit donc accepter l’égalité : \(r\geq b\).

Nouvel essai : refaire la trace corrigée de \(12\) par \(4\).

Correction expliquée. \((0,12)\to(1,8)\to(2,4)\to(3,0)\). Le dernier test \(0\geq4\) est faux ; \(12=4\times3+0\) et \(0\leq0<4\). Revenir ensuite à \(18\) par \(6\) : ajouter le passage manquant \((2,6)\to(3,0)\). Le contrôle des bornes permet de localiser l’erreur, même si l’égalité seule reste vraie.

Reprise différée : Lors d’une prochaine séance, sans relire d’abord

Prévoir euclidienne(-94, 7), les diviseurs positifs de \(81\), puis le reste de \(2^{20}\) modulo \(9\). Pour chaque réponse, donner un contrôle et expliquer un cas limite de l’algorithme employé.

Indice. Encadrer \(-94\) par des multiples de 7 ; ne pas doubler la racine entière de 81 ; pour la puissance, chercher une petite puissance congrue à 1 ou suivre les carrés.

Correction expliquée. \(-98\leq-94<-91\), donc \(q=-14\), \(r=4\), et \(-94=7\times(-14)+4\). Un dividende négatif n’autorise pas un reste négatif.

Pour 81, les paires sont \((1,81)\), \((3,27)\) et \((9,9)\). Les candidats de 1 à 9 ont été examinés ; les autres \(2,4,5,6,7,8\) ne divisent pas 81. Le résultat est \([1,3,9,27,81]\), avec une seule occurrence de 9.

Enfin, \(2^6=64\equiv1\pmod9\), et \(20=6\times3+2\). Donc \(2^{20}\equiv1^3\times2^2\equiv4\pmod9\). Une trace par carrés donne également 4. Pour un exposant nul, on renverrait le reste de 1 sans entrer dans la boucle ; pour le module 1, ce reste serait 0.

À retenir : Exactitude, états et preuve

Les entiers, // et % sont les outils naturels de ces programmes. Une trace respecte l’ordre des affectations. Une justification complète relie préconditions, invariant, terminaison et conditions de sortie. Réduire après chaque produit conserve un reste ; les carrés successifs traitent l’exposant beaucoup plus rapidement. Une liste de tests réussis ne remplace jamais cette justification.

Remarque : Un prolongement indépendant du parcours principal

Cette unité est facultative. Elle explique deux prolongements accessibles avec les outils du chapitre : écrire un entier dans une autre base et produire les décimales d’un rationnel. Aucun résultat du parcours principal ne suppose sa lecture. Il n’est pas nécessaire de connaître PGCD, Bézout, Gauss, les groupes ou les anneaux.

Repérage : Place du chiffre et rôle du reste

On a \(13=2\times6+1\). Pour écrire treize en base 6, faut-il écrire \(21\) ou \(12\) ? Expliquer sans se fier à la façon de prononcer les deux chiffres.

Correction expliquée. En base 6, la place de gauche vaut des paquets de 6, celle de droite des unités. On écrit donc \((21)_6\), car \(2\times6+1=13\). En revanche, \((12)_6=1\times6+2=8\). Si l’ordre te paraît arbitraire, reprends le tableau des positions dans la définition suivante : il fait partie du sens de l’écriture.

Avant les décimales. Pour développer \(3/4\), on calcule \(30=4\times7+2\). Le premier chiffre après la virgule est-il \(7\) ou \(2\) ?

Correction expliquée. C’est \(7\), le quotient ; le reste \(2\) sert au calcul suivant. Si tu les confonds, reprends dans cette unité le paragraphe « Produire les décimales d’un rationnel », qui explique leur rôle.

Définition : Écriture d’un entier en base \(b\)

Soit \(b\geq2\) un entier, appelé base. Les chiffres sont les entiers \(0,1,\ldots,b-1\). Pour un entier \(N>0\), une écriture en base \(b\) est une suite de chiffres \(a_k,a_{k-1},\ldots,a_0\), avec \(a_k\neq0\), telle que

Attention : la juxtaposition des chiffres n’est pas un produit. En base 8, \((531)_8\) désigne

Convention : Au-delà du chiffre 9

Pour une base supérieure à 10, il faut des symboles supplémentaires pour certains chiffres. En base 16, dite hexadécimale, on utilise

En base 2, seuls \(0\) et \(1\) sont des chiffres. En base 8, le chiffre 8 n’est pas autorisé. La base doit donc être précisée lorsqu’une ambiguïté est possible.

Analogie : Regrouper des objets, sans changer leur nombre

Pour \(345\) objets, un regroupement par paquets de 8 donne \(43\) paquets et \(1\) objet isolé. Regrouper ces \(43\) paquets par 8 donne \(5\) grands paquets et \(3\) paquets simples. On compte donc \(5\) groupes de 64, \(3\) groupes de 8 et \(1\) unité : \((531)_8\).

Correspondance : les restes donnent les groupes incomplets, donc les chiffres ; les quotients donnent ce qu’il reste à regrouper à l’échelle suivante. Limite : il s’agit d’une image de la division euclidienne pour les entiers positifs. La démonstration ci-dessous, et non le dessin mental, garantit l’existence et l’unicité de l’écriture.

Lemme : Les quotients successifs finissent par être nuls

Soit \(b\geq2\). Si \(q\geq1\) est un entier, le quotient \(q'\) de sa division par \(b\) vérifie \(0\leq q'<q\).

Démonstration complète. De \(q=bq'+r\), avec \(r\geq0\), on tire \(bq'\leq q\), donc \(q'\leq q/b\). Comme \(b\geq2\) et \(q>0\), on a \(q/b\leq q/2<q\). Le quotient est naturel et strictement plus petit. Chaque diminution entière enlève au moins 1. En partant d’un entier \(N\), après \(j\) diminutions le quotient est donc au plus \(N-j\). Plus de \(N\) diminutions le rendraient négatif, ce qui est impossible. Les divisions successives atteignent donc le quotient 0, après un nombre fini d’étapes.

Théorème : Existence et unicité de l’écriture en base

Tout entier naturel possède une unique écriture en base \(b\geq2\), sans zéro ajouté à gauche, avec la convention spéciale \((0)_b\) pour zéro.

Démonstration complète. Existence pour \(N>0\). On divise successivement le nombre, puis les quotients :

Unicité. Dans toute écriture, \(a_0\) est le reste de la division de \(N\) par \(b\), car tous les autres termes sont multiples de \(b\) et \(0\leq a_0<b\). Il est donc imposé. Le quotient \((N-a_0)/b\) est alors imposé aussi ; sa division suivante impose \(a_1\). On recommence jusqu’au quotient 0. Tous les chiffres, et le moment où ils s’arrêtent sans zéro initial, sont donc déterminés.

Pour \(N=0\), on adopte \((0)_b\). Ajouter des zéros à gauche ne change pas une valeur, mais est exclu ici pour parler d’une écriture unique.

Méthode : Passer de l’écriture décimale à une base

Conditions : \(N\geq0\), \(b\geq2\), entiers. Traiter \(N=0\) à part.

Premier geste. Diviser \(N\) par \(b\) et écrire le quotient et le reste, avec \(0\leq r<b\).

1. Recommencer avec le quotient, jusqu’à obtenir un quotient nul.

2. Lire les restes dans l’ordre inverse de leur apparition : le premier est le chiffre des unités, donc celui de droite.

3. Traduire les valeurs 10 à 15 en lettres si la base 16 est utilisée.

Contrôle. Reconstruire \(N\) avec les puissances de la base. C’est un contrôle de valeur, pas seulement de la forme des chiffres.

Exemple de référence. Pour \(345\) en base 8 :

Pour \(173\) en base 16, \(173=16\times10+13\), puis \(10=16\times0+10\). Les chiffres lus à l’envers sont \(10,13\), donc \((AD)_{16}\), et \(10\times16+13=173\).

Algorithme : Produire les chiffres d’une base

La fonction renvoie une liste des valeurs des chiffres, du plus significatif au moins significatif. Le nombre initial n n’est pas modifié ; reste_a_convertir conserve le quotient courant.

def chiffres_base(n, base):
    if n < 0 or base < 2:
        raise ValueError("il faut n >= 0 et base >= 2")
    if n == 0:
        return [0]
    chiffres = []
    reste_a_convertir = n
    while reste_a_convertir > 0:
        chiffre = reste_a_convertir % base
        chiffres.append(chiffre)
        reste_a_convertir = reste_a_convertir // base
    return chiffres[::-1]

chiffres[::-1] renvoie la liste dans l’ordre inverse. Pour \(345\) en base 8, la liste construite est successivement \([1]\), \([1,3]\), \([1,3,5]\), puis la fonction renvoie \([5,3,1]\).

Invariant. Après \(j\) divisions, les \(j\) chiffres enregistrés sont les \(j\) chiffres de droite de \(N\), et

Méthode : Lire une écriture de gauche à droite

On peut reconstruire une valeur sans calculer séparément toutes les puissances. À partir de 0, multiplier la valeur déjà lue par la base, puis ajouter le nouveau chiffre.

def lire_base(chiffres, base):
    if base < 2 or len(chiffres) == 0:
        raise ValueError("base >= 2 et liste non vide requis")
    valeur = 0
    for chiffre in chiffres:
        if not 0 <= chiffre < base:
            raise ValueError("chiffre hors de la base")
        valeur = base * valeur + chiffre
    return valeur

Exemple : pour \([5,3,1]\) en base 8, les valeurs sont \(0\), puis \(8\times0+5=5\), puis \(8\times5+3=43\), puis \(8\times43+1=345\).

Justification. Ajouter un chiffre à droite décale tous les chiffres précédents d’une position, donc multiplie leur valeur par \(b\), puis ajoute les unités du nouveau chiffre. Ainsi, après chaque passage, valeur est celle du préfixe déjà lu. Le nombre de chiffres est fini ; la boucle termine et renvoie la valeur de l’écriture entière. Le programme refuse un chiffre hors de la base, au lieu de le traiter silencieusement comme une écriture normale.

Propriété : Somme des chiffres et somme alternée dans une base

Si \(N=(a_ka_{k-1}\ldots a_0)_b\), avec \(b\geq2\), alors

Démonstration complète. On a \(b-1\mid b-1\), donc \(b\equiv1\pmod{b-1}\). En multipliant cette congruence, \(b^i\equiv1\) pour tout \(i\geq0\). De même, \(b-(-1)=b+1\) donne \(b\equiv-1\pmod{b+1}\), donc \(b^i\equiv(-1)^i\). Remplacer chaque puissance dans \(N=a_kb^k+\cdots+a_1b+a_0\) et additionner donne les deux résultats. Pour \(b=2\), le premier module est 1 : tous les entiers y sont congrus, ce cas est correct mais sans intérêt pour distinguer les nombres.

Corollaire, démontré par ces congruences : \(b-1\) divise \(N\) si et seulement s’il divise la somme des chiffres ; \(b+1\) divise \(N\) si et seulement s’il divise la somme alternée. En effet, deux entiers dont la différence est un multiple du module sont soit tous deux divisibles par lui, soit tous deux non divisibles.

Exemple : Deux contrôles en base 8 et en base 16

Pour \((531)_8=345\), la somme des chiffres est \(5+3+1=9\). Donc \(345\equiv9\equiv2\pmod7\). La somme alternée, calculée à partir de la droite, est \(1-3+5=3\) : \(345\equiv3\pmod9\). Contrôles directs : \(345=7\times49+2=9\times38+3\).

Pour \((2AF)_{16}\), les valeurs des chiffres sont \(2,10,15\). Sa valeur décimale est

Limite : on ne peut pas garder les modules 9 et 11 lorsque la base change. Ils proviennent de \(10-1\) et \(10+1\) en base 10 ; dans une autre base, il faut reprendre le raisonnement.

Essai guidé : Écrire 157 en base 8

Compléter \(157=8\times\square+\square\), puis diviser le quotient à son tour. Lire les restes dans le bon sens et contrôler la valeur. Trouver ensuite le reste de 157 modulo 7 avec les chiffres obtenus.

Correction expliquée. \(157=8\times19+5\), \(19=8\times2+3\), \(2=8\times0+2\). Les restes sont \(5,3,2\), donc \(157=(235)_8\). Le contrôle donne \(2\times64+3\times8+5=128+24+5=157\). La somme \(2+3+5=10\) est congrue à 3 modulo 7 ; ainsi \(157\equiv3\pmod7\). Directement, \(157=7\times22+3\).

À toi : Une écriture binaire à construire

Écrire 94 en base 2. Reconstituer ensuite 94 à partir de l’écriture obtenue. Quelle écriture le programme doit-il renvoyer pour zéro ?

Indice. Les restes des divisions par 2 valent 0 ou 1. Conserver tous les restes, y compris les zéros au milieu et à la fin.

Correction expliquée. Les divisions successives sont

Définition et méthode : Produire les décimales d’un rationnel

Considérons \(a/b\), avec \(a\geq0\) et \(b\geq1\) entiers. Sa partie entière est le quotient \(q\) de \(a\) par \(b\), et le reste initial est \(r_0\) :

Premier geste. Écrire le reste initial avant de chercher une décimale. Ne pas confondre le quotient, qui est le chiffre à écrire, et le reste, qui sert au passage suivant.

Contrôle. À chaque ligne, vérifier \(10\times\text{ancien reste}=b\times\text{chiffre}+\text{nouveau reste}\) et les bornes du nouveau reste. Pour une fraction négative, travailler sur sa valeur absolue puis remettre le signe moins.

Propriété : Ce que représente chaque étape de la division décimale

Après \(k\) chiffres, pour \(k\geq1\),

Démonstration complète. D’abord, \(a/b=q+r_0/b\). La première division donne \(10r_0=bd_1+r_1\). En divisant les deux membres par \(10b\neq0\),

Enfin, \(0\leq r_k<b\) implique

Théorème : Une écriture décimale rationnelle finit ou devient périodique

La division précédente a deux comportements possibles :

• un reste devient nul ; tous les chiffres suivants sont alors nuls : l’écriture décimale est finie ;

• aucun reste ne devient nul ; à partir d’un certain rang, un bloc non vide de chiffres se répète indéfiniment.

Le bloc répété s’appelle une période. La répétition ne commence pas nécessairement au premier chiffre après la virgule.

Démonstration complète. Si \(r_i=0\), la division suivante est \(10\times0=b\times0+0\), puis toutes les suivantes sont identiques : seuls des zéros sont ajoutés.

Sinon, chaque reste appartient à l’ensemble fini \(\{1,2,\ldots,b-1\}\). Si \(b=1\), le reste initial est déjà nul ; ce second cas ne se présente donc pas. Pour \(b\geq2\), parmi \(b\) restes successifs non nuls, deux sont nécessairement égaux : on ne peut ranger \(b\) objets dans \(b-1\) places distinctes sans répétition. Il existe donc \(i<j\) tels que \(r_i=r_j\).

À partir de deux restes égaux, les divisions de \(10r_i\) et de \(10r_j\) par le même \(b\) ont le même quotient et le même reste, par unicité de la division euclidienne. Donc \(d_{i+1}=d_{j+1}\) et \(r_{i+1}=r_{j+1}\). Le même argument se répète à tous les rangs suivants. Le bloc de chiffres \(d_{i+1}\ldots d_j\) revient donc indéfiniment. Rien n’oblige \(i\) à être nul : il peut y avoir des chiffres avant la période.

Portée : cette preuve concerne l’écriture construite par la division. Elle ne suppose pas une factorisation du dénominateur ni un théorème sur les nombres premiers.

Exemple de référence : Une période qui ne commence pas tout de suite

Pour \(13/28\), la partie entière est 0 et le reste initial 13. Chaque ligne produit un chiffre après la virgule.

Contrôle de précision. Après deux chiffres,

Critère : Reconnaître une écriture décimale finie sans outil supplémentaire

Pour \(a\geq0\), \(b\geq1\), l’écriture produite s’arrête au plus après \(k\) chiffres si et seulement si \(b\mid10^ka\), où \(k\) est un entier naturel.

Démonstration complète. Pour \(k\geq1\), multiplier la formule précédente par \(b10^k\) donne

Exemple : \(40\mid1000\times7\), car \(7000=40\times175\). La fraction \(7/40\) possède donc au plus trois chiffres après la virgule ; la division donne précisément \(0{,}175\). Ce critère ne nécessite pas de supposer la fraction irréductible.

Algorithme : Séparer les chiffres initiaux et la période

La fonction renvoie trois objets : la partie entière, la liste des chiffres avant la période, puis la liste des chiffres de la période. Une période vide signifie que l’écriture s’arrête. Les arguments sont des entiers \(a\geq0\) et \(b\geq1\).

def developpement_decimal(a, b):
    if a < 0 or b <= 0:
        raise ValueError("il faut a >= 0 et b > 0")
    entier, reste = divmod(a, b)
    chiffres = []
    positions = {}
    while reste != 0 and reste not in positions:
        positions[reste] = len(chiffres)
        chiffre, reste = divmod(10 * reste, b)
        chiffres.append(chiffre)
    if reste == 0:
        return entier, chiffres, []
    debut = positions[reste]
    return entier, chiffres[:debut], chiffres[debut:]

positions est un dictionnaire : à chaque reste déjà rencontré, il associe le nombre de chiffres qui avaient été produits avant de traiter ce reste. len(chiffres) compte ces chiffres. Par exemple, pour \(13/28\), le reste 12 apparaît alors que deux chiffres sont déjà écrits ; on mémorise positions[12] = 2.

À la nouvelle apparition de 12, le test arrête la boucle. chiffres[:2] donne les deux premiers chiffres \([4,6]\), et chiffres[2:] donne ceux qui suivent, \([4,2,8,5,7,1]\). Le retour est donc (0, [4, 6], [4, 2, 8, 5, 7, 1]).

Invariant. Au test, chiffres contient exactement les quotients décimaux déjà produits ; reste est le reste courant ; positions conserve l’emplacement de première rencontre des restes antérieurs. L’enregistrement se fait avant de modifier le reste, pour ne pas associer l’ancien emplacement au nouveau reste. La division suivante conserve l’identité de la propriété précédente.

Terminaison et correction. Un nouveau passage enregistre un reste non nul encore absent. Il y en a au plus \(b-1\). La boucle s’arrête donc sur 0 ou sur une répétition. Dans le premier cas, le développement est fini ; dans le second, le théorème précédent justifie exactement le bloc découpé. Une répétition de chiffre ne suffit pas : c’est le reste, état de départ de la division suivante, qu’il faut mémoriser.

Essai guidé : Un développement fini

Produire les chiffres de \(7/40\), en écrivant les anciens restes, les quotients et les nouveaux restes. Quel retour donne la fonction précédente ?

Correction expliquée. La partie entière est 0 et le reste initial 7. On calcule

À toi : Repérer le bon début de la période

Déterminer par divisions successives l’écriture décimale de \(19/24\). Écrire séparément les chiffres avant la période et ceux de la période. Ne pas conclure à partir d’un simple affichage de calculatrice.

Indice. Chercher un reste qui revient. Les deux premières divisions à effectuer portent sur 190 puis 220.

Correction expliquée. La partie entière est 0. Les divisions successives sont

Justifier : Pourquoi la finitude des restes prouve-t-elle une répétition ?

Rédiger un argument expliquant pourquoi une fraction qui ne donne jamais le reste 0 finit par produire une période. Ajouter une phrase expliquant pourquoi la période n’est pas forcément immédiate.

Correction expliquée. Le dénominateur \(b\) étant fixé, les seuls restes non nuls possibles sont 1 à \(b-1\). Si l’on poursuit les divisions, un de ces restes est rencontré une seconde fois. À partir d’un même reste, la division suivante par le même \(b\) donne le même chiffre et le même nouveau reste ; le même bloc de chiffres recommence donc sans fin. La première répétition peut concerner un reste rencontré après plusieurs chiffres, pas nécessairement le reste initial. Ainsi, \(5/6=0{,}8\overline3\) : \(50=6\times8+2\), puis \(20=6\times3+2\).

Critères de réussite. Nommer le petit ensemble fini ; expliquer le passage « même reste \(\Rightarrow\) même suite de chiffres » par l’unicité de la division ; distinguer chiffres initiaux et période. Dire « la calculatrice montre beaucoup de mêmes chiffres » n’est pas une preuve.

Variation : Même chiffre, même état ?

Dans le développement de \(13/28\), le chiffre 4 apparaît au premier et au troisième rang. Peut-on en conclure que les chiffres se répètent dès le premier rang ? Comparer avec un changement de base : peut-on enlever le 0 de \((1011110)_2\) parce qu’il ne contribue pas directement à la somme ?

Correction expliquée. Non dans les deux cas. Après le premier chiffre 4 de \(13/28\), le reste est 18 ; après le troisième chiffre 4, le reste est 8. Les états sont différents et les chiffres suivants sont différents :6 après le premier,2 après le troisième. Seule la répétition du reste garantit la répétition des étapes.

Dans \((1011110)_2\), les zéros fixent des positions. Retirer le dernier 0 déplacerait tous les chiffres d’une place vers la droite et diviserait la valeur par 2 : \((101111)_2=47\), non 94. Retirer le 0 situé après le premier 1 change également les poids des chiffres. Un coefficient nul peut être indispensable pour décrire les positions.

Réparation : « J’écris le reste à la place du chiffre »

Première erreur : en divisant \(30\) par 8 pour développer \(3/8\), écrire 6 comme premier chiffre parce que \(30=8\times3+6\). Le quotient 3 est le chiffre des dixièmes ; le reste 6 sert au calcul suivant.

Rappel et exemple plus simple. Pour \(1/2\), on divise 10 par 2 : \(10=2\times5+0\). Le chiffre est 5 et le reste 0 fait s’arrêter : \(1/2=0{,}5\), pas \(0{,}0\).

Nouvel essai : développer \(7/12\) en séparant bien deux colonnes « chiffre » et « reste ».

Correction expliquée. \(70=12\times5+10\), \(100=12\times8+4\), \(40=12\times3+4\). Les chiffres sont 5,8 puis 3 répété ; les restes sont 10,4 puis 4 répété. Donc \(7/12=0{,}58\overline3\).

Retour à l’erreur : pour \(3/8\), écrire \(30=8\times3+6\), puis \(60=8\times7+4\), puis \(40=8\times5+0\). On obtient \(0{,}375\). Le contrôle \(375\times8=3000\) donne bien \((375/1000)\times8=3\).

Réparation : « J’ai lu les restes dans le sens des calculs »

Première erreur : les divisions de 157 par 8 ont donné les restes 5,3,2, et tu as écrit \((532)_8\). La première division fournit les unités : le premier reste doit être à droite.

Rappel simple. \(13=6\times2+1\), puis \(2=6\times0+2\). Les restes 1,2 donnent \((21)_6\), vérifié par \(2\times6+1=13\).

Nouvel essai : convertir 11 en base 3.

Correction expliquée. \(11=3\times3+2\), \(3=3\times1+0\), \(1=3\times0+1\). Les restes 2,0,1 se lisent \((102)_3\), et \(1\times9+0\times3+2=11\). Revenir alors à 157 : les restes 5,3,2 donnent \((235)_8\). Leur ordre est imposé par les poids 1,8,64 révélés successivement.

Reprise différée : À reprendre avant relecture

Écrire 250 en base 7 et vérifier l’écriture. Déterminer ensuite les décimales de \(3/8\) avec une trace complète. Expliquer pourquoi l’une des listes se lit à l’envers alors que l’autre reste dans l’ordre des calculs.

Indice. Pour la base 7, les divisions commencent par \(250=7\times35+5\). Pour les décimales, commencer par la partie entière 0 et le reste 3.

Correction expliquée. \(250=7\times35+5\), \(35=7\times5+0\), \(5=7\times0+5\), donc \(250=(505)_7\). Le contrôle donne \(5\times49+0\times7+5=245+5=250\).

Pour \(3/8\), les divisions \(30=8\times3+6\), \(60=8\times7+4\), \(40=8\times5+0\) donnent \(0{,}375\). Le reste 0 arrête le développement. Les divisions de base construisent d’abord les unités, puis les poids croissants : on renverse donc les chiffres pour l’écriture habituelle. Les divisions décimales construisent d’abord les dixièmes, puis les centièmes, puis les millièmes : c’est déjà l’ordre de gauche à droite après la virgule.

Critères de réussite. Chiffres autorisés ; quotients et restes distingués ; bon ordre de lecture ; reconstruction exacte ; arrêt ou répétition justifié par les restes.

À retenir : La division construit l’écriture

Une base fixe les chiffres autorisés et le poids de chaque position. Les divisions successives construisent les chiffres d’un entier, en commençant par la droite. Les congruences \(b\equiv1\pmod{b-1}\) et \(b\equiv-1\pmod{b+1}\) expliquent les critères par somme et somme alternée.

Pour un rationnel, la division de \(10\times\) le reste produit un chiffre puis un nouveau reste. Un reste nul termine l’écriture ; un reste déjà rencontré déclenche une période, éventuellement après plusieurs chiffres initiaux. C’est le retour d’un reste, non d’un chiffre isolé, qui apporte la preuve.

À retenir : Les résultats avec leurs conditions

• Pour \(a,d\in\mathbb{Z}\), \(d\mid a\) signifie \(a=dk\) avec \(k\in\mathbb{Z}\). On admet le diviseur \(0\) dans cette définition : \(0\mid a\) seulement si \(a=0\). Une fraction \(a/d\) exige toujours \(d\neq0\).

• Si \(d\mid a\) et \(d\mid b\), alors \(d\mid ua+vb\) pour tous \(u,v\in\mathbb{Z}\). Une divisibilité d’une somme ne se transmet pas forcément à chacun de ses termes.

• Si \(N\geqslant1\), les diviseurs positifs se trouvent par paires \(d,N/d\) en testant tous les \(d\) tels que \(1\leqslant d\) et \(d^2\leqslant N\). Ajouter les opposés si l’on cherche dans \(\mathbb{Z}\).

• Pour \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}\), \(b\geqslant1\), il existe un unique couple \((q,r)\in\mathbb{Z}^2\) tel que \(a=bq+r\) et \(0\leqslant r<b\). Si \(a\) est négatif, le reste n’est pas négatif pour autant.

• Pour \(m\geqslant2\), \(a\equiv b\pmod m\) signifie \(m\mid a-b\), ou, de façon équivalente, que \(a\) et \(b\) ont le même reste modulo \(m\).

• À module fixé, addition, soustraction, produit et puissance d’exposant entier au moins égal à \(1\) conservent les congruences. Une division demande une justification supplémentaire. Si \(ku\equiv kv\pmod{km}\) avec \(k\geqslant1\), alors \(u\equiv v\pmod m\) : le module change aussi.

• Si \(ca\equiv1\pmod m\), alors \(ax\equiv b\pmod m\) équivaut à \(x\equiv cb\pmod m\). Un tel \(c\) se vérifie par multiplication ; il n’existe pas toujours.

• \(x\equiv r\pmod m\) décrit tous les entiers \(x=r+mk\), \(k\in\mathbb{Z}\), et pas seulement un représentant.

• Pour \(a\in\mathbb{Z}\setminus\{0\}\), \(m\geqslant2\), \(p\geqslant1\) entier et \(n\in\mathbb{N}\), si \(a^p\equiv1\pmod m\) et si \(n=pq+r\) est la division euclidienne de \(n\) par \(p\) (\(q\in\mathbb{N}\), \(0\leqslant r<p\)), alors \(a^n\equiv a^r\pmod m\). On justifie la période \(p\) ; on ne remplace pas automatiquement l’exposant par son reste modulo \(m\).

À retenir : Le fil conducteur

Une égalité avec un témoin entier prouve une divisibilité. Une identité accompagnée des bornes prouve une division euclidienne. Un calcul modulo un entier conserve seulement l’information pertinente sur les restes. La force de l’arithmétique consiste à choisir cette information sans perdre les hypothèses, les cas limites ni le sens de la conclusion.

Méthode : Choisir la première piste

À toi : Bilan mélangé, sans méthode imposée

Chercher d’abord sans consulter les indices. Pour chaque réponse, écrire au moins une justification et un contrôle.

1. Déterminer tous les diviseurs de \(-54\) dans \(\mathbb{Z}\).

2. Trouver tous les entiers \(n\) tels que \(n+2\mid3n+13\).

3. Résoudre \(x^2-y^2=24\) dans \(\mathbb{N}^2\).

4. Donner le quotient et le reste de \(-2026\) par \(17\). Puis déterminer les entiers dont la division par \(5\) donne un quotient égal au reste augmenté de \(2\).

5. Trouver tous les entiers \(x\) compris entre \(-20\) et \(20\) tels que \(x\equiv-47\pmod9\).

6. Un élève déduit de \(6x\equiv18\pmod{24}\) que \(x\equiv3\pmod{24}\). Corriger cette transformation et décrire toutes les solutions.

7. Quel est le chiffre des unités de \(7^{2031}\) ?

8. Résoudre \(7x\equiv5\pmod{12}\) dans \(\mathbb{Z}\).

9. Le nombre \(73\,821\) est-il divisible par \(9\) ? Par \(11\) ? Justifier sans poser ces deux divisions.

10. Existe-t-il des entiers \(x,y\) tels que \(x^2+y^2=87\) ? Une affirmation sans justification ne suffit pas.

11. On fabrique un code pédagogique avec quatre chiffres \(a,b,c,d\) et une clé \(e\in\{0,\ldots,9\}\) telle que \(a+3b+c+3d+e\equiv0\pmod{10}\). Donner la clé de \(3812\), puis dire si l’échange des deux premiers chiffres est détecté. Dans un autre codage, \(y\equiv5x+7\pmod{26}\) avec \(A=0,\ldots,Z=25\) : quelle lettre a pour code \(y=0\) ?

12. On initialise \(q=0\), \(r=15\), \(b=5\), puis on répète « tant que \(r>b\) : remplacer \(r\) par \(r-b\) et \(q\) par \(q+1\) ». Qu’obtient-on ? Est-ce une division euclidienne ? Corriger le test et expliquer pourquoi la boucle corrigée s’arrête.

Indices : Une aide à choisir, seulement après une tentative

1. \(7^2<54<8^2\) ; chaque petit facteur a un partenaire.

2. Écrire \(3n+13=3(n+2)+7\) et établir les deux implications.

3. Poser \(u=x-y\), \(v=x+y\) ; \(u\) et \(v\) doivent avoir la même parité.

4. Encadrer \(-2026\) par deux multiples consécutifs de \(17\). Pour la seconde question, \(0\leqslant r<5\) et \(q=r+2\).

5. Réduire \(-47\) à un reste entre \(0\) et \(8\), puis ajouter ou retrancher \(9\).

6. Traduire la congruence par l’existence de \(k\in\mathbb{Z}\) vérifiant \(6x-18=24k\).

7. Calculer \(7^4\) modulo \(10\), puis diviser \(2031\) par \(4\).

8. \(7\times7=49\) est congru à \(1\) modulo \(12\).

9. Modulo \(9\), \(10\equiv1\) ; modulo \(11\), \(10\equiv-1\).

10. Examiner ce que peut être le reste d’un carré modulo \(4\).

11. Une clé détecte-t-elle toujours une erreur ? Pour décoder, \(5\times21\equiv1\pmod{26}\).

12. Suivre les états \((q,r)\), y compris quand \(r=b\).

Correction : Questions 1 à 3 : exhaustivité et domaines

1. On étudie \(54\), puis on ajoute les opposés. Comme \(7^2=49<54<64=8^2\), on teste \(1,2,\ldots,7\). Les paires qui conviennent sont \((1,54)\), \((2,27)\), \((3,18)\) et \((6,9)\). Les autres petits candidats ne divisent pas \(54\) : \(4\times13=52<54<56=4\times14\) ; \(5\times10=50<54<55=5\times11\) ; \(7\times7=49<54<56=7\times8\). La liste est donc

2. Si \(n+2\mid3n+13\), alors \(n+2\) divise

3. Factoriser : \((x-y)(x+y)=24\). Comme \(x,y\geqslant0\) et \(x^2-y^2>0\), on a \(x>y\), donc \(u=x-y>0\) et \(v=x+y\geqslant u\). Les paires positives \(u\leqslant v\) sont \((1,24),(2,12),(3,8),(4,6)\). Les formules

Contrôle. \(7^2-5^2=49-25=24\) et \(5^2-1^2=25-1=24\). Le domaine \(\mathbb{N}^2\) explique pourquoi on n’ajoute pas des coordonnées négatives.

Correction : Questions 4 à 6 : restes et transformation correcte

4. \(17\times(-120)=-2040\) et \(17\times(-119)=-2023\). Ainsi

Pour la seconde partie, écrire \(a=5q+r\), \(0\leqslant r<5\), et \(q=r+2\). Alors \(a=5(r+2)+r=5r+10+r=6r+10\). Pour \(r=0,1,2,3,4\), on trouve respectivement \(a=10,16,22,28,34\). Ces cinq valeurs conviennent : les quotients associés sont \(2,3,4,5,6\) et les restes sont bien dans la plage autorisée.

5. \(-47=9\times(-6)+7\), donc \(-47\equiv7\pmod9\). Tous les candidats s’écrivent \(x=7+9k\) avec \(k\in\mathbb{Z}\). Les bornes donnent

6. La congruence signifie \(6x-18=24k\) pour un entier \(k\). Diviser cette égalité par \(6\neq0\) donne \(x-3=4k\). Ainsi

Correction : Questions 7 à 10 : calculer, puis interpréter

7. \(7^2=49\equiv9\pmod{10}\), \(7^3\equiv9\times7=63\equiv3\pmod{10}\), et \(7^4=2401\equiv1\pmod{10}\). Cette dernière égalité justifie une période de \(4\) pour le calcul. Comme \(2031=4\times507+3\),

8. \(7\times7=49=12\times4+1\), donc \(7\) est un inverse de \(7\) modulo \(12\). Multiplier \(7x\equiv5\pmod{12}\) par \(7\) donne \(49x\equiv35\pmod{12}\), puis \(x\equiv11\pmod{12}\). Réciproquement, si \(x=11+12k\), alors \(7x=77+84k=5+12(6+7k)\), donc \(7x\equiv5\pmod{12}\). Toutes les solutions sont \(x=11+12k\), \(k\in\mathbb{Z}\).