Divisibilité et congruences · Terminale maths expertes

Avant de commencer5 questions pour vérifier tes bases

Pourquoi ce chapitre ?

Le problème fondamental : résoudre dans les entiers

Pour partager 23 objets en lots de 5, le quotient réel 4,6 n'est pas le résultat attendu : tu obtiens 4 lots et 3 objets restants. En arithmétique, la contrainte entière change la question. Nous allons formaliser cette idée de reste, puis l'utiliser pour remplacer certains calculs immenses par quelques possibilités.

Prérequis. Entiers relatifs, multiples, distributivité, puissances, division d'entiers positifs, preuve par contraposée ou par l'absurde. On note $\N=\{0,1,2,\ldots\}$ et $\Z$ l'ensemble des entiers relatifs.

Le cours suit le socle officiel. Le problème de chiffrement affine est une application guidée ; la méthode générale pour inverser un entier modulo $$n$$ sera démontrée dans la fiche 5.

L'idée avant la formule

Plusieurs entiers, un même reste

Les entiers 3, 10 et 17 ont le même reste modulo 7. Ils restent différents comme entiers, mais se comportent de la même manière si l'on ne regarde que le jour de la semaine. Leur différence est un multiple de 7 : c'est cette propriété exacte que la notation de congruence retiendra.

Un reste positif même en reculant

Reculer de 2 jours produit le même décalage qu'avancer de 5 jours. L'écriture $$-2=7(-1)+5$$ possède un reste entre 0 et 6. Le quotient $$-1$$ compte un tour en arrière ; le reste 5 donne une position autorisée. Cette lecture évite de confondre le signe du nombre et celui du reste.

Détecter une impossibilité avant de chercher

Un carré entier est congru à 0 ou à 1 modulo 4. Une somme de deux carrés ne peut donc être congrue à 3. On pourra ainsi exclure une équation entière sans essayer tous les couples. Attention au sens logique : franchir un test modulaire ne garantit pas qu'une solution entière existe.

Le cours formel

Divisibilité dans les entiers relatifs

Par exemple $-3\mid12$ car $$12=(-3)(-4)$$ . Tout entier divise 0 car $0=a\times0$ . L'égalité $0\mid b$ n'est vraie que pour $$b=0$$ . Pour un entier non nul $$b$$ , ses diviseurs entiers viennent par paires opposées ; on précise « positifs » si l'on veut seulement ceux de $\N^*$ .

Démonstration · Revenir à l'égalité

Transitivité. Dire $a\mid b$ signifie qu'il existe un entier $$k$$ tel que $$b=ak$$ . Dire $b\mid c$ signifie qu'il existe un entier $\ell$ tel que $c=b\ell$ . Remplaçons $$b$$ dans cette seconde égalité :

\begin{aligned}c &= (ak)\ell\\[.35em] &= a(k\ell).\end{aligned}

Comme le produit $k\ell$ est un entier, nous avons exhibé le quotient entier qui prouve $a\mid c$ .

Combinaison linéaire. Si $d\mid a$ et $d\mid b$ , écrivons $$a=dr,b=ds$$ avec $r,s\in\Z$ . Alors

\begin{aligned}ua+vb &= u(dr)+v(ds)\\[.35em] &= d(ur+vs).\end{aligned}

Si $$u,v$$ sont entiers, $$ur+vs$$ est entier : c'est la condition nécessaire pour conclure à la divisibilité. La preuve reste valable pour des coefficients négatifs.

Divisibilité dans les deux sens. Si $a,b\ne0$ et $$b=ak$$ , alors $k\ne0$ . Un entier non nul a une valeur absolue au moins 1, donc $|b|=|a||k|\ge|a|$ . L'hypothèse inverse $b\mid a$ donne de même $|a|\ge|b|$ . Les deux inégalités imposent $$|a|=|b|$$ . On ne conclut pas nécessairement $$a=b$$ : les entiers opposés, par exemple 2 et $$-2$$ , se divisent aussi mutuellement.

À toi d’essayer

Transformer le symbole en égalité

Si d divise a et b, prouve qu’il divise $$5a-2b$$ . Pourquoi les coefficients entiers comptent-ils ?

Pour démarrer. Remplace chaque divisibilité par une égalité avec un quotient entier.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Écris $$a=du$$ et $$b=dv$$ avec u,v entiers.

Indice 2 · Un pas de plus

