j'ai compris mes maths
J'ai compris.com
Cours et exercices corrigés en vidéo comme en classe
lycée
collège
primaire
Manuel scolaire

Web


Continuer sur

Continuer sur

Ce sera prêt pour 2018

Ce sera prêt pour 2017

Terminale S

Congruences dans $\mathbb{Z}$ - Spé Maths


Congruences: définition et propriétés

♦ Cours les congurences et modulo [$n$] en vidéo Cours de math en vidéo
  • $a$ et $b$ sont congrus modulo $[n]$ 
    Dire que $a$ et $b$ sont congrus modulo $[n]$  
    $n$ est un entier strictement positif
    $a$ et $b$ sont des entiers relatifs

    signifie que
    $n$ divise la différence entre $a$ et $b$
    $n$ divise la différence entre $a$ et $b$
    $\Updownarrow$
    $n$ divise $b-a$
    $\Updownarrow$
    $n$ divise $a-b$

    Exemple:
    8 et 14 sont égaux modulo 3
    car 3 divise 14-8
    ou encore car 3 divise 8-14

    Cela se note
    $8\equiv 14 [3]$

    $\Updownarrow$
    Pour passer de $a$ à $b$,
    on rajoute un certain nombre de fois $n$
    Exemple:
    5 et 19 sont congrus modulo [7]
    car 7 divise 19-5
    ou encore car pour passer de 5 à 19,
    il faut rajouter 14, un certain nombre de fois 7.

    $\Updownarrow$
    $b=a+k\cdot n$
    où $k$ est un entier relatif.

  • On dit aussi
    Au lieu de dire $a$ et $b$ sont congrus modulo [$n$]
    On peut dire également
    $a$ et $b$ sont égaux modulo [$n$]
    C'est ce qu'on utilisait déjà avec les angles:
    $\frac {\pi}3$ et $\frac{7\pi}{3}$ sont égaux modulo [$2\pi$] ou encore à $2\pi$ près.

  • Congru signifie
    Congru signifie "Qui coïncide"
  • Notation
    $a\equiv b ~[n]$
    est la notation pour dire que
    $a$ et $b$ sont congrus modulo $n$
  • $a\equiv 0~[n]$
    $a\equiv 0 ~[n]$
    $\Updownarrow$
    $a$ est divisible par $n$.
    On utilisera très souvent cette propriété
    pour démontrer qu'un nombre est divisible par un autre.

    Pour démontrer que $a$ est divisible par $n$,
    Penser à calculer $a$ modulo $[n]$.
    Penser à utiliser les règles de calcul avec les congruences
    Voir "Comment calculer avec des congruences"

    Si $a\equiv 0 ~[n]$ alors $a$ est divisible par $n$.
    Si $a\not\equiv 0 ~[n]$ alors $a$ est divisible par $n$.
  • $a\equiv b ~[n]$ et $b\equiv c ~[n]$
    Si $a\equiv b ~[n]$ et $b\equiv c ~[n]$
    alors
    $a\equiv c ~[n]$
    On dit que la relation de congruence est transitive.
  • Lien avec la division euclidienne
        $a\equiv b~[n]$
    $\Updownarrow$
    $a$ et $b$ ont le même reste dans la division euclidienne par $n$
    C'est une nouvelle façon
    de traduire $a\equiv ~b [n]$


    Exemple:
    23 et 31 sont congrus modulo [4] car
    Si on divise 23 par 4, on obtient $23=4\times 5+3$. Donc le reste est 3.
    Et si on divise 31 par 4, on obtient $31=4\times 7+3$. Donc le reste est 3.
    Comme on a le même reste, $23\equiv 31~[4]$
  • 3 façons de dire $a\equiv b~[n]$
    $a\equiv b~[n]$
    $\Updownarrow$
    $n$ divise $b-a$
    $\Updownarrow$
    $b=a+k\cdot n$ où $k$ est un entier relatif
    $\Updownarrow$
    $a$ et $b$ ont le même reste dans la division euclidienne par $n$
    Dans les exercices,
    il faudra choisir la plus pratique parmi les 3.

  • Dans les exercices
    Si on sait que $a\equiv b [n]$
    vous pouvez écrire:
    $n$ divise $b-a$
    $b=a+k\cdot n$ avec $k$ entier relatif
    $a$ et $b$ ont le même reste dans la division euclidienne par $n$
    Puis choisir la plus pratique
    pour traiter l'exercice.

  • Pour démontrer que $a\equiv b~[n]$
    4 méthodes
    Méthode 1: Montrer que $n$ divise $b-a$
    Méthode 2: Ecrire $b$ sous la forme $b=a+k\times n$ où $k$ est un entier relatif.
    Méthode 3: Vérifier que $a$ et $b$ ont le même reste dans la division euclidienne par $n$.
    Méthode 4: Calculer $a[n]$ en utilisant règles de calcul sur les congruences
    Voir ci-dessous
    Comment calculer avec des congruences
  • Pour montrer qu'un nombre est divisible par $b$
    Penser à calculer $a$ modulo $[b]$.
    si $a\equiv 0~[b]$ alors $a$ est divisible par $b$.
    si $a\not\equiv 0~[b]$alors $a$ n'est pas divisible par $b$.
    Pour calculer $a$ modulo $[b]$
    penser à utiliser
    les règles de calcul sur les congruences
    voir ci-dessous
    "Comment calculer avec des congruences"
  • Déterminer un reste
    Pour déterminer le reste dans la division euclidienne de $a$ par $b$
    1) Calculer $a$ modulo $[b]$
    Si $b$ est négatif,
    calculer modulo $|b|$


    2) Jusqu'à ce que le resultat obtenu soit positif et plus petit que $|b|$
    3) Ce résultat est alors le reste.
    Penser à utiliser les règles de calcul sur les congruences
    voir ci-dessous
    "Calculer avec des congruences"

  • disjonction de cas
    Un intérêt très important des congruences,
    c'est de se ramener à un nombre fini de cas.
    Quand on travaille modulo $[n]$,
    il n'y a que $n$ cas possibles
    Tout entier est égal modulo $[n]$:
    soit à 0, soit à 1, .... soit à $n-1$.



    Par exemple, modulo [3],
    il n'y a que 3 cas possibles: 0, 1 ou 2.

    Tout entier est égal modulo $[3]$
    soit à 0, soit à 1, soit à 2.

    Donc pour tout entier $n$ , on a:
    $n\equiv 0[3]$ ou $n\equiv 1[3]$ ou $n\equiv 2[3]$
    $\Updownarrow$
    $n=3k$ ou $n=3k+1$ ou $n=3k+2$ avec $k$ entier relatif.



    L'intérêt d'avoir un nombre cas finis,
    c'est que l'on peut tous les essayer!
    Pour celà, on dresse un tableau
    avec toutes les valeurs possibles.

    Exemple:
    Pour résoudre l'équation $3x\equiv 1~[4]$
    Comme on travaille modulo [4],
    il n'y a que 4 cas possibles:
    $x\equiv$    0     1     2    3  
    $3x\equiv$   0    3    2    1  
    Donc $3x\equiv 1~[4]$ n'a qu'une solution $x\equiv 3~[4]$





