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]$.



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 :
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