Ressources · Terminale · Maths expertes (option Tle)

Congruences

Congruences modulo n et restes, compatibilité avec l’addition, la multiplication et les puissances, restes de grandes puissances, critères de divisibilité démontrés (rappels du collège, 11, 7 et 13), tableaux de congruences, équations ax ≡ b [n] et inverse modulo n.

À propos de cette page

Cinq problèmes corrigés sur les congruences : jours de la semaine d’un calendrier, clé de contrôle modulo 97 qui détecte les erreurs de saisie, chiffrement affine modulo 26, suite étudiée modulo 5 et 7, exponentiation rapide en Python.

5 problèmes, du plus simple au plus difficile. Écris tes réponses, puis « Vérifier ».

Résoudre un problème : la méthode

Je traduis l’énoncé en congruences : « divisible par n » donne ≡ 0 [n], « le jour de la semaine » un reste modulo 7, « la lettre codée » un reste modulo 26.
Je réduis les nombres modulo n avant tout calcul, et je cherche le cycle dès qu’une puissance apparaît.
Je calcule en citant la compatibilité à chaque étape et en écrivant le module.
Je démontre ce qui est demandé (récurrence, tableau de congruences, multiplication par un inverse) et je vérifie sur un exemple numérique.
Je réponds dans les termes de l’énoncé : un jour, une lettre, une clé, un chiffre, et non un reste brut.

Problème 1 · Un calendrier modulo 7★★★Facile

Le samedi 10 octobre 2026, une association lance un calendrier d’activités. Une année non bissextile compte

365

jours, une année bissextile

366

; l’année

2027

n’est pas bissextile, l’année

2028

l’est (le 29 février 2028 existe). On numérote les jours de la semaine : samedi

0

, dimanche

1

, lundi

2

, mardi

3

, mercredi

4

, jeudi

5

, vendredi

6

1. Reste de $365$ modulo $7$ :
$365 = 7 \times 52 + 1$ : une année non bissextile compte $52$ semaines et $1$ jour.
2. Jour de la semaine du 10 octobre 2027 :
Du 10 octobre 2026 au 10 octobre 2027, il s’écoule $365$ jours (pas de 29 février entre ces deux dates). Le numéro du jour augmente de $365 \equiv 1 [7]$ : samedi ( $0$ ) devient dimanche ( $1$ ).
3. Jour de la semaine du 10 octobre 2028 :
Du 10 octobre 2027 au 10 octobre 2028, il s’écoule $366$ jours, car le 29 février 2028 est entre les deux. $366 = 7 \times 52 + 2$ , donc $366 \equiv 2 [7]$ : dimanche ( $1$ ) devient le jour $1 + 2 = 3$ , un mardi.
4. Jour de la semaine $1 000$ jours après le samedi 10 octobre 2026 :
$1 000 = 7 \times 142 + 6$ , donc $1 000 \equiv 6 [7]$ : le jour $0$ devient le jour $6$ , un vendredi.
5. Une activité a lieu le 10 octobre 2026, puis tous les $10$ jours. Démontrer que la $k$ -ième activité suivante tombe un samedi si et seulement si $k$ est un multiple de $7$ . Nombre de jours écoulés jusqu’au premier samedi suivant où elle a lieu :
Rédaction attendue. La $k$ -ième activité suivante a lieu $10 k$ jours plus tard ; elle tombe un samedi si et seulement si $10 k \equiv 0 [7]$ , soit $3 k \equiv 0 [7]$ car $10 \equiv 3 [7]$ . L’inverse de $3$ modulo $7$ est $5$ ( $3 \times 5 = 15 \equiv 1 [7]$ ) ; en multipliant par $5$ , $k \equiv 0 [7]$ . Réciproquement, si $k = 7 j$ , $10 k = 70 j$ est un multiple de $7$ . La première fois, $k = 7$ , soit $70$ jours plus tard : le samedi 19 décembre 2026.