Calculer avec des congruences


  • Remplacer  
    Dans une addition, on peut remplacer un nombre par autre qui lui égal modulo $[n]$ 
    Autrement dit:
    Si $a\equiv b~[n]$ et $c\equiv d~[n]$ alors $a+c\equiv b+d~[n]$
    En remplaçant $a$ par $b$ et $c$ par $d$
    ça reste égal
    car $a\equiv b~[n]$ et $c\equiv d~[n]$


    Exemple:
    $132\equiv 2~[5]$ et $429\equiv 4~[5]$
    donc $132+428\equiv 2+4\equiv 6\equiv 1~[5]$
    On dit que la relation de congruence
    est compatible avec l'addition.


    Dans une multiplication, on peut remplacer un nombre par autre qui lui égal modulo $[n]$
    Autrement dit:
    Si $a\equiv b~[n]$ et $c\equiv d~[n]$ alors $a\times c\equiv b\times d~[n]$
    En remplaçant $a$ par $b$ et $c$ par $d$
    ça reste égal
    car $a\equiv b~[n]$ et $c\equiv d~[n]$


    Exemple:
    $132\equiv 2~[5]$ et $429\equiv 4~[5]$
    donc $132\times 428\equiv 2\times 4\equiv 8\equiv 3~[5]$
    On dit que la relation de congruence
    est compatible avec la multiplication.


    Avec des puissances, on peut remplacer le nombre dans la puissance par autre qui lui égal modulo $[n]$.
    Autrement dit:
    Si $a\equiv b~[n]$ alors $a^p \equiv b^p ~[n]$
    où $p$ est un entier strictement positif


    Exemple:
    $7\equiv 2~[5]$
    donc $7^4\equiv 2^4\equiv 16\equiv 1~[5]$

    réciproque fausse
    $a^p \equiv b^p ~[n]$ n'entraine pas $a\equiv b~[n]$

    Exemple:
    $5^2\equiv 7^2~[6]$
    car
    $5^2\equiv 25\equiv 1~[6]$
    $7^2\equiv 49\equiv 1~[6]$


    Pourtant $5\not\equiv 7~[6]$
    car
    7-5 n'est pas divisible par 6!


    Mais on ne peut pas remplacer le nombre en exposant par autre qui lui égal modulo $[n]$
    Exemple:
    $4\equiv 1~[3]$
    et pourtant
    $2^4\not\equiv 2^1~[3]$
    Car
    $2^4\equiv 16\equiv 1~[3]$
    $2^1\equiv 2~[3]$
    $1\not\equiv 2~[3]$
  • Additionner  
    On peut additionner le même nombre des 2 côtés dans une égalité modulo $[n]$
    Si $a\equiv b~[n]$ alors $a+k\equiv b+k~[n]$ où $k$ est un entier relatif.


    Exemple:
    Pour résoudre
    $x-3\equiv 4 ~[5]$
    On additionne 3 de chaque côtés

    $\Updownarrow$
    $x\equiv 4+3~[5]$
    $\Updownarrow$
    $x\equiv 7~[5]$
    $\Updownarrow$
    $x\equiv 2~[5]$
  • Soustraire  
    On peut soustraire le même nombre des 2 côtés dans une égalité modulo $[n]$
    Si $a\equiv b~[n]$ alors $a-k\equiv b-k~[n]$ où $k$ est un entier relatif.


    Exemple:
    Pour résoudre
    $x+3\equiv 7 ~[5]$
    On soustrait 3 de chaque côtés

    $\Updownarrow$
    $x\equiv 7-3~[5]$
    $\Updownarrow$
    $x\equiv 4~[5]$
  • Multiplier  
    On peut multiplier par le même nombre des 2 côtés dans une égalité
    Si $a\equiv b~[n]$ alors $a\times k\equiv b\times k~[n]$ où $k$ est un entier relatif.


    Exemple:
    $4x\equiv 1 ~[6]$
    On peut multiplier par 3 de chaque côtés
    Il n'y a pas équivalence!

    $\Downarrow$
    $12x\equiv 3 ~[6]$
    $\Downarrow$
    $0\equiv 3 ~[6]$
    Or 0 et 3 ne sont pas égaux modulo [6].
    Donc cétte équation $4x\equiv 1 ~[6]$ n'a pas de solution.


    Réciproque fausse
    $a\times b\equiv a\times c~[n]$
    n'entraine pas en général
    $b\equiv c~[n]$
    ça reviendrait à diviser par c
    ce qui est faux.
    Exemple:
    $2\times 4\equiv 2\times 9~[10]$
    n'entraine pas
    $4\equiv 9~[10]$
    Car c'est faux
    $4\not\equiv 9~[10]$
    Car 10 ne divise pas 9-4 !
  • Puissance  
    On peut élever à la même puissance des 2 côtés dans une égalité modulo $[n]$
    Si $a\equiv b~[n]$ alors $a^p\equiv b^p~[n]$ où $p$ est un entier strictement positif.


    Exemple:
    $7\equiv 2~[5]$
    donc $7^4\equiv 2^4\equiv 16\equiv 1~[5]$

    réciproque fausse
    $a^p \equiv b^p ~[n]$ n'entraine pas $a\equiv b~[n]$

    Exemple:
    $5^2\equiv 7^2~[6]$
    car
    $5^2\equiv 25\equiv 1~[6]$
    $7^2\equiv 49\equiv 1~[6]$


    Pourtant $5\not\equiv 7~[6]$
    car
    7-5 n'est pas divisible par 6!
  • Diviser  
    Lorsque
    $a\times b\equiv a\times c~[n]$
    Il est tentant diviser par $a$
    Et d'en déduire que
    $b\equiv c~[n]$
    Mais en général, c'est faux!
    Donc ne pas diviser avec des congruences.
    Exemple:
    $2\times 4\equiv 2\times 9~[10]$
    On peut pas diviser par 2
    et en déduire que
    $4\equiv 9~[10]$
    Car c'est faux
    $4\not\equiv 9~[10]$
    Car 10 ne divise pas 9-4 !
  • $a\times b\equiv 0~[n]$  
    Lorsque
    $a\times b\equiv 0~[n]$
    Il est tentant de penser que:
    $a\equiv 0~[n]$ ou $b\equiv 0 ~[n]$
    C'est à dire appliquer la règle du produit nul.
    Mais en général, c'est faux!
    Donc ne pas appliquer la règle du produit nul avec les congruences
    Par exemple:
    $2\times 3\equiv 6\equiv 0~[6]$
    Et pourtant ni 2, ni 3 ne sont égaux à 0 modulo [6]!



