3

Congruences

DIFFÉRENCIATION

◉◉◉ Parcours 1 : exercices 61 ; 65 ; 79 ; 80 ; 99 et 108
◉◉◉ Parcours 2 : exercices 63 ; 67 ; 84 ; 89 ; 102  et 117
◉◉◉ Parcours 3 : exercices 66 ; 74 ; 90 ; 105 et 112

Sans calculatrice, compléter les égalités.

1. $54\equiv$$[7]$

2. $85\equiv$$[7]$

3. $139\equiv$$7]$

4. $25\equiv$$[11]$

5. $100\equiv$$[11]$

6. $2500\equiv$$[11]$

Dans chacun des cas, déterminer les restes dans la division euclidienne de $a$, $b$ et $c$ par $26$ sachant que $a\equiv 55[26]$ ; $b\equiv 110[26]$ et $c\equiv -39[26]$.

Sachant que $a\equiv 7[13]$ et $b\equiv 4[13]$, déterminer les restes dans la division euclidienne par $13$ de :

1. $a+b$


2. $ab$


3. $2b-3a$


4. $a^2+b^2$

On considère l’équation $(\mathrm{E}):2x+3\equiv 0[7]$

1. Trouver un entier naturel $x$ solution de cette équation.


2. Résoudre dans $\mathbb{N}$ l’équation $\text{(E)}$.

[ Raisonner. ]

[DÉMO]

Soit $m$ un entier naturel non nul.
Le but de l’exercice est de démontrer que, quels que soient les entiers $a$ et $b$, $a\equiv b[m]\iff m|(a-b)$.

1. On souhaite démontrer que $a\equiv b[m]\Rightarrow m|(a-b)$.
a. Sachant que $a\equiv b[m]$, écrire les divisions euclidiennes de $a$ et $b$ par $m$.

b. En déduire que $a-b$ est un multiple de $m$.


2. On souhaite démontrer que $m|(a-b)\Rightarrow a\equiv b[m]$.
a. Écrire la division euclidienne de $a$ par $m$. On notera $r$ le reste de cette division euclidienne.

b. Traduire la relation $m|(a-b)$.


c. En déduire que $a$ et $b$ ont le même reste dans la division euclidienne par $m$.

[ Raisonner. ]

[DÉMO]

Dans cet exercice, on note $m$ un entier naturel non nul et $a$, $b$, $c$ et $d$ quatre entiers relatifs.

1. Compatibilité de la relation de congruence avec l’addition
On suppose que $a\equiv b[m]$ et $c\equiv d[m]$.
Démontrer alors que $a+c\equiv b+d[m]$.

Aide

On pourra utiliser la propriété démontrée dans l’exercice

96

et la transitivité de la relation de divisibilité.

2. Compatibilité de la relation de congruence avec la multiplication
On suppose que $a\equiv b[m]$ et $c\equiv d[m]$.
Démontrer alors que $a\times c\equiv b\times d[m]$.


3. Compatibilité de la relation de congruence avec les puissances
On suppose que $a\equiv b[m]$.
Démontrer par récurrence que, pour tout $p\in {\mathbb{N}}^{\ast }$, $a^p\equiv b^p[m]$.


4. Application : Sachant que $a\equiv 5[7]$ et $b\equiv 3[7]$, déterminer le reste dans la division euclidienne par $7$ de $3a^2-b^2$.

[ Chercher. ]
Soient $a$ et $b$ deux entiers relatifs.
1. Développer $(a+b{)}^3$.



2. En déduire que $(a+b{)}^3$ est un multiple de $3$ si, et seulement si, $a^3+b^3$ est un multiple de $3$.



3. Trouver tous les entiers relatifs $x$ tels que $(x+2{)}^3$ soit un multiple de $3$ avec $-5⩽x⩽5$.

[ Calculer. ] ◉◉◉
1. Compléter les tables d’addition et de multiplication modulo $3$.



