Sommaire

Introduction
Rappels sur la divisibilité
Rappels sur la division euclidienne
Notion de congruence
Propriétés des congruences
Astuces de calcul
Tableau des restes
Exercices

Introduction

Ce chapitre aborde les congruences, qui sont très pratiques pour résoudre certains problèmes.
La notion de congruence est étroitement liée à la divisibilité, ce pourquoi nous ferons des rappels sur la divisibilité et la division euclidienne avant de passer aux congruences.
L’application la plus courante en exercice sur les congruences est la cryptographie, nous verrons cela dans les exercices en vidéo.
Certains critères de divisibilité (par 7, par 13 etc…) sont également basés sur les congruences, nous ferons les démonstrations en vidéo également.

Rappels sur la divisibilité

Pour les critères de divisibilité usuels, tu es invité à aller voir le chapitre correspondant.

Dans tout le chapitre, nous ne considérerons que des entiers relatifs (donc positif ou négatif). Si parfois il est juste écrit entier, c’est sous-entendu entier relatif.
On prend donc deux entiers relatifs a et b.
Que signifie mathématiquement que a divise b ?

—
a divise b signifie qu’il existe un entier relatif k tel que b = ka
On dit aussi que :
a est un diviseur de b
b es un multiple de a
b est divisible par a
—

Par exemple, 4 divise 12 car 12 = 3 × 4 (ici k = 3).
-2 divise 8 car 8 = -4 × (-2) (ici k = -4)
28 est un multiple de 4 car 28 = 7 × 4 (ici k = 7)

Il existe deux propriétés pour la divisibilité qui vont se retrouver dans les congruences : la transitivité et les combinaisons linéaires.

Commençons par la transitivité : on considère maintenant 3 entiers relatifs a, b et c.
La transitivité nous dit que :

—
Si a divise b et si b divise c, alors a divise c.
—

La démonstration est très simple :
si a divise b, alors par définition il existe un entier k tel que b = ka.
Et comme b divise c, alors il existe un entier k’ tel que c = k’b.
On a donc c = k'(ka) = k’ka.
k’k est un entier, donc il existe bien un entier m = k’k tel que c = ma, donc a divise c.

L’autre propriété concerne les combinaisons linéaires.
Si on prend 2 entiers a et b, une combinaison linéaire de a et b est de la forme au + bv, avec u et v entiers relatifs.
Par exemple, si on prend 4 et 7, 4 × 3 + 7 × 9 est une combinaison linéaire de 4 et 7 (ici u = 3 et v = 9).

On considère un troisième entier c.
On a la propriété suivante :

—
Si c divise a et b, alors c divise toute combinaison linéaire de a et b.
—

La démonstration est là aussi très simple.
c divise a, donc il existe un entier k tel que a = kc
c divise b, donc il existe un entier k’ tel que b = k’c
Pour tout entier u et v : au + bv = kcu + k’cv = c(ku + k’c).
Or ku + k’c est un entier que l’on peut appeler p, d’où au + bv = pc : donc c divise au + bv.

Exemple d’application très classique :
Soit c un entier naturel divisant 2n + 1 et n. Montrons que c = 1.
On dit que c divise 2n + 1 et n donc toute combinaison linéaire de 2n + 1 et n et notamment :
1 × (2n + 1) – 2 × n = 1 (on a pris u = 1 et v = -2).
Donc c divise 1, donc c = 1 ou c = -1, mais comme c est un entier naturel, alors c = 1.
Très simple comme tu le vois

Passons maintenant aux rappels sur la division euclidienne.

Rappels sur la division euclidienne

Haut de page

On considère un entier naturel a et un entier naturel non nul b.
La division euclidienne de a par b est l’unique manière d’écrire a sous la forme a = bq + r, avec q et r entiers naturels, et 0 ≤ r < b (on peut aussi écrire 0 ≤ r ≤ b- 1 car r et b sont des entiers).
q est appelé le quotient et r le reste de la division euclidienne (d’où les notations r et q).

On peut aussi écrire :

Par exemple : la division euclidienne de 35 par 4 s’écrit 35 = 8 × 4 + 3
La condition 0 ≤ r < b est fondamentale, car on a aussi 35 = 6 × 4 + 11, mais le reste 11 n’est pas strictement inférieur à 4, donc il ne s’agit pas de la division euclidienne de 35 par 4.
De même, 35 = 10 × 4 – 5, mais -5 n’est pas supérieur ou égal à 0 donc il ne s’agit pas de la division euclidienne de 35 par 4.

Tu trouveras tous les détails sur la division euclidienne en cliquant ici.

Les rappels étant terminés, nous allons pouvoir passer aux congruences !

Notion de congruence

Haut de page