Factorise d dans la combinaison.

Voir l’explication

Puisque $d\mid a$ , il existe $u\in\Z$ tel que $$a=du$$ ; de même $$b=dv$$ avec $v\in\Z$ . Alors

\begin{aligned}5a-2b &= 5du-2dv\\[.35em] &= d(5u-2v).\end{aligned}

La parenthèse est entière, ce qui prouve la divisibilité par définition. Avec des coefficients réels arbitraires, ce quotient ne serait plus garanti entier : 2 divise 2, mais multiplier 2 par $$1/2$$ donne 1, que 2 ne divise pas. La nature entière des coefficients est donc une hypothèse utilisée dans la preuve.

Division euclidienne : existence et unicité

Démonstration · Pourquoi ce couple existe et est unique

Construire un couple. Le symbole $\lfloor x\rfloor$ désigne le plus grand entier inférieur ou égal à $$x$$ . Par exemple $\lfloor3{,}4\rfloor=3$ et $\lfloor-3{,}4\rfloor=-4$ . Choisissons $q=\lfloor a/b\rfloor$ . Par définition, $q\le a/b<q+1$ . Comme $$b>0$$ , multiplier conserve les sens : $bq\le a<bq+b$ . Soustraire $$bq$$ donne $0\le a-bq<b$ .

Posons $$r=a-bq$$ . Il est entier puisque $$a,b,q$$ le sont ; l'encadrement précédent dit qu'il est un reste autorisé. Sa définition donne aussi $$a=bq+r$$ . Cela prouve l'existence.

Montrer qu'il ne peut y en avoir deux. Supposons

\begin{aligned}a &= bq+r\\[.35em] &= bq'+r'\end{aligned}

avec $0\le r,r'<b$ . En soustrayant, $$b(q-q')=r'-r$$ . Comme les deux restes sont entre 0 et $$b-1$$ , leur différence est strictement entre $$-b$$ et $$b$$ . Or les multiples de $$b$$ les plus proches de zéro sont $$-b,0,b$$ ; le seul dans cet intervalle ouvert est 0. Donc $$b(q-q')=0$$ . Puisque $b\ne0$ , $$q=q'$$ , et l'égalité initiale impose alors $$r=r'$$ . Les bornes du reste sont donc ce qui assure l'unicité.

À toi d’essayer

Corriger un reste

On écrit $$-17=4(-4)-1$$ . Trouve la division euclidienne correcte.

Pour démarrer. Diminue le quotient de 1 et compense en ajoutant 4 au reste.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le reste doit être positif ou nul.

Indice 2 · Un pas de plus

Remplace $$-4$$ par $$-5$$ et compense.

Voir l’explication

L'égalité initiale est vraie mais son reste $$-1$$ est négatif. Remplacer $$-4$$ par $$-5$$ retire 4 au produit, donc il faut ajouter 4 au reste : $$-1+4=3$$ . Ainsi $$-17=4(-5)+3$$ . Le calcul $$-20+3=-17$$ vérifie l'égalité et $0\le3<4$ vérifie la borne. Pour $$-18$$ , le même quotient donne

\begin{aligned}r &= -18-(-20)\\[.35em] &= 2,\end{aligned}

donc $$-18=4(-5)+2$$ , avec un reste encore autorisé.

Congruences : oublier le quotient, garder le reste

Une congruence ne signifie pas une égalité : $17\equiv2\pmod5$ mais $17\ne2$ . Elle dépend du module : $17\not\equiv2\pmod4$ . Pour $$n=1$$ , tous les entiers sont congrus.

Chaque entier se place dans l'une des cinq classes de restes. Après 4, ajouter 1 ramène à 0 ; cela ne veut pas dire que les entiers 4 et 5 sont égaux.

À toi d’essayer

Même reste ne signifie pas même nombre

Pourquoi $-8\equiv7\pmod5$ ? Donne leur reste commun, puis un module pour lequel ils ne sont pas congrus.

Pour démarrer. Soustrais les nombres, puis cherche leurs deux divisions euclidiennes.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La différence vaut moins quinze.

Indice 2 · Un pas de plus

Écris $$-8=5(-2)+2$$ et $$7=5+2$$ .

Voir l’explication

La différence est

\begin{aligned}-8-7 &= -15\\[.35em] &= 5(-3),\end{aligned}