2. L’entier $2$ admet-il un inverse modulo $3$ ? Si oui, préciser quel est cet inverse.

[ Calculer. ]
1. Justifier que tout entier $n$ est congru modulo $7$ à $-3$ ; $-2$ ; $-1$ ; $0$ ; $1$ ; $2$ ou $3$.


2. En déduire les restes possibles de $n^2$ dans la division euclidienne par $7$.


3. Quels sont les restes possibles de $n^4$ dans la division euclidienne par $7$ ?

[ Raisonner. ]
Soit $n$ un entier naturel.

1. Démontrer par récurrence que
${\mathrm{S}}_n=0^2+1^2+2^2+3^2+\dots +n^2$$=\frac{n(n+1)(2n+1)}{6}$.


2. Quelle condition $n$ doit-il vérifier pour que $\text{S}$ soit pair ? Justifier.

[ Chercher. ] ◉◉◉
1. Montrer que $\text{A}=2305^{2019}+1106^{2019}$ est divisible par $9$.


2. Montrer que, pour tout $n\in \mathbb{N}$, $\mathrm{B}=5^n\times 12-12^n\times 5$ est divisible par $7$.

[ Chercher. ]
1. Déterminer, suivant les valeurs de l’entier naturel non nul $n$, le reste dans la division euclidienne de $3^n$ par $5$.


2. En déduire le reste de la division euclidienne de $243^{942}$ par $5$.

[ Chercher. ]
1. Quels sont les restes possibles de la division euclidienne de $5^n$ par $6$ ?


2. En déduire le reste de la division euclidienne de $15365^{221}$ par $6$.

[ Chercher. ] ◉◉◉
1. Quel est le chiffre des unités de $9^{231}$ ? Justifier.


2. Quel est le chiffre des unités de $4^{125}$ ? Justifier.

[ Calculer. ]
Résoudre dans $\mathbb{Z}$ les systèmes suivants.