Pour comprendre les congruences, nous avons besoin d’un entier naturel non nul n, et de deux entiers relatifs a et b.

Si a – b est divisible par n, on dit que a et b sont congrus modulo n et on note a ≡ b [n].
On dit aussi que a est congru à b modulo n.

Exemple : 15 ≡ 7 [4] car 15 – 7 = 8, qui est divisible par 4.
32 ≡ 2 [3] car 32 – 2 = 30, qui est divisible par 3.
En revanche, 15 n’est pas congru à 3 module 5 car 15 – 3 = 12, qui n’est pas divisible par 5.

Maintenant que tu as compris le principe des congruences, nous allons voir les différentes propriétés sur les congruences que tu devras appliquer dans les exercices.

Propriétés sur les congruences

Haut de page

Dans tout ce qui suit, n est un entier naturel non nul, a et b sont des entiers relatifs.
Commençons par des propriétés assez évidentes :

Nous te laissons le soin de démontrer ces deux formules, c’est extrêmement simple !

Autre propriété évidente :

Autrement dit on peut inverser le a et le b.
En effet, si n divise a – b, alors n divise b – a.

Par ailleurs, si on fait la division euclidienne de a par b : a = bq + r.
On a alors :

En effet, a – r = bq, donc a – r est bien divisible par b.

Exemple : division euclidienne de 35 par 4 : 35 = 8 × 4 + 3, donc 35 ≡ 3 [4].

—
Attention cependant, ce n’est pas parce que a = p [b] que p est le reste dans la division euclidienne de a par b !!
C’est le cas uniquement si 0 ≤ r < b.
—

Autrement dit, la réciproque de la propriété précédente est fausse.
En effet, 35 ≡ 27 [4] car 35 – 27 = 8 divisible par 4, et pourtant 27 n’est pas le reste dans la division euclidienne de 35 par 4.

Ainsi, si on cherche le reste dans la division euclidienne de a par b, il faut trouver l’unique entier k compris entre 0 et n-1 tel que a ≡ k [n].
Nous reviendrons plus loin sur cette méthode.

Autre propriété : la transitivité.
Nous avions vu la transitivité pour la divisibilité, voici ce que cela donne pour les congruences.
On considère trois entiers relatifs a, b et c, et un entier naturel n non nul.
On a alors :

Là encore la démonstration est simple :
Si a ≡ b [n] et b ≡ c [n], alors n divise a – b et n divise b – c.
Donc n divise la combinaison linéaire (a – b) + (b – c) = a – c.
Ainsi n divise a – c donc a ≡ c [n]

Enfin, les propriétés les plus importantes et que l’on utilisera le plus souvent en exercice concernent les opérations que l’on peut faire sur les congruences : additionner, soustraire, multiplier et mettre à une certaine puissance.
On considère 4 entiers relatifs, a, a’, b et b’ et un entier naturel non nul n tels que :
a ≡ b [n] et a’ ≡ b’ [n]
Alors :

—
En revanche, il est STRICTEMENT INTERDIT de diviser des congruences !!!
Autrement dit, a/a’ n’est pas congru à b/b’ !!
—

Nous ferons les démonstrations de ces 4 formules en vidéo.
Elles sont fondamentales car elle seront utilisées dans presque tous les exercices.

On peut donner des conséquences immédiates des propriétés ci-dessus.
En effet, pour tout entier k, k ≡ k [n], donc en remplaçant a’ et b’ par k, on obtient :

Autrement dit, on peut ajouter soustraire ou multiplier par un entier k de part et d’autre comme pour une égalité.
En revanche, il est toujours strictement interdit de diviser de part et d’autre.

Par ailleurs, on suppose toujours a ≡ b [n]
On a n ≡ 0 [n], donc par somme :
a + 0 ≡ b + n [n] et a + 0 ≡ b – n [n]
Donc a ≡ b + n [n] et a ≡ b – n [n]

Et par récurrence immédiate, on a pour tout entier k :

Autrement dit, on peut ajouter ou soustraire autant de fois que l’on veut le modulo.

Ainsi, si on a par exemple :
a ≡ 40 [7], on peut dire a ≡ 33 [7], a ≡ 26 [7], a ≡ 19 [7], etc… (on enlève 7 à chaque fois).
On peut aussi dire a ≡ 47 [7], a ≡ 54 [7], etc… (on rajoute 7 à chaque fois).

Bien sûr on peut additionner ou soustraire plusieurs fois d’un coup le modulo.
Par exemple, si a ≡ 62 [5], on peut enlever 10 fois 5, donc 50, d’un seul coup, et dire a ≡ 12 [5] (car 62 – 50 = 12).