Corrigé en vidéo
Exercices 1:

Savoir calculer avec des congruences - Arithmétique - Spé Maths


1) Démontrer que $115 \equiv 27 \, [11]$ et que $-39 \equiv 27 \, [11]$
2) Trouver un entier naturel $n$ inférieur à $100$ qui vérifie : $\begin{cases} n \equiv 27 \, & [11] \\ n \equiv 4 \, & [7] \end{cases} $
3) Combien d'entiers naturels inférieurs à $1000$ sont congrus à $27$ modulo $11$?
Exercices 2:

Chiffre des unités avec les congruences - Arithmétique - Spé Maths


A l'aide des congruences, quel est le dernier chiffre dans l'écriture décimale de $3^{2017}$ ?

Corrigé en vidéo
Exercices 3:

Déterminer un reste à l'aide des congruences - Arithmétique - Spé Maths


Quel est le reste dans la division euclidienne de $451 \times 6^{43} - 912$ par $7$ ?

Corrigé en vidéo
Exercices 4:

Chiffre des unités à l'aide des congruences - Arithmétique - Spé Maths


1) Vérifier que $7^4 \equiv 1 \, [10]$.
2) Quel est le chiffre des unités (dans l'écriture décimale) de $7^{98}$ ?
Corrigé en vidéo
Exercices 5:

Congruences: erreurs classiques à ne pas faire - Arithmétique - Spé Maths


Indiquer si les affirmations suivantes sont vraies ou fausses, en justifiant:
1) Si $a\times b\equiv 0 ~[6]$ alors $a\equiv 0 ~[6]$ ou $b \equiv 0 ~[6]$.
2) Si $2x\equiv 4 ~[12]$ alors $x\equiv 2 ~[12]$.
3) Si $2x\equiv 4 ~[12]$ alors $x\equiv 2 ~[6]$.
4) Si $7-x\equiv 5 ~[3]$ alors $x\equiv 2 ~[3]$.
5) Pour tout entier $x$, $x^5\equiv x ~[4]$.
Corrigé en vidéo
Exercices 6:

