arithmétique - congruence dans Z Modulo [n]

Conseils

Congruences dans Z - Modulo [n]

Cours

Comprendre les congruences et modulo [$n$]

• Comprendre la définition

$\phantom{\Leftrightarrow}$ Dire que $a$ et $b$ sont congrus modulo $[n]$

$\Leftrightarrow$ $n$ divise $b-a$

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

$\Leftrightarrow$ $a$ et $b$ ont le même reste dans la division euclidienne par $n$

Notation

Faut-il dire "congru" ou "égal"

$a\equiv 0 ~[n]$

• Exemple

• Méthodes

Pour montrer qu'un entier $b$ divise $a$
cela revient à montrer que $a\equiv 0 ~[b]$
Concrètement on calcule $a$ modulo $b$ jusqu'à obtenir 0.
Pour 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 résultat 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 que quand on travaille modulo $[n]$, il n'y a que $n$ cas possibles

Et donc le nombre de cas est fini et donc on peut tous les essayer

Exemple Résoudre l'équation $3x\equiv 1~[4]$

Cours

Comment calculer avec les congruences, expliqué en vidéo

• Règles de calcul avec les congruences

Avec l'addition et la soustraction
- Dans une addition ou une soustraction, 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]$
  On dit que la relation de congruence est compatible avec l'addition (et la soustraction).
  
  Exemple $132+429\equiv ~? ~[5]$
  Comme $132\equiv 2~[5]$ et $429\equiv 4~[5]$ Donc $132+429\equiv 2+4\equiv 6\equiv 1~[5]$
- Dans une égalité modulo $[n]$, on peut additionner ou soustraire le même nombre des 2 côtés
  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]$
  
  $\phantom{\Leftrightarrow~}x-3\equiv 4 ~[5]$
  On additionne 3 de chaque côté.
  
  $\Leftrightarrow x-3{\color{red}+3}\equiv 4{\color{red}+3}~[5]$
  $\Leftrightarrow x\equiv 7~[5]$
  $\Leftrightarrow x\equiv 2~[5]$
Avec la multiplication
- 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]$
  On dit que la relation de congruence est compatible avec la multiplication.
  
  Exemple $132 \times 429\equiv ~? ~[5]$
  Comme $132\equiv 2~[5]$ et $429\equiv 4~[5]$ Donc $132 \times 429\equiv 2\times 4\equiv 8\equiv 3~[5]$
- Dans une égalité modulo [n], on peut multiplier des 2 côtés par un même nombre
  Si $a\equiv b~[n]$ alors $a\times k\equiv b\times k~[n]$ où $k$ est un entier relatif
  Attention, c'est une implication et pas une équivalence !
  
  Exemple Résoudre $4x\equiv 1 ~[6]$
  $\phantom{\Rightarrow~}4x\equiv 1 ~[6]$
  On multiplie par $3$ des deux côtés
  Attention c'est une implication pas une équivalence!
  
  $\Rightarrow 12x\equiv 3 ~[6]$
  $\Rightarrow 0\equiv 3 ~[6]$
  Donc cette équation n'a pas de solution modulo [6]
  Car 0 et 3 ne sont pas congrus modulo 6
- Pourquoi quand on multiplie, c'est une implication et pas une équivalence
  $a\equiv b~[n]$ implique $a\times k\equiv b\times k~[n]$
  Mais la réciproque est fausse:
  $a\times k\equiv b\times k~[n]$ n’entraîne pas en général $a\equiv b~[n]$. Cela reviendrait à diviser par $k$, ce qui est faux
  Exemple $2\times 4\equiv 2\times 9~[10]$ est vrai
  D'abord on remarque que $2\times 4\equiv 2\times 9~[10]$ est vrai car $8\equiv 18 ~[10]$
  Il est alors tentant de vouloir diviser par $2$. Si c'était possible, on obtiendrait $4\equiv 9~[10]$ ce qui est faux car $10$ ne divise pas $9-4$.
Avec la division
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 il ne faut pas diviser avec des congruences.
Exemple $2\times 4\equiv 2\times 9~[10]$
$2\times 4\equiv 2\times 9~[10]$ est vrai
car $8\equiv 18 ~[10]$

Il est alors tentant de vouloir diviser par $2$. Si c'était possible, on obtiendrait $4\equiv 9~[10]$ ce qui est faux car $10$ ne divise pas $9-4$. Donc retenez qu'en général, il ne faut pas diviser avec les congruences.
Avec les puissances
- 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^4\equiv ~? ~[5]$
  Comme $7\equiv 2~[5]$ donc $7^4\equiv 2^4\equiv 16\equiv 1~[5]$
- Erreur à ne pas faire avec les puissances et les congruences
  on ne peut pas remplacer le nombre en exposant par autre qui lui égal modulo $[n]$
  Exemple $2^4\not\equiv 2^1~[3]$ même si $4\equiv 1~[3]$
  Car $\left. \begin{array}{rr} 2^4\equiv 16\equiv 1~[3] \\ 2^1\equiv 2~[3] \end{array} \right\}$ donc $2^4\not\equiv 2^1~[3]$
$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.
Exemple $2\times 3\equiv 0~[6]$
$2\times 3\equiv 0~[6]$ est vrai
car $2\times 3=6$ et $6\equiv 0 ~[6]$

Et pourtant ni 2, ni 3 ne sont égaux à 0 modulo [6]!