donc les deux nombres sont congrus modulo 5. Les divisions confirment $$-8=5(-2)+2$$ et $7=5\times1+2$ : même reste 2. Modulo 2, en revanche, $$-8=2(-4)$$ a reste 0 et $7=2\times3+1$ a reste 1. Ils ne sont donc pas congrus modulo 2. Une congruence indique une égalité de restes relativement à un module précis, pas une égalité des nombres.

Calculer avec les congruences

Démonstration · Les opérations permises

Les hypothèses signifient $$a=b+nu$$ et $$c=d+nv$$ pour des entiers $$u,v$$ .

Pour les sommes,

\begin{aligned}(a+c)-(b+d) &= (b+nu+d+nv)-(b+d)\\[.35em] &= n(u+v)\end{aligned}

leur différence est un multiple de $$n$$ . Pour les différences, le même calcul donne $$(a-c)-(b-d)=n(u-v)$$ .

Pour les produits, développons les quatre termes :

\begin{aligned}ac &= (b+nu)(d+nv)\\[.35em] &= bd+bnv+dnu+n^2uv.\end{aligned}

Donc $$ac-bd=n(bv+du+nuv)$$ , encore un multiple de $$n$$ car la parenthèse est entière. Cela autorise les remplacements dans une addition, une soustraction ou une multiplication.

Pour les puissances, au rang 0 les deux valeurs sont 1, donc congrues. Si $a^k\equiv b^k$ , la propriété du produit, appliquée aussi à $a\equiv b$ , donne

\begin{aligned}a^{k+1} &= a^ka\equiv b^kb\\[.35em] &= b^{k+1}.\end{aligned}

Par récurrence, la propriété vaut pour tout $k\ge0$ . Nous n'avons pas démontré de règle de division : elle nécessite d'autres conditions.

À toi d’essayer

Réparer une simplification interdite

Résous $2x\equiv2\pmod6$ sans diviser abusivement en gardant le module 6.

Pour démarrer. Écris $$2(x-1)=6k$$ avec $$k$$ entier avant de simplifier.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Écris la divisibilité de 2x moins 2 par 6.

Indice 2 · Un pas de plus

$$2(x-1)=6k$$ équivaut à $$x-1=3k$$ .

Voir l’explication

La définition donne $6\mid(2x-2)$ , soit $$2(x-1)=6k$$ pour un entier $$k$$ . Diviser cette égalité par 2 donne $$x-1=3k$$ , donc les solutions sont $$x=1+3k$$ . Pour $$k$$ pair, elles ont reste 1 modulo 6 ; pour $$k$$ impair, reste 4. Les valeurs 1 et 4 vérifient bien l'équation initiale puisque $2\times1=2$ et

\begin{aligned}2\times4 &= 8\\[.35em] &= 6+2.\end{aligned}

Le module devient 3 après la simplification ; conserver 6 ferait perdre une classe.

Puissances et raisonnements par restes

Pour trouver $a^N\pmod n$ , calcule quelques puissances réduites. Si $a^t\equiv1\pmod n$ , écris $$N=tq+r$$ : $a^N\equiv a^r$ . Il faut avoir établi le cycle avant de l'utiliser.

Une preuve à construire

Trois entiers consécutifs

Montre que $$n(n+1)(n+2)$$ est divisible par 3 pour tout entier relatif $$n$$ .

Pour démarrer. Liste les trois restes possibles de $$n$$ et repère le facteur de reste zéro.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Examine le reste de n modulo 3.

Indice 2 · Un pas de plus

Parmi trois entiers consécutifs, l'un a un reste nul.

Voir la preuve expliquée

Si $$n=3k$$ , le premier facteur est divisible par 3. Si $$n=3k+1$$ , alors

\begin{aligned}n+2 &= 3k+3\\[.35em] &= 3(k+1)\end{aligned}

l'est. Si $$n=3k+2$$ , alors $$n+1=3k+3$$ l'est. Dans chaque cas, le produit contient un facteur $3\ell$ et peut s'écrire 3 fois un entier. Ces trois restes couvrent tout $n\in\Z$ , y compris négatif. Pour la variante, parmi $$n$$ et $$n+1$$ , l'un est pair : si $$n$$ est impair, son successeur est pair. Le produit contient donc aussi un facteur 2.

À toi d’essayer

Une table de restes est une preuve finie

Quels restes peut prendre un carré modulo 3 ? Déduis que $$x^2+y^2=3m+2$$ impose x et y non divisibles par 3.