Une application très classique est pour trouver le reste dans une division euclidienne.
Supposons a ≡ -33 [7]. On cherche le reste dans la division euclidienne de a par 7.
Evidemment ce n’est pas -33 car le reste doit être compris entre 0 et 6 (puisque l’on fait la division par 7).
Or -33 + 7 × 5 = 2, donc a ≡ 2 [7].
On a bien 0 ≤ 2 ≤ 6, donc 2 est le reste dans la division euclidienne de a par 7.

Cela sera utilisé dans presque tous les exercices utilisant des congruences !

Voyons maintenant des techniques et astuces que tu devras souvent utiliser en exercices.

Astuces de calcul

Haut de page

1ère astuce : multiplier au fur et à mesure en simplifiant à chaque fois.
Exemple : on a a ≡ 34 [6]
On cherche à quoi est congru 22a modulo 6.
L’erreur à ne pas faire est de multiplier directement par 22, ce qui donnerait 22a ≡ 22 × 34 [6]
Mais 22 × 34 n’est pas simple à calculer…

La première étape consiste déjà à simplifier l’énoncé (petite astuce supplémentaire).
En effet, a ≡ 34 [6], mais 34 ≡ 4 [6], donc a ≡ 4 [6]
Là encore multiplier par 22 directement serait une erreur.
22 = 2 × 11, on va donc d’abord multiplier par 2, puis par 11 :
2a ≡ 2 × 4 [6]
2a ≡ 8 [6]
Or 8 ≡ 2 [6]
Donc 2a ≡ 2 [6]
On multiplie par 11 :
22a ≡ 22 [6]
22a ≡ 4 [6] (car 22 – 6 × 3 = 4)

Comme on le voit c’est beaucoup plus simple !

2ème astuce : aller dans les négatifs.
En effet, si a ≡ 10 [11], on peut dire a ≡ -1 [11] (car 10 ≡ -1 [11]).
Donc a⁶ ≡ (-1)⁶ [11]
D’où a⁶ ≡ 1 [11]

Si on avait gardé a ≡ 10 [11], on aurait eu a⁶ ≡ 10⁶ [11], et on n’aurait pas pu simplifier.

Autre exemple, on a a ≡ 6 [8], on cherche à quoi est congru a⁴ modulo 8.
On passe dans les négatifs : a ≡ -2 [8] car 6 ≡ -2 [8], d’où :
a⁴ ≡ (-2)⁴ [8]
a⁴ ≡ 16 [8]
D’où a⁴ ≡ 0 [8] car 16 ≡ 0 [8]

Comme on le voit c’est très pratique !

3ème astuce : trouver une puissance congrue à 1 ou -1
Cette astuce est également une méthode générale à savoir utiliser dans plusieurs cas, notamment pour calculer une puissance élevée.

Exemple : on veut savoir le reste dans la division euclidienne de 2¹⁴⁹⁵ par 15.
L’idée est de trouver le plus entier k ≥ 1 tel que 2^k ≡ 1 [15] ou 2^k ≡ -1 [15].
Remarque : on ne prend pas k = 0 car cela n’a aucun intérêt pour la suite du calcul, on verra plus bas pourquoi.
Pour trouver k, pas de méthode particulière il faut essayer k = 1, puis k = 2 etc… jusqu’à trouver (généralement les exercices sont faits de sorte à ce que k ne soit pas trop élevé).
2¹ ≡ 2 [15]
2² ≡ 4 [15]
2³ ≡ 8 [15]
2⁴ ≡ 16 [15]
or 16 ≡ 1 [15], donc 2⁴ ≡ 1 [15]
On prend donc k = 4.
Ensuite, on fait la division euclidienne de 1495 par 4 (la puissance considérée par k).
1495 = 4 × 373 + 3
Or on a 2⁴ : pour faire apparaître 2¹⁴⁹⁵ à partir de 2⁴, il faut donc mettre à la puissance 373 puis multiplier par 2³ :
2⁴ ≡ 1 [15]
(2⁴)³⁷³ ≡ 1³⁷³ [15]
2^{4 × 373} ≡ 1 [15]
2^{4 × 373} × 2³ ≡ 1 × 2³ [15]
2^{4 × 373 + 3} ≡ 8 [15]
2¹⁴⁹⁵ ≡ 8 [15]

Comme 0 ≤ 8 < 15, 8 est bien le reste dans la division euclidienne de 2¹⁴⁹⁵ par 15.

L’intérêt d’avoir trouvé 1, c’est que quand on le met à la puissance 373, cela reste 1 !