Problème 2 · Une clé de contrôle modulo 97★★★Moyen

Une mutuelle identifie ses adhérents par un numéro

N

de huit chiffres, suivi d’une clé

K = 97 - r

, où

r

est le reste de la division euclidienne de

N

par

97

: la clé est comprise entre

1

97

. À chaque saisie, le logiciel recalcule la clé et refuse le dossier si elle ne coïncide pas avec la clé annoncée.

1. Clé du numéro $N = 40 618 375$ : $K$ =
$97 \times 418 746 = 40 618 362$ et $40 618 375 - 40 618 362 = 13$ , avec $0 ⩽ 13 < 97$ : $r = 13$ et $K = 97 - 13 = 84$ .
2. Inverse de $10$ modulo $97$ , compris entre $1$ et $96$ :
On cherche un multiple de $10$ parmi $98$ , $195$ , $292$ , $389$ , $486$ , $583$ , $680$ … (les nombres $97 k + 1$ ) : $680 = 10 \times 68 = 7 \times 97 + 1$ . Donc $10 \times 68 \equiv 1 [97]$ : l’inverse de $10$ est $68$ .
3. Un opérateur se trompe sur un seul chiffre. Démontrer que l’erreur est toujours détectée. Pour $40 618 375$ saisi $40 618 875$ , clé recalculée :
Rédaction attendue. Si le chiffre de rang $k$ (celui de $10^{k}$ ) est remplacé, le numéro saisi $N'$ vérifie $N' - N = d \times 10^{k}$ avec $d$ entier et $1 ⩽ | d | ⩽ 9$ . Supposons $N' \equiv N [97]$ : alors $d \times 10^{k} \equiv 0 [97]$ . En multipliant $k$ fois par $68$ , inverse de $10$ , on obtient $d \equiv 0 [97]$ , impossible puisque $1 ⩽ | d | ⩽ 9$ . Donc $N' ≢ N [97]$ : les restes, donc les clés, diffèrent. Ici $N' - N = 500$ , et $13 + 500 = 513 = 5 \times 97 + 28$ : le nouveau reste vaut $28$ et la clé recalculée $97 - 28 = 69$ , différente de la clé correcte.
4. Un opérateur intervertit deux chiffres voisins distincts. Démontrer que l’erreur est détectée. Inverse de $9$ modulo $97$ , compris entre $1$ et $96$ :
Rédaction attendue. Notons $a$ le chiffre de rang $k + 1$ et $b$ celui de rang $k$ . Après l’échange, $N' - N$ $= (b - a) \times 10^{k + 1} + (a - b) \times 10^{k}$ $= 9 (b - a) \times 10^{k}$ . Or $9 \times 54 = 486 = 5 \times 97 + 1$ : l’inverse de $9$ modulo $97$ est $54$ . Si l’on avait $N' \equiv N [97]$ , on multiplierait $9 (b - a) \times 10^{k} \equiv 0 [97]$ par $54$ , puis $k$ fois par $68$ : $b - a \equiv 0 [97]$ , impossible car $1 ⩽ | b - a | ⩽ 9$ . L’interversion change donc la clé.
5. Un adhérent annonce le numéro $51 204 967$ et la clé $60$ . Clé attendue par le logiciel :
$97 \times 527 886 = 51 204 942$ et $51 204 967 - 51 204 942 = 25$ : $r = 25$ , et la clé attendue est $97 - 25 = 72$ . Elle diffère de $60$ : le dossier est refusé.
6. Avec le module $100$ au lieu de $97$ , une erreur sur le chiffre des centaines passerait inaperçue. Plus petit entier $k ⩾ 1$ tel que $10^{k} \equiv 0 [100]$ :
$10^{1} = 10 ≢ 0 [100]$ , mais $10^{2} = 100 \equiv 0 [100]$ , donc $10^{k} \equiv 0 [100]$ pour tout $k ⩾ 2$ . Modulo $100$ , seuls les deux derniers chiffres comptent : une erreur sur le chiffre des centaines, ou plus à gauche, ne change pas la clé. Avec $97$ , $10$ est inversible et toutes les positions sont contrôlées.