Cours

Les questions qui tombent avec les congruences + les méthodes

Cours

Comprendre pourquoi les congruences permettent de faire des disjonctions de cas & à quoi ça sert en exercice

Cours

Congruence : erreur à ne pas faire lorsqu'on multiplie dans une égalité

Cours

Congruence : calculer avec des puissances - Connaître l'erreur à ne pas faire

Cours

Autres erreurs à ne pas faire avec les congruences

Cours

La preuve par neuf - Lien avec les congruences

Dérivation et Nombre dérivé : Exercices à Imprimer

Exercice 1: Congruence - Arithmétique - Savoir si des nombres sont congrus modulo [n] - maths expertes

Les propositions suivantes sont-elles vraies ou fausses?

a. $37\equiv 4 ~[3]$ b. $101\equiv 1 ~[5]$ c. $-16\equiv 0 ~[6]$ d. $-15\equiv 6 ~[7]$

Exercice 2: Congruences - Arithmétique - Démontrer qu'un nombre divise un autre - Maths expertes

Démontrer que pour tout entier naturel $n$:

$n(n^2+11)$ est divisible par $3$
$n(n+1)(2n+1)$ est divisible par $6$
$n^3+5n$ est divisible par $6$
$n^3-n$ est divisible par $2$ et par $3$

Exercice 3: Table de congruences - Arithmétique - Démontrer qu'un nombre divise un autre - Maths expertes

Démontrer que pour tout entier naturel $n$ impair, $n^2-1$ est divisible par $8$

Exercice 4: Table de congruences - Arithmétique - Démontrer qu'un nombre divise un autre - Maths expertes

Démontrer que pour tous entiers naturels $a$ et $b$, $ab(a^2-b^2)$ est divisible par $3$

Exercice 5: Table de congruences - Démontrer qu'un nombre divise un autre - Maths expertes

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

Exercice 6: Congruences - Arithmétique - Démontrer qu'un nombre est un multiple - Maths expertes

Démontrer de deux façons différentes que pour tout entier naturel $n$, $3^{2n}-1$ est un multiple de 8.

Exercice 7: Congruences - chiffre unités - Maths expertes

Vérifier que $7^4 \equiv 1 \, [10]$
Quel est le chiffre des unités (dans l'écriture décimale) de $7^{98}$ ?

Exercice 8: Congruences - chiffre unités - Maths expertes

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

Exercice 9: Congruences - Démontrer qu'un nombre divise un autre - Maths expertes

Démontrer que pour tout entier naturel $n$:

$4$ divise $9^n-1$
$3$ divise $5^n-2^n$
$3$ divise $2^n+2^{n+1}$
$2^{4n+1}+3^{4n+1}$ est divisible par $5$

Exercice 10: Congruences et puissance - maths expertes

Démontrer que $3^{43}\equiv 3~~[7]$

Exercice 11: Congruences - Démontrer qu'un nombre divise un autre - Maths expertes

$a$ et $b$ désignent deux entiers relatifs.
Démontrer que $3$ divise $(a+b)^3$ si et seulement si $3$ divise $a^3+b^3$.

Exercice 12: Congruences - Déterminer un reste - Maths expertes

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

Exercice 13: Congruences - Déterminer un reste - Maths expertes

$n$ désigne un entier naturel.
Déterminer suivant les valeurs de $n$, le reste de la division euclidienne de:

$2^n$ par $5$
$3^n$ par $7$
$5^n$ par $3$

Exercice 14: Congruences - Démontrer qu'un nombre divise un autre - Maths expertes

Démontrer que pour tout entier naturel $n$, $31^n+6n-1$ est divisible par $9$.

Exercice 15: Congruences - Déterminer un reste - Maths expertes

Pour quelles valeurs de l'entier naturel $n$, $3\times 4^n+2$ est-il divisible par 11?

Exercice 16: Congruences - erreurs classiques à ne pas faire - Maths expertes

Indiquer si les affirmations suivantes sont vraies ou fausses, en justifiant:

Si $a\times b\equiv 0 ~[6]$ alors $a\equiv 0 ~[6]$ ou $b \equiv 0 ~[6]$.
Si $2x\equiv 4 ~[12]$ alors $x\equiv 2 ~[12]$.
Si $2x\equiv 4 ~[12]$ alors $x\equiv 2 ~[6]$.
Si $7-x\equiv 5 ~[3]$ alors $x\equiv 2 ~[3]$.
Pour tout entier $x$, $x^5\equiv x ~[4]$.

Exercice 17: équation et congruence - Arithmétique - Maths expertes

Compléter la table des restes dans la congruence modulo $9$:

$x\equiv$	0	1	2	3	4	5	6	7	8
$4x\equiv$

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

Exercice 18: Congruences - Arithmétique - Démontrer qu'un nombre est divisible - Maths expertes

Montrer que la somme de trois cubes consécutifs (comme $1^3 + 2^3 + 3^3$) est toujours divisible par 9.

Exercice 19: $n^2$ pair alors $n$ pair - congruence - Arithmétique - Maths expertes

Soit $n$ un entier naturel. Démontrer à l'aide des congruences, que si $n^2$ est pair alors $n$ est pair.

Exercice 20: Comprendre les congruences - Arithmétique - Maths expertes

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

$x\equiv$ $[4]$	0	1	2	3
$3x\equiv$ $[4]$	0	3	2	1