Voyons un exemple similaire avec -1 :
On veut savoir le reste dans la division euclidienne de 2⁷⁶⁷ par 9.
On cherche le plus entier k ≥ 1 tel que 2^k ≡ 1 [9] ou 2^k ≡ -1 [9].
2¹ ≡ 2 [9]
2² ≡ 4 [9]
2³ ≡ 8 [9]
or 8 ≡ -1 [9], donc 2³ ≡ -1 [9]
On prend donc k = 3.
Ensuite, on fait la division euclidienne de 767 par 3.
767 = 3 × 255 + 2.
2³ ≡ -1 [9]
(2³)²⁵⁵ ≡ (-1)²⁵⁵ [9]
2^{3 × 255} ≡ -1 [9]
2^{3 × 255} × 2² ≡ -1 × 2² [9]
2^{3 × 255 + 2} ≡ -4 [9]
Or -4 ≡ 5 [9] donc 2^{3 × 255 + 2} ≡ 5 [9]
Ainsi 2⁷⁶⁵ ≡ 5 [9]
0 ≤ 5 < 9 donc 5 est bien le reste dans la division euclidienne de 2⁷⁶⁷ par 9.

La petite différence quand on a -1 et non 1 c’est que quand on met à une puissance impaire (comme ici 255) on a -1 et non 1, mais cela ne change pas grand chose, il faut simplement à la fin penser à remettre le résultat en positif.

Remarque : comme on fait la division de la puissance par k, on ne prend pas k = 0 au début, car on ne divise par par 0 !

Toutes ces astuces permettront de résoudre de nombreux exercices, nous verrons les appliquerons dans les exercices en vidéo.

Tableau des restes

Haut de page

Une autre méthode très utilisée est le tableau des restes.
Elle est basée sur le fait que le reste dans la division euclidienne de a par n est compris entre 0 et n-1.
Ainsi, si on fait un tableau avec tous les entiers de 0 à n – 1, on obtient toutes les possibilités modulo n :

a

0

1

2

3

…

n-1

n

Ce tableau est modulo n (ce n’est pas marqué c’est sous-entendu).

Si on prend par exemple n = 5 :

a

0

1

2

3

4

En effet, si l’on prend 5, comme 5 ≡ 0 [5], cela revient à prendre 0.
Si l’on prend 6, comme 6 ≡ 1 [5], cela revient à prendre 1.
Si l’on prend 7, comme 7 ≡ 2 [5], cela revient à prendre 2.
Etc…
Autrement dit on obtient quelque chose de cyclique modulo 5.

Cherchons par exemple à quoi peut être congru a² modulo 5.
Pour cela, il suffit de rajouter une ligne avec a² et de mettre chaque terme au carré :

a	0	1	2	3	4
a2	0	1	4	9	16

Mais il ne faut pas oublier que ce tableau est modulo 5 !
Or 9 ≡ 4 [5] et 16 ≡ 1 [5], d’où :

a	0	1	2	3	4
a2	0	1	4	4	1

Ainsi, on voit que a² ne peut être congru qu’à 0, 1 ou 4 modulo 5.

C’est un moyen de montrer que a² ne peut pas être congru à 2 modulo 5 par exemple.

Cela permet également de résoudre des équations.
Imaginons que l’on cherche tous les entiers x tels que x² ≡ 4 [5]
On voit qu’alors il y a deux possibilités : x ≡ 2 [5] ou x ≡ 3 [5]
On vient de résoudre l’équation x² ≡ 4 [5] grâce au tableau !

On peut également combiner plusieurs lignes dans le tableau, par somme, addition ou soustraction.
Exemple : on cherche à quoi peut être congru a² + 3a modulo 5.

On commence par faire le tableau pour a² :

a	0	1	2	3	4
a2	0	1	4	4	1

On rajoute une ligne pour 3a :

a	0	1	2	3	4
a2	0	1	4	4	1
3a	0	3	6	9	12

On simplifie cette ligne modulo 5 :

a	0	1	2	3	4
a2	0	1	4	4	1
3a	0	3	1	4	2

Et on additionne la ligne de a² et la ligne de 3a (on a le droit d’additionner les congruences, c’est une des propriétés que l’on a vues !) :

a	0	1	2	3	4
a2	0	1	4	4	1
3a	0	3	1	4	2
a2 + 3a	0	4	5	8	3

On simplifie modulo 5 comme précédemment :

a	0	1	2	3	4
a2	0	1	4	4	1
3a	0	3	1	4	2
a2 + 3a	0	4	0	3	3

Ainsi, si on veut résoudre a² + 3a ≡ 4 [5], on voit que la solution est a ≡ 1 [5]

Il ne faut pas oublier de simplifier avec le modulo quand on utilise un tel tableau !

Nous verrons dans les exercices en vidéo plusieurs exercices utilisant ce tableau des restes.

Exercices

Haut de page

Tu trouveras sur cette page tous les exercices sur les congruences !

Retour au sommaireHaut de la page