Pour démarrer. Construis la liste des carrés de 0, 1 et 2 modulo 3, puis celle de leurs sommes.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Teste les trois restes 0, 1 et 2.

Indice 2 · Un pas de plus

Pour obtenir 2, quelle somme de deux restes parmi 0 et 1 convient ?

Voir l’explication

Les restes possibles de $$x$$ sont 0,1,2 ; leurs carrés donnent 0,1,4, soit 0,1,1 modulo 3. Un carré n'a donc que les restes 0 ou 1. Pour que $$x^2+y^2$$ ait le reste 2, les quatre sommes possibles sont $$0+0=0$$ , $$0+1=1$$ , $$1+0=1$$ , $$1+1=2$$ : seule la dernière convient. Chaque carré doit donc avoir reste 1. Cela exclut que $$x$$ ou $$y$$ soit divisible par 3, car son carré aurait alors reste 0. La condition est nécessaire pour une solution, mais ne suffit pas à résoudre l'équation entière pour un $$m$$ donné.

Démontrer les tests de divisibilité

Un entier naturel d'écriture décimale $a_ma_{m-1}\cdots a_0$ vaut $N=\sum_{k=0}^m a_k10^k$ , où chaque chiffre est entre 0 et 9.

Pour 2, 5 ou 10, écrivons $$N=10q+a_0$$ . Le module divise $$10q$$ , donc $N\equiv a_0$ : seul le chiffre des unités compte. Pour 4 ou 25, écrivons $$N=100q+(10a_1+a_0)$$ . Comme 100 est multiple du module, le premier terme a reste zéro ; on teste donc l'entier formé par les deux derniers chiffres. Pour 8 ou 125, $1000=8\times125$ est multiple des deux modules : écrire $$N=1000q+r$$ , avec $$r$$ formé des trois derniers chiffres, prouve de même $N\equiv r$ .

À toi d’essayer

Retrouver un test par la base dix

Pourquoi les deux derniers chiffres suffisent-ils pour tester la divisibilité par 4 ?

Pour démarrer. Sépare la partie des centaines et le nombre formé par les deux derniers chiffres.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Écris le nombre sous la forme $$100q+r$$ , avec $0\le r<100$ .

Indice 2 · Un pas de plus

100 est un multiple de 4.

Voir l’explication

Tout entier naturel s'écrit $$N=100q+r$$ avec $0\le r<100$ . Le nombre $$r$$ correspond aux deux derniers chiffres, y compris un zéro initial éventuel. Comme $100=4\times25$ , $$N-r=4(25q)$$ est divisible par 4. Donc $$N$$ et $$r$$ ont le même reste modulo 4 : l'un est divisible par 4 si et seulement si l'autre l'est. Pour 3128,

\begin{aligned}r &= 28\\[.35em] &= 4\times7;\end{aligned}

donc 3128 est divisible par 4. En effet $3128=4\times782$ .

Algorithmes et précautions de programmation

Pour un diviseur positif, Python fournit quotient et reste via // et %. Il s'agit de la division avec quotient arrondi vers le bas, ce qui respecte la division euclidienne aussi pour un dividende négatif.

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

def puissance_mod(a, n, m):
    if n < 0 or m <= 0:
        raise ValueError("n >= 0 et m > 0 requis")
    resultat = 1 % m
    for _ in range(n):
        resultat = (resultat * a) % m
    return resultat

Avant la boucle. Aucun facteur $$a$$ n'a encore été multiplié. La variable contient le reste de 1 modulo $$m$$ , donc elle est congrue à $$a^0=1$$ et appartient à $\{0,\ldots,m-1\}$ . Cela reste vrai pour $$m=1$$ , où le seul reste est 0.

Pendant un tour. Supposons qu'après $$k$$ tours, la variable soit congrue à $$a^k$$ . La multiplier par $$a$$ donne un nombre congru à $a^{k+1}$ . L'opération % m remplace ce nombre par son reste : elle conserve la congruence et remet la valeur entre 0 et $$m-1$$ . La propriété se transmet donc du rang $$k$$ au rang $$k+1$$ .