1. $\{\begin{array}{l}x\equiv 2[7]\\ -3<x<10\end{array}$



2. $\{\begin{array}{l}x+2\equiv 4[5]\\ -3<x<10\end{array}$



3. $\{\begin{array}{l}x\equiv 6[4]\\ -4<x<12\end{array}$

[ Calculer. ]
L’objectif de l’exercice est de résoudre dans $\mathbb{Z}$ l’équation $3x\equiv 2[5]$.

1. Utiliser un tableau de congruence pour déterminer les restes possibles de $3x$ dans la division euclidienne par $5$.


2. En déduire les solutions de l’équation dans $\mathbb{Z}$.

[ Calculer. ] ◉◉◉
1. Résoudre dans $\mathbb{N}$ l’équation $6x\equiv 2[7]$.


2. Résoudre dans $\mathbb{Z}$ l’équation $7x\equiv 2[11]$.


3. Résoudre dans $\mathbb{N}$ l’équation $4x\equiv 0[10]$.


4. Résoudre dans $\mathbb{Z}$ l’équation $5x+2\equiv 13[5]$.

[ Calculer. ]
Soit $n$ est un entier naturel non nul. On pose :
${\mathrm{U}}_n=3^{n+3}-4^{4n+2}$. 1. Calculer ${\text{U}}_1$, ${\text{U}}_2$ et ${\text{U}}_3$.


2. En remarquant que $3\equiv -8[11]$, démontrer que $3^{n+3}\equiv (-1{)}^{n+1}\times 2^{3n+9}[11]$.


3. a. Démontrer que ${\text{U}}_n\equiv (-1{)}^{n+1}\times 2^{3n+9}-2^{8n+4}[11]$.


b. En déduire que ${\mathrm{U}}_n\equiv 2^{3n+9}\left((-1{)}^{n+1}-2^{5(n-1)}\right)[11]$.


4. Déterminer le reste de $2^5$ dans la division euclidienne par $11$. En déduire que $2^{5(n-1)}\equiv (-1{)}^{n-1}[11]$.


5. Déduire des questions précédentes que ${\text{U}}_n$ est divisible par $11$.

[ Raisonner. ]
Critère de divisibilité par $3$

1. Soit $\overline{abc}$ un entier naturel écrit en base $10$, c’est‑à‑dire $\overline{abc}=a\times 10^2+b\times 10+c$.
a. Démontrer que $\overline{abc}\equiv a+b+c[3]$.


b. Donner une condition nécessaire et suffisante de divisibilité par $3$ de $\overline{abc}$.


2. Généralisation : Soit $\text{A}$ un entier naturel.
On note $a_0$ ; … ; $a_n$ les entiers compris entre $0$ et $9$, $a_n\ne 0$, tels que $\mathrm{A}=\overline{a_n{a}_{n-1}{a}_{n-2}\dots a_1{a}_0}$ en base $10$.
a. Exprimer l’entier $\text{A}$ en fonction de $a_0$ ; … ; $a_n$ et des puissances de $10$.


b. Déterminer les restes possibles dans la division euclidienne de $10^n$ par $3$.


c. En déduire une condition nécessaire et suffisante de divisibilité par $3$.

[ Raisonner. ]
Critère de divisibilité par $9$
Démontrer qu’un entier est divisible par $9$ si, et seulement si, la somme de ses chiffres est divisible par $9$.

PYTHON

[ Représenter, Modéliser. ] ◉◉◉
1. Soit $x$ un entier relatif. Démontrer la proposition : « $x$ impair $\iff x^2\equiv 1[8]$. »


2. Résoudre dans ${\mathbb{Z}}^2$ l’équation $x^2=8y+1$.


3. En déduire l’ensemble des points à coordonnées entières de la parabole d’équation $y=\frac{1}{8}{x}^2-\frac{1}{8}$.


4. Le programme ci-dessous permet d’obtenir les coordonnées des points à coordonnées entières d’une fonction du second degré quelconque pour une abscisse comprise entre $1$ et $n$.

from math import *

def f(a, b, c, x):
  return a*x**2 + b*x + c

def coord_entieres(a, b, c, n):
  for i in range(0, n + 1):
    if f(a, b, c, i) == floor(f(a, b, c, i)):
      print([i, f(a,b,c,i)])

Comment modifier ce programme pour qu’il donne tous les points à coordonnées entières d’abscisses comprises entre $-n$ et $n$ ?

[ Communiquer. ]
Une association culturelle affecte à chacun de ses membres un numéro d’adhérent lors de son inscription. Ce numéro comporte 7 chiffres et s’écrit donc $c_0$ $c_1$ $c_2$ $c_3$ $c_4$ $c_5$ $c_6$. Le premier chiffre $c_o$ correspond à l’activité de l’adhérent :

• $1$ pour un adhérent suivant l’activité « Informatique » ;
• $2$ pour un adhérent suivant l’activité « Travaux artistiques » ;
• $3$ pour un adhérent suivant l’activité « Lecture ».

Les deux chiffres $c_1$ et $c_2$ du numéro d’adhérent correspondent à son année de naissance (par exemple, $91$ pour un adhérent né en 1991 et $02$ pour un adhérent né en 2002).
Les trois chiffres suivants sont donnés lors de l’adhésion à l’association.
Le dernier chiffre est appelé clé de contrôle. Il est calculé automatiquement de la manière suivante : on calcule la somme $s=c_0+c_1+2c_2+3\left(c_3+c_4+c_5\right)$ ; on effectue ensuite la division euclidienne de $s$ par $9$ ; le reste obtenu est la clé de contrôle.
1. a. Le numéro $1024578$ peut‑il être le numéro d’un adhérent ? Justifier.


b. Le numéro $2923517$ peut‑il être le numéro d’un adhérent ? Justifier.


2. Un adhérent né en 1982 et inscrit à l’activité « Travaux artistiques », se voit attribuer par l’association lors de son inscription le numéro $123$.
Déterminer la clé de contrôle.


3. Lors de la saisie d’un numéro d’adhérent, une erreur est commise sur le chiffre correspondant à l’activité de l’adhérent. Cette erreur peut‑elle être détectée par la clé de contrôle ?


4. Lors de la saisie de son numéro, un adhérent intervertit les chiffres de son année de naissance. Cette erreur peut‑elle être détectée par la clé de contrôle ?

VRAI / FAUX

[ Communiquer. ]
Les affirmations suivantes sont-elles vraies ou fausses ?
Justifier.

1. Si $n\equiv 3[7]$, alors $n^3+1$ est divisible par $7$.


2. Pour tout entier naturel $n$, $2^{2n}+1$ est divisible par $3$.


3. Si $x$ est solution de $x^2-x\equiv 0[5]$, alors $x\equiv 1[5]$.


4. Si un entier naturel $\text{A}$ a pour écriture décimale $\overline{abc}$ et un entier $\text{B}$ a pour écriture décimale $\overline{bac}$ , alors $\text{A}-\text{B}$ est divisible par $9$.

[ Raisonner. ]
Soient $n$ un entier naturel non nul, et les entiers ${\text{A}}_n=7^n+9^n$ et ${\mathrm{B}}_n=3^{2n}-2^n$.

1. Montrer que ${\text{A}}_n$ est divisible par $8$ pour tout entier naturel $n$ impair.


2. Montrer que ${\text{B}}_n$ n’est pas divisible par $2$.


3. Déterminer $x$ tel que, pour tout $n\in \mathbb{N}$, ${\mathrm{B}}_n\equiv x[7]$.

[ Raisonner. ]
On considère l’équation $(\mathrm{E}):$ $4x^2+3y^2=11$.

1. Montrer que si un couple d’entiers $(x;y)$ est solution de $\text{(E)}$, alors $4x^2\equiv 2[3]$.


2. En déduire que l’équation $\text{(E)}$ n’admet pas de solution entière.

[ Calculer. ] ◉◉◉
D’après bac S, Métropole, juin 2009
Les deux questions de cet exercice sont indépendantes.

1. a. Démontrer que, pour tout nombre entier naturel $k$, on a $2^{3k}\equiv 1[7]$.


b. Quel est le reste dans la division euclidienne de $2^{2009}$ par $7$  ?


2. Soient $a$ et $b$ deux nombres entiers naturels inférieurs ou égaux à $9$ avec $a\ne 0$.
On considère le nombre $\mathrm{N}=a\times 10^3+b$. On se propose de déterminer parmi ces nombres entiers naturels $\text{N}$ ceux qui sont divisibles par $7$.
a. Vérifier que $10^3\equiv -1[7]$.


b. En déduire tous les nombres entiers $\text{N}$ cherchés.

PYTHON

[ Raisonner, Modéliser. ]
Suite et congruence
On considère la suite $({\text{U}}_n)$ définie, pour tout entier naturel $n$, par ${\mathrm{U}}_n=2^n+2^{2n}+2^{3n}$.

1. Calculer ${\text{U}}_0$, ${\text{U}}_1$ et ${\text{U}}_2$.


2. Démontrer que, pour tout $n\in \mathbb{N}$, ${\mathrm{U}}_{n+3}\equiv {\mathrm{U}}_n[7]$.


3. En déduire les valeurs de $n$ pour lesquelles ${\text{U}}_n$ est divisible par $7$.


4. Recopier et compléter la fonction Python donnée ci-dessous afin qu’elle affiche les indices $i$ des termes de la suite vérifiant ${\mathrm{U}}_i\equiv 0[7]$.

from math import*
def indice(n):
	...
	for i in range(n+1):
		u = ...
		if u ... 7 == 0:
			l.append(...)
	return l