Exercices sur les congruences

Sommaire

Démonstration des formules
Théorème de Bézout
Simplification et calcul avec des congruences
Résolution d’équations avec les congruences
Principe de récurrence et congruence
Reste d’une division euclidienne suivant les valeurs de n
Somme de carrés divisibles par 7
Somme de cubes divisibles par 9
Congruences module 13
Nombre palindrome divisible par 11
Codage et décodage avec des congruences
Par l’absurde modulo 10
Calculs dans dans Z/nZ

Pour accéder au cours sur les congruences, clique ici !

Démonstration des formules

Soit 4 réels a, b, a’ et b’ et un entier naturel non nul n tels que :

$a \equiv b \, [n]$
et
$a' \equiv b' \, [n]$

Montrer que l’on a alors :

$a + a' \equiv b + b' \, [n]$

$a - a' \equiv b - b' \, [n]$

$a \times a' \equiv b \times b' \, [n]$

$a^p \equiv b^p \, [n] \, \forall p \in \mathbb{N}$

Il s’agit tout simplement des démonstrations des formules vues dans le cours.

Bézout : trouver u et v avec l’algorithme d’Euclide

Haut de page

Trouver deux entiers u et v tels que 5873 u + 51 v = 1
Trouver deux entiers u et v tels que 9397 u + 49 v = 1

Simplification et calcul avec des congruences

Haut de page

Simplifier :

$x \equiv 32 \, [9]$

Trouver la valeur la plus simple remplaçant le point d’interrogation :

$x \equiv 3 \, [7] \Rightarrow x^5 \equiv ? \, [7]$

$x \equiv 4 \, [13] \Rightarrow x^5 \equiv ? \, [13]$

$x \equiv 4 \, [17] \Rightarrow x^{21} \equiv ? \, [17]$

Résolution d’équations avec les congruences

Haut de page

Nous allons résoudre les équations suivantes (le but est de trouver tous les x vérifiant l’équation) :

$3x \equiv 5 \, [4]$

$x^2 - 2x + 16 \equiv 0 \, [5]$

$7x \equiv 8 \, [9]$

Nous verrons deux méthodes différentes.

Principe de récurrence et congruence

Haut de page

Montrer que pour tout entier naturel n, 3^{2n + 1} + 2^{4n + 2} est divisible par 7.

Reste d’une division euclidienne suivant les valeurs de n

Haut de page

Quel est, suivant le valeur de n, le reste de la division euclidienne de 2ⁿ par 5 ?
Quel est le reste de la division euclidienne de 1357²⁰²⁰ par 5 ?

Somme de carrés divisibles par 7

Haut de page

Soit a et b deux entiers relatifs tels que :

$a^2 + b^2 \equiv 0 \, [7]$

Montrer que a et b sont divisibles par 7.

Somme de cubes divisibles par 9

Haut de page

Montrer que la somme de 3 cubes consécutifs est divisible par 9.

Congruences module 13

Haut de page

Montrer que 3¹²⁶ + 5¹²⁶ est divisible par 13

Nombre palindrome divisible par 11

Haut de page

Montrer qu’un nombre palindrome est divisible par 11 si son nombre de chiffres est pair.

On rappelle qu’un palindrome est un mot qui se lit de la même manière de gauche à droite et de droite à gauche, comme « kayak » par exemple.
Exemples de nombres palindromes : 15351 – 7997 – 27488472 etc…

Codage et décodage avec des congruences

Haut de page

Cet exercice est extrait du bac S 2016.
Pour coder et décoder un nombre, on associe à chaque lettre de l’alphabet un chiffre de la manière suivante :

Pour coder une lettre, on lui associe son chiffre que l’on note x.
On transforme x en un autre chiffre codé y de la manière suivante :
y est le reste dans la division euclidienne de 7x + 5 par 26.
1) Coder la lettre L (qui correspond à 11)
2) Montrer que :

$7x + 5 \equiv y \, [26] \Leftrightarrow x \equiv 15y + 3 \, [26]$