À la fin. La boucle a effectué exactement $$n$$ tours, donc la variable est congrue à $$a^n$$ et dans l'intervalle des restes. L'unicité de la division euclidienne prouve qu'elle contient le reste recherché. Si $$n=0$$ , aucun tour n'est exécuté et la valeur initiale convient déjà. Cette initialisation et cette transmission constituent une preuve par récurrence, appelée invariant de boucle. La fiche 6 réduira le nombre de multiplications pour les grands exposants.

À toi d’essayer

Prévoir le résultat du code

En Python avec un diviseur positif, prévois les valeurs de $-19\,\%\,6$ et $-19\,//\,6$ sans exécuter le code.

Pour démarrer. Encadre $$-19$$ entre deux multiples consécutifs de 6.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Cherche un reste entre 0 et 5.

Indice 2 · Un pas de plus

Le multiple de 6 immédiatement inférieur à -19 est -24.

Voir l’explication

Les multiples voisins sont $$6(-4)=-24$$ et $$6(-3)=-18$$ . Le multiple inférieur est $$-24$$ , et $$-19-(-24)=5$$ . Donc $$-19=6(-4)+5$$ , avec $0\le5<6$ . Python renvoie ainsi 5 pour -19 % 6 et $$-4$$ pour -19 // 6. Un quotient $$-3$$ donnerait un reste $$-1$$ ; ce serait une troncature vers zéro, qui ne respecte pas le reste positif utilisé par Python avec un diviseur positif.

Boîte à outils : chercher le bon module

Une équation impossible modulo 3

Un chiffre inconnu dans une écriture décimale

La somme des chiffres de $$4a32$$ vaut $$4+a+3+2=a+9$$ . Puisque $$a$$ est un chiffre, $0\le a\le9$ , donc $9\le a+9\le18$ . Les seuls multiples de 9 dans cet intervalle sont 9 et 18. Résoudre $$a+9=9$$ donne $$a=0$$ ; résoudre $$a+9=18$$ donne $$a=9$$ . On obtient donc exactement 4032 et 4932. Les contrôles $9\times448=4032$ et $9\times548=4932$ confirment les deux solutions.

Si l'on ajoute la divisibilité par 11, la somme alternée depuis les unités vaut $$2-3+a-4=a-5$$ . Parmi les chiffres autorisés, seul a=5 satisferait ce second test. Aucun chiffre ne satisfait donc simultanément les deux tests. Le domaine des chiffres, de 0 à 9, est une donnée essentielle du problème.

Un cycle n'est pas toujours immédiatement inversible

Passer d'une congruence à tous les entiers

L'écriture $x\equiv4\pmod7$ ne signifie pas seulement x=4. Elle équivaut à $$x=4+7k$$ pour un entier k, positif, nul ou négatif. Si une contrainte supplémentaire impose $0\le x\le30$ , alors $0\le4+7k\le30$ , donc k=0,1,2,3 ; les valeurs sont 4,11,18,25. Les contraintes d'intervalle viennent après la résolution modulaire.

À toi d’essayer

Retrouver un chiffre

Quel chiffre a rend le nombre $$7a5$$ divisible par 9 ?

Pour démarrer. Utilise le test de 9 et rappelle qu’un chiffre est compris entre 0 et 9.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Calcule la somme des chiffres.

Indice 2 · Un pas de plus

a+12 doit être un multiple de 9 compris entre 12 et 21.

Voir l’explication

La somme des chiffres de $$7a5$$ vaut $$7+a+5=a+12$$ . Comme $0\le a\le9$ , cette somme est entre 12 et 21. Les multiples de 9 voisins sont 9,18,27 ; seul 18 est dans cet intervalle. Il faut donc $$a+12=18$$ , soit $$a=6$$ . Cette valeur est bien un chiffre. Le nombre est 765, et $765=9\times85$ confirme la divisibilité. L'intervalle a permis de prouver qu'aucun autre chiffre ne convient.

À toi d’essayer

Réduire deux bases

Calcule le reste de $2^{100}+3^{100}$ modulo 8.

Pour démarrer. Pour $2^{100}$ , extrais un facteur 8 ; pour $3^{100}$ , groupe les facteurs par deux.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Traite séparément les deux puissances.

Indice 2 · Un pas de plus

La première est divisible par 8 ; pour la seconde, utilise $3^2\equiv1$ .

Voir l’explication

Comme $100\ge3$ ,

\begin{aligned}2^{100} &= 2^3\times2^{97}\\[.35em] &= 8\times2^{97},\end{aligned}

