Rejoignez la communauté !
Co-construisez les ressources dont vous avez besoin et partagez votre expertise pédagogique.
Nombres complexes
Ch. 1
Nombres complexes, point de vue algébrique
Ch. 2
Nombres complexes, point de vue géométrique
Arithmétique
Ch. 3
Divisibilité dans Z
Ch. 4
PGCD et applications
Ch. 5
Nombres premiers
Graphes et matrices
Ch. 6
Calcul matriciel et applications aux graphes
Ch. 7
Suites et matrices
Annexes
Cahier d'algorithmique et de programmation
Chapitre 3
Cours 3
Congruences
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
A
Définition
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Définition
Soient m un entier naturel non nul, et a et b deux entiers relatifs.
On dit que a et b sont congrus modulo \boldsymbol{m} lorsqu'ils ont le même reste dans la division euclidienne par m.
On dit aussi que a est congru à \boldsymbol{b} modulo \boldsymbol{m}.
On dit que a et b sont congrus modulo \boldsymbol{m} lorsqu'ils ont le même reste dans la division euclidienne par m.
On dit aussi que a est congru à \boldsymbol{b} modulo \boldsymbol{m}.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Notation
On note a \equiv b[m] ; a \equiv b(m) ou a \equiv b \bmod m.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Exemple
15 = 2 \times 7 + 1 et 21 = 2 \times 10 + 1 donc 15 \equiv 21[2].
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Théorème
Soient m un entier naturel non nul et a et b deux entiers relatifs. a \equiv b[m] si, et seulement si, m |(a-b).
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Remarque
En particulier, si a \equiv 0[m], alors m\ |\ a.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Démonstration
Voir exercice p. 109.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
B
Congruences et opérations
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Propriété
Soient a, b et c trois entiers relatifs et m un entier naturel non nul.
Si a \equiv b[m] et b \equiv c[m], alors a \equiv c[m].
Si a \equiv b[m] et b \equiv c[m], alors a \equiv c[m].
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Remarque
On dit que la relation de congruence est transitive.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Démonstration
D'après les hypothèses, a et b ont le même reste dans la division euclidienne par m, et b et c ont le même reste dans la division euclidienne par m, donc a et c ont le même reste dans la division euclidienne par m donc a \equiv c[m].
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Exemple
251 \equiv 8[3] et 8 \equiv 2[3] donc 251 \equiv 2[3].
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Propriété
Soient a, b, c et d quatre entiers relatifs et m un entier naturel non nul.
1. Compatibilité avec l'addition
Si a \equiv b[m] et c \equiv d[m], alors a+c \equiv b+d[m].
2. Compatibilité avec la multiplication
Si a \equiv b[m] et c \equiv d[m], alors a \times c \equiv b\times d[m].
3. Compatibilité avec les puissances
Soit p un entier naturel non nul. Si a \equiv b[m], alors a^p \equiv b^p[m].
1. Compatibilité avec l'addition
Si a \equiv b[m] et c \equiv d[m], alors a+c \equiv b+d[m].
2. Compatibilité avec la multiplication
Si a \equiv b[m] et c \equiv d[m], alors a \times c \equiv b\times d[m].
3. Compatibilité avec les puissances
Soit p un entier naturel non nul. Si a \equiv b[m], alors a^p \equiv b^p[m].
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Cas particuliers
c \equiv c[m] donc, si a \equiv b[m], alors a+c \equiv b+c[m] et a \times c \equiv b \times c[m].
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Attention
Il n'y a pas de compatibilité avec la division : 62 \equiv 26[4] mais 31 et 13 ne sont pas congrus modulo 4.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Démonstration
Voir exercice p. 109.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Application et méthode - 5
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Énoncé
Montrer en utilisant un tableau de congruence que, pour tout entier relatif n, n(n + 1)(2n + 1) est divisible par 3.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Méthode
On recherche les restes possibles de n dans la division par 3 (conséquence de la division euclidienne).
On complète le tableau de congruence pour obtenir, dans la dernière ligne, les restes possibles de la division de n(n + 1)(2n + 1) par 3. Ces restes étant toujours nuls, on en déduit que, pour tout entier n, n(n + 1)(2n + 1) est divisible par 3.
On complète le tableau de congruence pour obtenir, dans la dernière ligne, les restes possibles de la division de n(n + 1)(2n + 1) par 3. Ces restes étant toujours nuls, on en déduit que, pour tout entier n, n(n + 1)(2n + 1) est divisible par 3.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Solution
On dresse un tableau de congruence de n modulo 3.
On remarque que, pour tout entier n, n(n+1)(2 n+1) \equiv 0[3], c'est‑à‑dire que n(n+1)(2 n+1) est divisible par 3.
| \boldsymbol{n \equiv … [3]} | 0 | 1 | 2 |
| \boldsymbol{(n+1) \equiv … [3]} | 1 | 2 | 3 \equiv 0 |
| \boldsymbol{(2n+1) \equiv … [3]} | 1 | 3 \equiv 0 | 5 \equiv 2 |
| Produit \boldsymbol{n(n+1)(2n+1)}\boldsymbol{\equiv … [3]} | 0 \times 1 \times 1 \equiv 0 | 1 \times 2 \times 0 \equiv 0 | 2 \times 0 \times 2 \equiv 0 |
On remarque que, pour tout entier n, n(n+1)(2 n+1) \equiv 0[3], c'est‑à‑dire que n(n+1)(2 n+1) est divisible par 3.
Pour s'entraîner
Exercices et .
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
C
Inverse modulo \boldsymbol{m}
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Définition
Soient a un entier relatif et m un entier naturel non nul.
On dit que a est inversible modulo \boldsymbol{m} lorsqu'il existe un entier b tel que a \times b \equiv 1 [m].
On dit que a est inversible modulo \boldsymbol{m} lorsqu'il existe un entier b tel que a \times b \equiv 1 [m].
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Exemple
8 est inversible modulo 3 car 8 \times 2 \equiv 1 [3]. 2 est donc un inverse de 8 modulo 3.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Application et méthode - 6
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Énoncé
1. Démontrer que 3 est inversible modulo 5.
2. Montrer que 4 n'admet pas d'inverse modulo 6.
2. Montrer que 4 n'admet pas d'inverse modulo 6.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Méthode
1. On recherche un entier b tel que 3b \equiv 1 [5].
Pour cela, on établit un tableau de congruence modulo 5, en recherchant les restes possibles de 3b modulo 5. Dans le tableau, on recherche s'il existe un entier b tel que 3b \equiv 1 [5]. Dans ce cas, on observe que l'entier 2 est une solution.
2. On établit un tableau de congruence modulo 6. On observe que 4c n'est jamais congru à 1 modulo 6.
Pour cela, on établit un tableau de congruence modulo 5, en recherchant les restes possibles de 3b modulo 5. Dans le tableau, on recherche s'il existe un entier b tel que 3b \equiv 1 [5]. Dans ce cas, on observe que l'entier 2 est une solution.
2. On établit un tableau de congruence modulo 6. On observe que 4c n'est jamais congru à 1 modulo 6.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Solution
1. Soit b un entier relatif. On établit un tableau de congruence modulo 5.
On a donc 3 \times 2 \equiv 1 [5] donc 2 est un inverse de 3 modulo 5.
Cet inverse n'est d'ailleurs pas unique : tout entier s'écrivant 5k + 2, avec k \in \mathbb{Z}, est un inverse de 3 modulo 5.
2. Soit c un entier relatif. On établit un tableau de congruence modulo 6.
Il n'existe pas d'entier c tel que 4c \equiv 1 [6] Donc 4 n'admet pas d'inverse modulo 6.
| \boldsymbol{b \equiv …[5]} | 0 | 1 | 2 | 3 | 4 |
| \boldsymbol{3b \equiv …[5]} | 0 | 3 | 1 | 4 | 2 |
On a donc 3 \times 2 \equiv 1 [5] donc 2 est un inverse de 3 modulo 5.
Cet inverse n'est d'ailleurs pas unique : tout entier s'écrivant 5k + 2, avec k \in \mathbb{Z}, est un inverse de 3 modulo 5.
2. Soit c un entier relatif. On établit un tableau de congruence modulo 6.
| \boldsymbol{c \equiv …[6]} | 0 | 1 | 2 | 3 | 4 | 5 |
| \boldsymbol{4c \equiv …[6]} | 0 | 4 | 2 | 0 | 4 | 2 |
Il n'existe pas d'entier c tel que 4c \equiv 1 [6] Donc 4 n'admet pas d'inverse modulo 6.
Pour s'entraîner
Exercices et p. 105.
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.
Oups, une coquille
j'ai une idée !
Nous préparons votre pageNous vous offrons 5 essais
YolèneÉmilieJean-PaulFatimaSarah