Problème 3 · Chiffrement affine★★★Moyen

Chaque lettre de l’alphabet est repérée par son rang

x

: A = 0, B = 1, …, Z = 25. On code la lettre de rang

x

par la lettre de rang

y

, où

y

est le reste de

9 x + 5

modulo

26

y \equiv 9 x + 5 [26]

0 ⩽ y ⩽ 25

. Rangs utiles : B = 1, C = 2, D = 3, E = 4, G = 6, J = 9, M = 12, O = 14, P = 15, R = 17, X = 23.

1. Lettre qui code M :
M a pour rang $12$ : $9 \times 12 + 5 = 113 = 4 \times 26 + 9$ , donc $y = 9$ : M est codée par J.
2. Inverse de $9$ modulo $26$ , compris entre $1$ et $25$ :
$27 = 26 + 1$ est un multiple de $9$ : $9 \times 3 = 27 \equiv 1 [26]$ .
3. Démontrer que le déchiffrement s’écrit $x \equiv u y + c [26]$ , où $u$ est l’inverse trouvé et $0 ⩽ c ⩽ 25$ . Valeur de $c$ :
Rédaction attendue. Si $y \equiv 9 x + 5 [26]$ , alors $y - 5 \equiv 9 x [26]$ ; en multipliant par $3$ : $3 y - 15 \equiv 27 x \equiv x [26]$ , car $27 \equiv 1 [26]$ . Comme $- 15 \equiv 11 [26]$ , on obtient $x \equiv 3 y + 11 [26]$ . Réciproquement, si $x \equiv 3 y + 11 [26]$ , alors $9 x + 5 \equiv 27 y + 104 [26]$ , et $27 y + 104 \equiv y [26]$ car $27 \equiv 1$ et $104 = 4 \times 26$ : chaque lettre codée provient d’une seule lettre claire.
4. Message clair correspondant au message codé « XBGP » :
Avec $x \equiv 3 y + 11 [26]$ . X ( $y = 23$ ) : $3 \times 23 + 11 = 80 = 3 \times 26 + 2$ , donc C. B ( $y = 1$ ) : $3 + 11 = 14$ , donc O. G ( $y = 6$ ) : $18 + 11 = 29 \equiv 3$ , donc D. P ( $y = 15$ ) : $45 + 11 = 56 = 2 \times 26 + 4$ , donc E. Le message est CODE.
5. Un élève propose le codage $y \equiv 13 x + 4 [26]$ . Expliquer pourquoi il est inutilisable. Nombre de lettres différentes qu’il produit :
Rédaction attendue. Si $x$ est pair, $x = 2 m$ et $13 x = 26 m \equiv 0 [26]$ ; si $x$ est impair, $x = 2 m + 1$ et $13 x = 26 m + 13 \equiv 13 [26]$ . Donc toute lettre de rang pair est codée par E (rang $4$ ) et toute lettre de rang impair par R (rang $17$ ) : deux lettres seulement, et un message codé ne peut pas être déchiffré. La raison : $13$ n’a pas d’inverse modulo $26$ , car $pgcd (13; 26) = 13 \neq 1$ .

Problème 4 · Une suite étudiée modulo 5 et modulo 7★★★Difficile

On considère la suite

(u_{n})

définie par

u_{0} = 7

et, pour tout entier naturel

n

u_{n + 1} = 5 u_{n} + 12

. Tous ses termes sont des entiers naturels.