donc son reste modulo 8 est 0. Pour l'autre terme, $3^2=9\equiv1\pmod8$ et $100=2\times50$ , donc

\begin{aligned}3^{100} &= (3^2)^{50}\equiv1^{50}\\[.35em] &= 1.\end{aligned}

La somme a donc reste $$0+1=1$$ . Le premier terme devient définitivement nul modulo 8 ; le second utilise un retour périodique au reste 1. On ne traite pas les deux bases avec un cycle supposé commun.

Exercices progressifs

Les exercices 1 à 5 consolident les bases, 6 à 10 relient les notions et 11 à 15 demandent davantage d'initiative. Cherche d'abord, puis utilise un indice si tu en as besoin.

Exercice 1 : Diviseurs signés ★☆☆

Liste les diviseurs entiers de 18. Justifie $-6\mid18$ et décide si $0\mid18$ .

Exercice 2 : Division positive ★☆☆

Donne la division euclidienne de 173 par 12.

Exercice 3 : Division négative ★☆☆

Divise euclidiennement $$-59$$ par 7.

Exercice 4 : Lire une congruence ★☆☆

Décide si $38\equiv3\pmod7$ , $-17\equiv3\pmod5$ et $21\equiv1\pmod6$ .

Exercice 5 : Réduction préalable ★☆☆

Calcule le reste de $52\times79+100$ modulo 9.

Exercice 6 : Un facteur constant ★★☆

Montre que tout diviseur commun à $$5n+2$$ et $$3n+1$$ divise 1.

Exercice 7 : Puissance modulo 7 ★★☆

Détermine le reste de $2^{100}$ modulo 7.

Exercice 8 : Dernier chiffre ★★☆

Détermine le dernier chiffre de $7^{2026}$ .

Exercice 9 : Tester un nombre ★★☆

Le nombre 123 456 est-il divisible par 3, 9, 4 et 11 ?

Exercice 10 : Inverse visible ★★☆

Résous $5x\equiv3\pmod7$ .

Exercice 11 : Une simplification fausse ★★★

Trouve toutes les solutions modulo 6 de $2x\equiv2\pmod6$ et explique pourquoi $x\equiv1\pmod6$ est incomplet.

Exercice 12 : Une impossibilité entière ★★★

Montre qu’aucun entier n ne vérifie $$n^2=2027$$ .

Exercice 13 : Divisibilité universelle ★★★

Démontre que $$n^3-n$$ est divisible par 6 pour tout $n\in\Z$ .

Exercice 14 : Un test pour 7 ★★★

Écris $$N=10a+b$$ , où b est le chiffre des unités. Montre que N est divisible par 7 si et seulement si $$a-2b$$ l’est. Applique à 203.

Exercice 15 : Lire un algorithme ★★★

Que renvoie puissance_mod(3, 5, 7) ? Justifie la fonction et explique le cas n=0.

Problème : Pour aller plus loin

Ce prolongement est accessible à partir du cours : les résultats supplémentaires sont guidés, et leur mémorisation n'est pas un préalable. Tu peux répartir la recherche sur plusieurs séances.

Construire et casser un chiffrement affine

On code les lettres A à Z par les entiers 0 à 25. Une lettre de code $$x$$ est transformée en la lettre de code $$y$$ , reste de $$5x+8$$ modulo 26. Espaces et accents sont retirés. Ce modèle sert à apprendre ; il ne prétend pas protéger un message réel. Durée indicative : 60 à 90 minutes.

Partie I : Chiffrer

Chiffre le mot MATHS en détaillant les cinq restes.
Montre que $5\times21\equiv1\pmod{26}$ .
Démontre que deux codes donnant la même image sont congrus modulo 26 ; explique pourquoi deux lettres différentes ne se confondent pas.

Partie II : Déchiffrer

À partir de $y\equiv5x+8$ , exprime $$x$$ modulo 26 en fonction de $$y$$ .
Déchiffre IZ et vérifie en rechiffrant.
Que se passe-t-il si l'on remplace le coefficient 5 par 2 ? Donne deux lettres différentes ayant la même image.

Partie III : Retrouver une clé

On sait qu'un chiffrement $y\equiv ax+b\pmod{26}$ envoie A sur I et B sur N.

Retrouve $$b$$ puis $$a$$ modulo 26.
Rédige deux fonctions Python de chiffrement et déchiffrement d'un code entier.
Explique pourquoi la connaissance de deux lettres consécutives et de leurs images suffit ici à retrouver la clé.