Résoudre une équation avec des congruences - Arithmétique - Spé Maths


On considère l'équation $(E)$ : \[x^2 - 7y^2 = 3 \] où $x$ et $y$ sont deux entiers relatifs.
1) Justifier que si le couple d'entiers $(x~;~y)$ est solution alors $x^2 \equiv 3 \, [7]$.
2) Déterminer les restes possibles de la division de $x^2$ par $7$.
3) En déduire que l'équation $(E)$ n'a pas de solution.
Corrigé en vidéo
Exercices 7:

Montrer qu'un nombre est divisible par un autre avec les congruences


Démontrer que $2^{4n+1}+3^{4n+1}$ est divisible par $5$ quel que soit l'entier naturel $n$.

Corrigé en vidéo
Exercices 8:

Disjonction de cas et congruence - Arithmétique - Spé Maths


Démontrer en raisonnant par disjonction de cas que, pour tout entier naturel $n$, l'entier $n(n^2 + 5)$ est divisible par $3$.

Corrigé en vidéo
Exercices 9:

Critère de divisibilité par 3 et 9 - congruences - Arithmétique - Spé Maths


On considère un entier naturel $a$ défini par son écriture décimale $a = \overline{a_n a_{n-1}\cdots a_0}$ avec $a_n \neq 0$.
On a donc : \[a=a_n \times 10^n + a_{n-1} \times 10^{n-1} + \cdots + a_1 \times 10 + a_0 \]
1) Montrer que l'entier $a$ est divisible par $3$ si et seulement si la somme de ses chiffres est divisible par $3$.
2) Montrer de même que l'entier $a$ est divisible par $9$ si et seulement si la somme de ses chiffres est
divisible par $9$.
3) $983652145784512369566$ est-il divisible par $3$ ? Par $9$ ?
Exercices 10:

divisibilité et congruence - Arithmétique - Spé Maths


Déterminer les entiers naturels $n$ pour lesquels $n^2-2n$ est divisible par 7.

Corrigé en vidéo
Exercices 11:

équation et congruence - Arithmétique - Spé Maths


1) Compléter la table des restes dans la congruence modulo $9$:
$x\equiv$     0     1     2    3     4     5    6     7    8  
$4x\equiv$                                      

2) Résoudre alors l'équation $4x \equiv 5 \, [9] $
3) En remarquant que $4 \times 7 \equiv 1 \, [9]$, résoudre sans utiliser de table des restes l'équation : $$7x \equiv 8 \, [9] $$ 4) Résoudre enfin l'équation $3x \equiv 6 \, [9] $.
Corrigé en vidéo
Exercices 12:

compatibilité des congruences avec l'addition - démonstration du cours


Soient $a$, $b$, $c$, $d$ et $n$ cinq entiers avec $n$ non nul.
1) Montrer que si $a \equiv b \, [n]$ et $c \equiv d \, [n]$ alors $a + c \equiv b +d \, [n]$
2) En déduire que si $a \equiv b \, [n]$ alors $a + c \equiv b + c \, [n]$
3) La réciproque de la propriété précédente est-elle vraie ?
Corrigé en vidéo
Exercices 13:

compatibilité des congruences avec la multiplication - démonstration du cours


Soient $a$, $b$, $c$, $d$ et $n$ cinq entiers avec $n$ non nul.
1. Montrer que si $a \equiv b \, [n]$ et $c \equiv d \, [n]$ alors $a c \equiv b d \, [n]$
2. En déduire que si $a \equiv b \, [n]$ alors $a c \equiv b c \, [n]$
3. (a) Vérifier que $6 \times 5 \equiv 6 \times 7 \, [12]$
3. (b) La réciproque de la propriété précédente est-elle vraie ?
Corrigé en vidéo
Exercices 14:

compatibilité des congruences avec les puissances - démonstration du cours


Soient $a$, $b$ et $n$ trois entiers avec $n$ non nul.
1. Montrer par récurrence que pour tout entier naturel $p$ non nul, si $a \equiv b \, [n]$ alors $a ^p \equiv b^p\, [n]$.
2. Montrer que $41^{183} \equiv 6 \, [7]$.
3. (a) Vérifier que $2^3 \equiv 4^3 \, [7]$.
3. (b) Soit $p$ un entier naturel non nul, si $a ^p \equiv b^p\, [n]$, a-t-on $a \equiv b \, [n]$ ?
4. (a) A-t-on $2^2 \equiv 2^5 \, [3]$.
4. (b) Soit $p$ un entier non nul, si $a \equiv b \, [n]$, a-t-on $p ^a \equiv p^b\, [n]$ ?
Corrigé en vidéo
Exercices 15:

Chiffrement affine


Pour coder un message, on peut procéder de la façon suivante : chaque lettre du message munie de son numéro d'ordre $n$ (voir tableau ci-dessous) est remplacée par la lettre de l'alphabet munie du numéro d'ordre $p$ ($0 \leq p \leq 25$ ) obtenu à l'aide de la formule $p \equiv 3 n + 7 \, [26]$.
  A     B     C    D     E     F    G     H    I     J    K     L    M  
  0     1     2     3     4     5     6     7     8     9     10     11     12  
  N     O     P     Q     R     S     T     U     V     W     X     Y     Z  
  13     14     15     16     17     18     19     20     21     22     23     24     25  

1) Vérifier qu'avec ce chiffrement le S est remplacé par le J.
2) Coder le mot SECRET.
3) Montrer que si $p \equiv 3n + 7 \, [26]$ alors $n \equiv 9p +15 \, [26]$.
4) Déchiffrer le message suivant : KGHSX

congruences arithmétique Spé Maths : Exercices à Imprimer

Ce site vous a été utile? Ce site vous a été utile
alors dites-le !


Merci à vous.
Contact

N'hesitez pas à envoyer un mail à:
jaicompris.com@gmail.com

Liens
Qui sommes-nous? Nicolas Herla
Agrégé de Mathématiques
Professeur en S, ES et STI depuis 21 ans
Créateur de jeux de stratégie: Agora et Chifoumi

Stephane Chenevière
Agrégé de Mathématiques
Professeur en S, ES depuis 12 ans
Champion de France de magie en 2001: Magie