1. Valeur de $u_{3}$ :
$u_{1} = 5 \times 7 + 12 = 47$ , puis $u_{2} = 5 \times 47 + 12 = 247$ et $u_{3} = 5 \times 247 + 12 = 1 247$ .
2. Démontrer que tous les termes de la suite ont le même reste modulo $5$ . Ce reste vaut
Rédaction attendue. $u_{0} = 7 = 5 + 2$ , donc $u_{0} \equiv 2 [5]$ . Pour tout entier naturel $n$ , $5 u_{n} \equiv 0 [5]$ et $12 \equiv 2 [5]$ , donc $u_{n + 1} = 5 u_{n} + 12 \equiv 2 [5]$ . Ainsi $u_{n} \equiv 2 [5]$ pour tout entier naturel $n$ : aucun terme n’est divisible par $5$ .
3. Démontrer par récurrence qu’il existe un entier $a$ tel que $u_{n} = a \times 5^{n} - 3$ pour tout entier naturel $n$ . Valeur de $a$ :
Rédaction attendue. Pour $n = 0$ , il faut $a - 3 = 7$ , d’où $a = 10$ . Soit $P (n)$ : « $u_{n} = 10 \times 5^{n} - 3$ ». Initialisation : $10 \times 5^{0} - 3 = 7 = u_{0}$ . Hérédité : si $u_{n} = 10 \times 5^{n} - 3$ pour un entier naturel $n$ , alors $u_{n + 1}$ $= 5 (10 \times 5^{n} - 3) + 12$ $= 10 \times 5^{n + 1} - 15 + 12$ $= 10 \times 5^{n + 1} - 3$ . Conclusion : $P (n)$ est vraie pour tout entier naturel $n$ .
4. Démontrer que $u_{n + 6} \equiv u_{n} [7]$ pour tout entier naturel $n$ . Reste de $u_{2027}$ modulo $7$ :
Rédaction attendue. Modulo $7$ , $10 \equiv 3$ , donc $u_{n} \equiv 3 \times 5^{n} - 3 [7]$ . Les restes des puissances de $5$ modulo $7$ valent $1$ , $5$ , $4$ , $6$ , $2$ , $3$ pour $n = 0$ à $5$ , puis $5^{6} \equiv 3 \times 5 = 15 \equiv 1 [7]$ . Donc $5^{n + 6} = 5^{6} \times 5^{n} \equiv 5^{n} [7]$ , et $u_{n + 6} \equiv u_{n} [7]$ :
$n$ modulo $6$ $0$ $1$ $2$ $3$ $4$ $5$
$5^{n}$ modulo $7$ $1$ $5$ $4$ $6$ $2$ $3$
$u_{n}$ modulo $7$ $0$ $5$ $2$ $1$ $3$ $6$
$2 027 = 6 \times 337 + 5$ , donc $u_{2027} \equiv u_{5} [7]$ , et le reste vaut $6$ .
5. Nombre d’entiers $n$ compris entre $0$ et $100$ tels que $u_{n}$ soit divisible par $7$ :
D’après le tableau, $u_{n} \equiv 0 [7]$ si et seulement si $n \equiv 0 [6]$ : $n = 0$ , $6$ , $12$ , …, $96$ (car $96 = 6 \times 16$ ), soit $17$ entiers.
6. Justifier sans le calculer que $u_{30}$ n’est pas divisible par $35$ . Reste de $u_{30}$ modulo $35$ :
Rédaction attendue. $30 \equiv 0 [6]$ , donc $u_{30} \equiv 0 [7]$ . Mais $u_{30} \equiv 2 [5]$ : $u_{30}$ n’est pas divisible par $5$ , donc pas par $35$ . Le reste $ρ$ de $u_{30}$ modulo $35$ vérifie $u_{30} \equiv ρ$ modulo $7$ et modulo $5$ , qui divisent $35$ : $ρ$ est un multiple de $7$ compris entre $0$ et $34$ ( $0$ , $7$ , $14$ , $21$ ou $28$ ) dont le reste modulo $5$ vaut $2$ . Seul $7$ convient.