Pistes

M vaut 12, A vaut 0, T vaut 19, H vaut 7 et S vaut 18. Pour déchiffrer, soustrais 8 puis multiplie par 21. Pour la clé inconnue, A et B ont pour codes 0 et 1.

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Corrigé du problème

Partie I : Calculer les cinq images

1. Les codes de M,A,T,H,S sont 12,0,19,7,18. La transformation ajoute 8 après multiplication par 5, puis garde le reste entre 0 et 25 :

\begin{aligned}5\times12+8&=68=2\times26+16 &&\text{donne Q},\\[.35em]5\times0+8&=8=0\times26+8 &&\text{donne I},\\[.35em]5\times19+8&=103=3\times26+25 &&\text{donne Z},\\[.35em]5\times7+8&=43=1\times26+17 &&\text{donne R},\\[.35em]5\times18+8&=98=3\times26+20 &&\text{donne U}.\end{aligned}

Le mot chiffré est QIZRU. Chaque reste, et non le quotient, détermine la lettre.

2.

\begin{aligned}5\times21 &= 105\\[.35em] &= 4\times26+1,\end{aligned}

donc $5\times21\equiv1\pmod{26}$ . Le nombre 21 est un inverse de 5 modulo 26.

3. Supposons deux images égales. Alors $5x+8\equiv5x'+8$ . Soustraire 8 puis $$5x'$$ donne $5(x-x')\equiv0$ . Multiplier par 21 donne $x-x'\equiv0$ puisque $105\equiv1$ . Les codes $$x,x'$$ sont entre 0 et 25, donc leur différence est entre $$-25$$ et 25. Le seul multiple de 26 dans cet intervalle est zéro : $$x=x'$$ . Deux lettres distinctes ne peuvent donc pas se confondre.

Partie II : Remonter chaque opération

1. À partir de $y\equiv5x+8$ , soustrayons 8 : $y-8\equiv5x$ . Multiplions ensuite par 21 : $21(y-8)\equiv105x\equiv x$ . Le déchiffrement consiste donc à prendre le reste de $$21(y-8)$$ modulo 26. L'ordre compte : on retire d'abord le décalage, puis on annule la multiplication.

2. Pour I, $$y=8$$ , donc $$21(y-8)=0$$ et le code initial est 0, soit A. Pour Z, $$y=25$$ , donc

\begin{aligned}21(25-8) &= 21\times17\\[.35em] &= 357\\[.35em] &= 13\times26+19.\end{aligned}

Le code 19 est T. Ainsi IZ devient AT. Rechiffrons : A donne $5\times0+8=8$ , donc I ; T donne 103 de reste 25, donc Z. La vérification retrouve le message chiffré.

3. Avec le coefficient 2, le code 0 donne $2\times0+8=8$ ; le code 13 donne

\begin{aligned}2\times13+8 &= 34\\[.35em] &= 26+8.\end{aligned}

Les lettres A et N ont donc toutes deux pour image I. Une image ne permet plus de choisir un antécédent unique. Cette collision explique concrètement pourquoi on ne peut pas simplement diviser par 2 modulo 26.

Partie III : Retrouver puis programmer la clé

1. A a pour code 0 et I pour code 8. Donc $a\times0+b\equiv8$ , soit $b\equiv8$ . B a pour code 1 et N pour code 13 ; $a+b\equiv13$ . Soustraire la première congruence donne $a\equiv13-8=5$ . La clé est donc $$a=5,b=8$$ modulo 26.

2. Les fonctions prennent un code entier et renvoient un code entre 0 et 25 :

def chiffre(x):
    return (5*x + 8) % 26

def dechiffre(y):
    return (21*(y - 8)) % 26

L'opérateur % 26 impose le reste autorisé, même si $$y-8$$ est négatif. Les parenthèses de la seconde fonction assurent que la soustraction a lieu avant la multiplication. Pour tout code $$x$$ , la composition donne modulo 26 $21((5x+8)-8)=105x\equiv x$ . Comme le résultat et $$x$$ sont tous deux entre 0 et 25, ils sont égaux.

3. Pour deux codes consécutifs $$x$$ et $$x+1$$ , les images sont congrues à $$ax+b$$ et $$a(x+1)+b=ax+a+b$$ . Leur différence est donc congrue à $$a$$ . Une fois $$a$$ connu, $b\equiv y-ax$ le détermine aussi. Pour des codes non consécutifs, on obtiendrait un multiple de $$a$$ ; l'annuler demanderait un inverse qui pourrait ne pas exister. L'argument repose donc bien sur la différence égale à 1.

Faire le point par une variante autonome

Essaie cette variante sans relire le corrigé précédent. Explique le choix de ta méthode, puis utilise les contrôles pour décider quelle notion retravailler.

À toi d’essayer

Une puissance et une conclusion entière

Trouve le reste de $7^{2026}$ modulo 5, puis décide si $7^{2026}+1$ est divisible par 5.

Pour démarrer. Réduis la base modulo 5, puis démontre une puissance de retour à 1.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La base est congrue à 2.

Indice 2 · Un pas de plus

$2^4\equiv1\pmod5$ et $2026=4\times506+2$ .

Voir l’explication

Comme $$7=5+2$$ , $7^{2026}\equiv2^{2026}\pmod5$ . Or $2^4=16\equiv1\pmod5$ et $2026=4\times506+2$ . Donc

\begin{aligned}2^{2026} &= (2^4)^{506}2^2\equiv1^{506}\times4\\[.35em] &= 4.\end{aligned}

C'est le reste, car $0\le4<5$ . Ajouter 1 donne $7^{2026}+1\equiv0\pmod5$ , donc l'entier est divisible par 5. L'exposant a été partagé modulo 4 grâce au cycle, et non modulo 5 : la justification vient de $2^4\equiv1$ .

Fiche-mémoire

$a\mid b$ signifie $$b=ak$$ pour un entier $$k$$ .
Division euclidienne : $$a=bq+r$$ avec $$b>0$$ et $0\le r<b$ .
$a\equiv b\pmod n$ signifie $n\mid(a-b)$ , ou mêmes restes.
Addition, soustraction, produit et puissances positives conservent une congruence.
Une division exige une justification ; un inverse modulaire permet de simplifier.
Un test de divisibilité découle des puissances de 10 modulo le diviseur.

Autocontrôle. Mes quotients sont-ils entiers ? Le reste est-il dans le bon intervalle ? Ai-je conservé le module ? Ai-je prouvé la période des puissances ? Ai-je vérifié la réciproque d'une équivalence ?

Maîtrise du chapitre

Validation contrôlée

Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.

Avant le cours, vérifie tes bases

Pourquoi ce chapitre ?

Le problème fondamental : résoudre dans les entiers

L'idée avant la formule

Plusieurs entiers, un même reste

Un reste positif même en reculant

Détecter une impossibilité avant de chercher

Le cours formel

Divisibilité dans les entiers relatifs

Division euclidienne : existence et unicité

Congruences : oublier le quotient, garder le reste

Calculer avec les congruences

Puissances et raisonnements par restes

Démontrer les tests de divisibilité

Algorithmes et précautions de programmation

Boîte à outils : chercher le bon module

Une équation impossible modulo 3

Un chiffre inconnu dans une écriture décimale

Un cycle n'est pas toujours immédiatement inversible

Passer d'une congruence à tous les entiers

Exercices progressifs

Exercice 1 : Diviseurs signés ★☆☆

Exercice 2 : Division positive ★☆☆

Exercice 3 : Division négative ★☆☆

Exercice 4 : Lire une congruence ★☆☆

Exercice 5 : Réduction préalable ★☆☆

Exercice 6 : Un facteur constant ★★☆

Exercice 7 : Puissance modulo 7 ★★☆

Exercice 8 : Dernier chiffre ★★☆

Exercice 9 : Tester un nombre ★★☆

Exercice 10 : Inverse visible ★★☆

Exercice 11 : Une simplification fausse ★★★

Exercice 12 : Une impossibilité entière ★★★

Exercice 13 : Divisibilité universelle ★★★

Exercice 14 : Un test pour 7 ★★★

Exercice 15 : Lire un algorithme ★★★

Problème : Pour aller plus loin

Construire et casser un chiffrement affine

Partie I : Chiffrer

Partie II : Déchiffrer

Partie III : Retrouver une clé

Pistes

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Corrigé du problème

Partie I : Calculer les cinq images

Partie II : Remonter chaque opération

Partie III : Retrouver puis programmer la clé

Faire le point par une variante autonome

Fiche-mémoire

Maîtrise du chapitre

Pour relier les notions