$n$ modulo $6$	$0$	$1$	$2$	$3$	$4$	$5$
$5^{n}$ modulo $7$	$1$	$5$	$4$	$6$	$2$	$3$
$u_{n}$ modulo $7$	$0$	$5$	$2$	$1$	$3$	$6$

Problème 5 · L’exponentiation rapide en Python★★★Difficile

Pour calculer le reste de

a^{m}

modulo

p

sans former le nombre

a^{m}

, on utilise la fonction suivante, où a, m et p sont des entiers naturels avec

p ⩾ 2

def puissance_mod(a, m, p):
  r = 1
  a = a % p
  while m > 0:
    if m % 2 == 1:
      r = (r * a) % p
    a = (a * a) % p
    m = m // 2
  return r

1. Pour l’appel puissance_mod(3, 13, 7), nombre de passages dans la boucle while :
Valeurs des variables à chaque passage :
Passage $1$ $2$ $3$ $4$
m au début $13$ $6$ $3$ $1$
r à la fin $3$ $3$ $5$ $3$
a à la fin $2$ $4$ $2$ $4$
Après le quatrième passage, m vaut $0$ : la boucle s’exécute $4$ fois, une fois par chiffre de l’écriture binaire $1101$ de $13$ .
2. Démontrer qu’à chaque passage le produit $r \times a^{m}$ reste congru à $3^{13}$ modulo $7$ , puis donner la valeur renvoyée :
Rédaction attendue. Au départ, $r \times a^{m} = 1 \times 3^{13}$ . Pendant un passage, notons $r$ , $a$ , $m$ les valeurs au début. Si $m = 2 m'$ est pair, $r$ ne change pas, $a$ est remplacé par un entier congru à $a^{2}$ et $m$ par $m'$ : comme $a^{m} = (a^{2})^{m'}$ , le produit $r \times a^{m}$ est conservé modulo $7$ . Si $m = 2 m' + 1$ est impair, $r$ est remplacé par un entier congru à $r \times a$ et $a^{m} = a \times (a^{2})^{m'}$ : le produit est encore conservé (compatibilité avec le produit et les puissances). À la sortie, $m = 0$ , donc $r \equiv 3^{13} [7]$ avec $0 ⩽ r < 7$ . Comme $3^{6} \equiv 1 [7]$ et $13 = 6 \times 2 + 1$ , $3^{13} \equiv 3 [7]$ : la fonction renvoie $3$ .
3. Nombre de chiffres égaux à $1$ dans l’écriture de $560$ en base $2$ :
$560 = 512 + 32 + 16 = 2^{9} + 2^{5} + 2^{4}$ , donc $560$ s’écrit $1000110000$ en base $2$ : $10$ chiffres, dont $3$ égaux à $1$ .
4. Nombre total de multiplications effectuées par l’appel puissance_mod(a, 560, p) :
La boucle tourne $10$ fois, une fois par chiffre binaire de $560$ : $10$ élévations au carré, plus une multiplication de r pour chacun des $3$ chiffres égaux à $1$ , soit $13$ multiplications, contre $559$ pour le calcul naïf $a \times a \times \dots \times a$ .
5. Démontrer que $7^{4} \equiv 1 [100]$ , puis donner le nombre formé par les deux derniers chiffres de $7^{2027}$ , c’est-à-dire la valeur renvoyée par puissance_mod(7, 2027, 100) :
Rédaction attendue. $7^{2} = 49$ et $7^{4} = 49^{2} = 2 401 = 24 \times 100 + 1$ , donc $7^{4} \equiv 1 [100]$ . Comme $2 027 = 4 \times 506 + 3$ , $7^{2027} = (7^{4})^{506} \times 7^{3} \equiv 7^{3} = 343 \equiv 43 [100]$ : $7^{2027}$ se termine par $43$ .

Passage	$1$	$2$	$3$	$4$
`m` au début	$13$	$6$	$3$	$1$
`r` à la fin	$3$	$3$	$5$	$3$
`a` à la fin	$2$	$4$	$2$	$4$

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs