Séance 14-1 : Arithmétique dans Z (Cours)

Sommaire

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-1/ Divisibilité dans $\mathrm{\mathbb{Z}}$

1-2/ Division euclidienne dans $\mathrm{\mathbb{N}}$

1-3/ Division euclidienne dans $\mathrm{\mathbb{Z}}$

II- Nombres premiers

2-1/ Nombres premiers

2-2/ Détermination des nombres premiers

2-3/ Décomposition en produit de facteurs premiers

III- Plus grand commun diviseur - Plus petit commun multiple

3-1/ Plus grand commun diviseur

3-2/ Calcul pratique du P.G.C.D : L'algorithme d'Euclide

3-3/ Plus petit commun multiple

3-4/ Nombre de diviseurs d'un entier naturel non nul

IV- Congruence module $n$

4-1/ Congruences module $n$

4-2/ Propriétés de la relation « congruence modulo »

V- L’ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$

5-1/ Classes d'équivalence

5-2/ Opérations dans l'ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-1/ Divisibilité dans $\mathrm{\mathbb{Z}}$

Définition

Soit $a$ et $b$ deux entiers relatifs.

On dit que $a$ divise $b$, et on écrit $a/b$ s’il existe $k\in \mathrm{\mathbb{Z}}$ tel que $b=ak$.

Autrement dit : $a/b\iff \left[\left(\exists k\in \mathrm{\mathbb{Z}}\right): b=ka\right]$

On dit aussi que $b$ est divisible par $a$, ou que $b$ est un multiple de $a$, ou encore que $a$ est un diviseur de $b$.

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-1/ Divisibilité dans $\mathrm{\mathbb{Z}}$

Applications

Soit $a$ et $b$ deux entiers relatifs non nuls.

1. Montrer que : $b/a\iff \left|b\right|\le \left|a\right|$

Soit $x$ et $y$ deux éléments de $\mathrm{\mathbb{Z}}*$, et $n$ un entier naturel non nul.

2. a- Montrer l'équivalence suivante : $xy=1\iff \left(x=y=1 ou x=y=-1\right)$

2. b- Montrer que si $x$ divise $y$, alors : $x/y^n$ et $x^n/y^n$

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-1/ Divisibilité dans $\mathrm{\mathbb{Z}}$

Proposition

Soit $a$, $b$, $c$ et $d$ des éléments de $\mathrm{\mathbb{Z}}$.

Alors :

$$\begin{gathered} \boxed{1} a/a et a/-a et a/ab \\ \boxed{2} a/b\iff a/-b \\ \boxed{3} \left(a/b et b/c\right)\Rightarrow a/c \\ \boxed{4} \left(a/b et a/c\right)\Rightarrow \left(a/b+c et a/b-c\right) \\ \boxed{5} \left(a/b et b/a\right)\Rightarrow \left|a\right|=\left|b\right| \\ \boxed{6} \left(a/b et c/d\right)\Rightarrow ac/bd \\ \boxed{7} \left(\forall \left(\alpha ;\beta \right)\in {\mathrm{\mathbb{Z}}}^2\right): \left(a/b et a/c\right)\Rightarrow a/\alpha b+\beta c \end{gathered}$$

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-1/ Divisibilité dans $\mathrm{\mathbb{Z}}$

Applications

Soit $a$, $b$, $c$, $x$ et $y$ des éléments de $\mathrm{\mathbb{Z}}$ tels que $a/x-y$ et $a/b-c$.

1. Montrer que : $a/bx-cy$

Soit $d$ et $n$ deux entiers relatifs.

2. Établir l’implication : $\left\{\begin{array}{l}d/n^2+3\\ d/2n-1\end{array}\right.\Rightarrow d/13$

3. Déterminer toutes les valeurs de l’entier relatif $n$ pour lesquelles : $n-17/n-1$

Soit $\left(x;y\right)\in {\mathrm{\mathbb{Z}}}^2$ et $d$ un diviseur commun des entiers $x$ et $y$.

4. Déterminer les valeurs possibles de $d$ sachant que : $4x-13y=5$

5. Résoudre dans ${\mathrm{\mathbb{Z}}}^2$ l’équation suivante : $\left(x+1\right)\left(y+2\right)=2xy$

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-2/ Division euclidienne dans $\mathrm{\mathbb{N}}$

Théorème

Soit $a$ et $b$ deux entiers naturels tels que $a\ne 0$.

Il existe un unique couple $\left(q;r\right)\in {\mathrm{\mathbb{N}}}^2$ tel que $b=aq+r$ et $0\le r<a$.

L’opération qui permet la détermination du couple $\left(q;r\right)$ est appelée la division euclidienne de l’entier $b$ par l'entier $a$ dans $\mathrm{\mathbb{N}}$.

Les entiers $b$, $a$, $q$ et $r$ sont appelés respectivement le dividende, le diviseur, le quotient et le reste.

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-2/ Division euclidienne dans $\mathrm{\mathbb{Z}}$

Théorème

Soit $a$ et $b$ deux entiers naturels tels que $a\ne 0$.

Il existe un unique couple $\left(q;r\right)\in \mathrm{\mathbb{Z}}\times \mathrm{\mathbb{N}}$ tel que $b=aq+r$ et $0\le r<a$.

L’opération qui permet la détermination du couple $\left(q;r\right)$ est appelée la division euclidienne de l’entier $b$ par l'entier $a$ dans $\mathrm{\mathbb{Z}}$.

Les entiers $b$, $a$, $q$ et $r$ sont appelés respectivement le dividende, le diviseur, le quotient et le reste.

I- Divisibilité dans l'ensemble $\mathrm{\mathbb{Z}}$

1-2/ Division euclidienne dans $\mathrm{\mathbb{Z}}$

Applications

1. Déterminer le quotient et le reste de la division euclidienne de $b$ par $a$ dans chacun des cas suivants :

Les restes de la division euclidienne des nombres $4294$ et $3512$ par un entier naturel non nul $a$ sont respectivement $10$ et $12$.

2. Déterminer la valeur de $a$.

La division euclidienne de l'entier $1517$ par un entier naturel $x$ donne $75$ comme quotient et $r$ comme reste.

3. Déterminer les valeurs des nombres $x$ et $r$.

Soit $n\in \mathrm{\mathbb{N}}*$.

On désigne par $q$ et $r$ le quotient et le reste de la division euclidienne de $125$ par $n$ respectivement.

4. Déterminer les valeurs de $q$ et $r$ sachant que $r=q^2$.

II- Nombres premiers

2-1/ Nombres premiers

Définition

Soit $p\in \mathrm{\mathbb{Z}}$

On dit que $p$ est un nombre premier si $\left|p\right|\ne 1$ et $D_p=\left\{-1;1;-p-p\right\}$, où $D_p$ désigne l'ensemble des diviseurs de $p$.

Remarque

Si $p$ est premier dans $\mathrm{\mathbb{N}}$, alors $-p$ est premier dans $\mathrm{\mathbb{Z}}$.

Plus précisément :

($p$ est premier dans $\mathrm{\mathbb{Z}}$)$\iff Card{D}_p=4$ ; ($p$ est premier dans $\mathrm{\mathbb{N}}$)$\iff Card{D}_p=2$

C’est pour cette raison qu’on va se contenter dans la suite du ce chapitre du traitement des nombres positifs, et l’ensemble des nombres premiers positifs sera noté $\mathrm{\mathbb{P}}$.

On a donc l’équivalence : $x\in \mathrm{\mathbb{P}}\iff$($x\in \mathrm{\mathbb{N}}$ et $x$ premier)

II- Nombres premiers

2-1/ Nombres premiers

Applications

1. Montrer que les nombres suivants ne sont pas premiers :

$4825 - 7281 - 2501 - 111 - 111111 - 25008$

2. Montrer que tout nombre premier positif et distinct de $2$ et $3$ s’écrit sous la forme $6p+1$ ou $6p+5$.

Pour tout $n\in \mathrm{\mathbb{N}}$, on pose : $P\left(n\right)=10n+7$

3. Déterminer les valeurs de $n$ inférieur à $10$ et pour lesquelles $P\left(n\right)$ n’est pas un nombre premier.

II- Nombres premiers

2-2/ Détermination des nombres premiers

Proposition

Soit $a$ un nombre non premier et différent de $1$.

Le plus petit diviseur propre de a (c’est-à-dire distinct de $1$ et $a$) est un nombre premier.

II- Nombres premiers

2-2/ Détermination des nombres premiers

Théorème

Soit $n$ un entier non premier et supérieur ou égal à $2$.

Alors, il existe au moins un diviseur premier $p$ du nombre $n$ et vérifiant $p^2\le n$.

En d'autres termes :

($n$ est un nombre premier)$\iff$($n$ n’admet pas de diviseur premier dans $\left[2;\sqrt{n}\right]\cap \mathrm{\mathbb{N}}$)

II- Nombres premiers

2-2/ Détermination des nombres premiers

Applications

1. Parmi les nombres suivants, lesquels sont des nombres premiers :

$127 - 1979 - 2017 - 13957 - 3599 - 2309$

2. En utilisant le crible d’Eratosthène, déterminer les nombres premiers qui existent entre $100$ et $150$.

Pour tout $n\in \mathrm{\mathbb{N}}$, on pose : $M_n=\frac{3^n-1}{2}$

3. Montrer que si $M_n$ est premier, alors $n$ est un nombre premier.

II- Nombres premiers

2-2/ Détermination des nombres premiers

Théorème

L’ensemble $\mathrm{\mathbb{P}}$ des nombres premiers positifs est infini.

II- Nombres premiers

2-3/ Décomposition en produit de facteurs premiers

Théorème

Tout entier relatif $n$ distinct de $1$ et $-1$ peut s'écrire et de façon unique sous la forme $n=\epsilon {p_1}^{{\alpha }_1}{p_2}^{{\alpha }_2}....{p_k}^{{\alpha }_k}$ où $p_1,p_2,....p_k$ des nombres premiers positifs et distincts, ${\alpha }_1,{\alpha }_2,....{\alpha }_k$ des éléments de $\mathrm{\mathbb{N}}*$ et $\epsilon =\pm 1$.

Cette écriture est appelée la décomposition de $n$ en produit de facteurs premiers.

II- Nombres premiers

2-3/ Décomposition en produit de facteurs premiers

Applications

1. Décomposer les nombres suivants en produit de facteurs premiers :

$10000 ; 8200 ; 1332 ; 1777 ; -1032 ; 111333 ; -51480$

2. Décomposer en produit de facteurs premiers le nombre $a=6^6+1$.

3. Décomposer en produit de facteurs premiers le nombre $x={100}^{2n}$ où $n\in \mathrm{\mathbb{N}}*$.

II- Nombres premiers

2-3/ Décomposition en produit de facteurs premiers

Proposition

Soit $n$ un entier naturel supérieur ou égal à $2$ et tel que sa décomposition en produit de facteurs premiers est : $n={p_1}^{{\alpha }_1}{p_2}^{{\alpha }_2}....{p_k}^{{\alpha }_k}$

- Pour qu’un entier naturel $d$ soit un diviseur de $n$, il faut et il suffit que sa décomposition en produit de facteurs premiers s’écrit sous la forme $d={p_1}^{{\beta }_1}{p_2}^{{\beta }_2}....{p_k}^{{\beta }_k}$ avec $0\le {\beta }_i\le {\alpha }_i$ pour tout $i\in \left\{1;2;...;k\right\}$.

- Pour qu'un entier naturel $m$ soit un multiple de $n$, il faut et il suffit que sa décomposition en produit de facteurs premiers s’écrit sous la forme $m={p_1}^{{\gamma }_1}{p_2}^{{\gamma }_2}....{p_k}^{{\gamma }_k}\times a$ avec ${\alpha }_i\le {\gamma }_i$ pour tout $i\in \left\{1;2;...;k\right\}$ et $a$ est produit des facteurs premiers distincts de $p_1,p_2,....p_k$.

III- Plus grand commun diviseur - Plus petit commun multiple

3-1/ Plus grand commun diviseur

Définition

Soit $a$ et $b$ deux entiers relatifs non nuls.

Le plus grand commun diviseur de $a$ et $b$, noté $a\wedge b$ ou $PGCD\left(a,b\right)$ ou $\Delta \left(a,b\right)$, est le plus grand des diviseurs strictement positifs communs à $a$ et $b$.

Remarques

- On convient que pour tout $a\in \mathrm{\mathbb{Z}}$ : $a\wedge 0=\left|a\right|$

- La définition précédente peut être encore formulée par l'équivalence suivante :

$\delta =a\wedge b\iff \left\{\begin{array}{l}\delta /a et \delta /b\\ \left(\forall d\in D_a\cap D_b\right): d\le \delta \end{array}\right.$

- Soit $a$ et $b$ deux entiers relatifs non nuls.

Si $\delta =a\wedge b$ alors :

• $\delta \ge 1$ et $\delta /a$ et $\delta /b$.
• Pour tout $d\in \mathrm{\mathbb{Z}}*$ : $\left(d/a et d/b\right)\Rightarrow d/\delta$

III- Plus grand commun diviseur - Plus petit commun multiple

3-1/ Plus grand commun diviseur

Proposition

Soit $a$, $b$ et $c$ des entiers relatifs non nuls et $n$ un entier naturel non nul.

Alors :

$$\begin{gathered} \boxed{1} a\wedge b=\left|a\right|\wedge \left|b\right| \\ \boxed{2} a\wedge b=b\wedge a \\ \boxed{3} a\wedge a=a\wedge 0=\left|a\right| \\ \boxed{4} a\wedge 1=1 \\ \boxed{5} \left(a\wedge b\right)\wedge c=a\wedge \left(b\wedge c\right) \\ \boxed{6} a/b\iff a\wedge b=\left|a\right| \\ \boxed{7} a^n\wedge a=\left|a\right| \end{gathered}$$

III- Plus grand commun diviseur - Plus petit commun multiple

3-2/ Calcul pratique du P.G.C.D : L'algorithme d'Euclide

Proposition

Soit $a$ et $b$ deux entiers relatifs non nuls.

Si $a=bq+r$ et $0<r<b$, alors : $a\wedge b=b\wedge r$

En d'autres termes : Lorsque $b$ ne divise pas $a$, le plus grand commun diviseur des entiers $a$ et $b$ est égal au dernier reste non nul obtenu grâce à l’algorithme d'Euclide.

III- Plus grand commun diviseur - Plus petit commun multiple

3-2/ Calcul pratique du P.G.C.D : L'algorithme d'Euclide

Explication de l'algorithme d'Euclide

On considère deux entiers $a\in \mathrm{\mathbb{Z}}*$ et $b\in \mathrm{\mathbb{N}}*$.

- On effectue la division euclidienne de $a$ par $b$ : $a=b{q}_1+r_1$ avec $0\le r_1<b$

• Si $r_1=0$, on arrête l’algorithme en déduisant que $a\wedge b=b$.
• Si $r_1\ne 0$, on continue.

- On effectue la division euclidienne de $b$ par $r_1$ : $b=r_1{q}_2+r_2$ avec $0\le r_2<r_1$

• Si $r_2=0$, on arrête l’algorithme en déduisant que $a\wedge b=r_1$.
• Si $r_2\ne 0$, on continue.

- Etc.

Notons que le processus engagé va s’arrêter, car sinon, on construirait une suite d’entiers naturels strictement décroissante, ce qui est impossible.

Il existe donc un entier $p\in \mathrm{\mathbb{N}}$ tel que $r_p\ne 0$ et $r_{p+1}=0$.

Par conséquent : $a\wedge b=r_p$

III- Plus grand commun diviseur - Plus petit commun multiple

3-2/ Calcul pratique du P.G.C.D : L'algorithme d'Euclide

Applications

1. En utilisant l’algorithme d'Euclide, déterminer le plus grand commun diviseur des entiers relatifs a et b dans chacun des cas suivants :

$$\begin{gathered} \boxed{1} a=134 et b=25 \\ \boxed{2} a=336 et b=124 \\ \boxed{3} a=-74 et b=-24 \\ \boxed{4} a=21384 et b=613 \\ \boxed{5} a=-1074 et b=323 \end{gathered}$$

Soit $n$ un entier naturel supérieur ou égal à $2$.

2. En utilisant l’algorithme d’Euclide, montrer que :

$\left(n^3+3n^2+n+1\right)\wedge n^2=n^2\wedge \left(n+1\right)$

III- Plus grand commun diviseur - Plus petit commun multiple

3-2/ Calcul pratique du P.G.C.D : L'algorithme d'Euclide

Proposition

Soit $a$, $b$ et $c$ des entiers relatifs non nuls.

Alors :

$$\begin{gathered} \boxed{1} \left(c/a et c/b\right)\iff c/a\wedge b \\ \boxed{2} \left(ca\right)\wedge \left(cb\right)=\left|c\right|\left(a\wedge b\right) \\ \boxed{3} \left\{\begin{array}{l}c/a\\ c/b\end{array}\right.\Rightarrow \left(\frac{a}{c}\right)\wedge \left(\frac{b}{c}\right)=\frac{a\wedge b}{\left|c\right|} \end{gathered}$$

III- Plus grand commun diviseur - Plus petit commun multiple

3-2/ Calcul pratique du P.G.C.D : L'algorithme d'Euclide

Proposition

Soit $\left(a;b\right)\in {\left(\mathrm{\mathbb{N}}*\right)}^2$ tel que $a={p_1}^{{\alpha }_1}{p_2}^{{\alpha }_2}....{p_k}^{{\alpha }_k}$ et $b={p_1}^{{\beta }_1}{p_2}^{{\beta }_2}....{p_k}^{{\beta }_k}$ avec $p_1,p_2,....p_k$ des nombres premiers positifs et distincts et ${\beta }_i=0$ si $p_i$ n’apparaît pas dans la décomposition de $b$ et ${\alpha }_i=0$ si $p_i$ n’apparaît pas dans la décomposition de $a$.

Alors :

$a\wedge b={p_1}^{{\gamma }_1}{p_2}^{{\gamma }_2}....{p_k}^{{\gamma }_k}$ avec ${\gamma }_i=inf\left({\alpha }_i;{\beta }_i\right)$ pour tout $i\in \left\{1;2;...;k\right\}$

III- Plus grand commun diviseur - Plus petit commun multiple

3-3/ Plus petit commun multiple

Définition

Soit $a$ et $b$ deux entiers relatifs non nuls.

Le plus petit commun multiple de $a$ et $b$, noté $a\vee b$ ou $PPCM\left(a,b\right)$ ou $M\left(a,b\right)$, est le plus petit des multiples strictement positifs communs à $a$ et $b$.

Remarques

- On convient que pour tout $a\in \mathrm{\mathbb{Z}}$ : $a\vee 0=0$

- En notant $a\mathrm{\mathbb{Z}}$ l’ensemble des multiples de $a$, on a : $a\mathrm{\mathbb{Z}}=\left\{...;-3a;-2a;-a;0;a;2a;3a;...\right\}$

Le plus petit élément de l’ensemble $\left(a\mathrm{\mathbb{Z}}\cap b\mathrm{\mathbb{Z}}\right)\cap \mathrm{\mathbb{N}}*$ est donc $a\vee b$.

- Soit $a$ et $b$ deux entiers relatifs non nuls.

Si $m=a\vee b$, alors :

• $m\ge 1$ et $a/m$ et $b/m$.
• Pour tout $c\in \mathrm{\mathbb{Z}}$ : $\left(a/c et b/c\right)\Rightarrow m/c$

III- Plus grand commun diviseur - Plus petit commun multiple

3-3/ Plus petit commun multiple

Proposition

Soit $a$, $b$ et $c$ des entiers relatifs non nuls.

Alors :

$$\begin{gathered} \boxed{1} a\vee b=\left|a\right|\vee \left|b\right| \\ \boxed{2} a\vee b=b\vee a \\ \boxed{3} a\vee a=\left|a\right| \\ \boxed{4} a\vee 1=\left|a\right| \\ \boxed{5} \left(a\vee b\right)\vee c=a\vee \left(b\vee c\right) \\ \boxed{6} a/b\iff a\vee b=\left|b\right| \\ \boxed{7} a\vee b/ab \end{gathered}$$

III- Plus grand commun diviseur - Plus petit commun multiple

3-3/ Plus petit commun multiple

Proposition

Soit $\left(a;b\right)\in {\left(\mathrm{\mathbb{N}}*\right)}^2$ tel que $a={p_1}^{{\alpha }_1}{p_2}^{{\alpha }_2}....{p_k}^{{\alpha }_k}$ et $b={p_1}^{{\beta }_1}{p_2}^{{\beta }_2}....{p_k}^{{\beta }_k}$ avec $p_1,p_2,....p_k$ des nombres premiers positifs et distincts et ${\beta }_i=0$ si $p_i$ n’apparaît pas dans la décomposition de $b$ et ${\alpha }_i=0$ si $p_i$ n’apparaît pas dans la décomposition de $a$.

Alors :

$a\vee b={p_1}^{{\gamma }_1}{p_2}^{{\gamma }_2}....{p_k}^{{\gamma }_k}$ avec ${\gamma }_i=sup\left({\alpha }_i;{\beta }_i\right)$ pour tout $i\in \left\{1;2;...;k\right\}$

III- Plus grand commun diviseur - Plus petit commun multiple

3-3/ Plus petit commun multiple

Proposition

Soit $a$, $b$ et $c$ des entiers relatifs non nuls.

Alors :

$$\begin{gathered} \boxed{1} \left(ca\right)\vee \left(cb\right)=\left|c\right|\left(a\vee b\right) \\ \boxed{2} \left\{\begin{array}{l}c/a\\ c/b\end{array}\right.\Rightarrow \left(\frac{a}{c}\right)\vee \left(\frac{b}{c}\right)=\frac{a\vee b}{\left|c\right|} \\ \boxed{3} \left(a\wedge b\right).\left(a\vee b\right)=\left|ab\right| \end{gathered}$$

III- Plus grand commun diviseur - Plus petit commun multiple

3-3/ Plus petit commun multiple

Applications

1. Déterminer $a\vee b$ dans chacun des cas suivants :

$$\begin{gathered} \boxed{1} a\wedge b=13 et ab=221 \\ \boxed{2} a\wedge b=17 et ab=-578 \end{gathered}$$

Soit $\left(a;b;c;d\right)\in {\left(\mathrm{\mathbb{Z}}*\right)}^4$.

2. a- Établir les égalités suivantes : $\left(ab\right)\vee \left(ac\right)=\left(a\wedge c\right)\left(\left(ab\right)\vee c\right)$

2. b- Montrer que si $b\wedge c=a\wedge d=1$, alors : $\left(ab\right)\vee \left(cd\right)=\left(a\vee c\right)\left(b\vee d\right)$

Soit $a$ et $b$ deux éléments de $\mathrm{\mathbb{N}}*$.

3. Montrer que : $\left(\exists \left(a\text{'};b\text{'}\right)\in {\mathrm{\mathbb{N}}}^2\right): \frac{1}{a}+\frac{1}{b}=\frac{a\text{'}+b\text{'}}{a\vee b}$

III- Plus grand commun diviseur - Plus petit commun multiple

3-4/ Nombre de diviseurs d'un entier naturel non nul

Proposition

Soit $a={p_1}^{{\alpha }_1}{p_2}^{{\alpha }_2}....{p_k}^{{\alpha }_k}$ la décomposition d’un entier naturel non nul en produit de facteurs premiers.

Le nombre de diviseurs positifs de $a$ vaut : $\left(1+{\alpha }_1\right)\left(1+{\alpha }_2\right)...\left(1+{\alpha }_n\right)$

III- Plus grand commun diviseur - Plus petit commun multiple

3-4/ Nombre de diviseurs d'un entier naturel non nul

Applications

On considère le nombre $a=p^2{q}^3$ avec $p$ et $q$ deux nombres premiers distincts.

1. Déterminer le nombre de diviseurs de $a$ puis donner ces diviseurs.

2. Montre que :

($p$ est premier dans $\mathrm{\mathbb{N}}$)$\iff$(la somme des diviseurs de $p$ est $p+1$)

IV- Congruence module $n$

4-1/ Congruences module $n$

Définition

Soit $n$ un entier naturel non nul.

On dit que deux entiers relatifs $a$ et $b$ sont congrus modulo $n$ si $n$ divise $b-a$, c’est-à-dire s’il existe un entier $k\in \mathrm{\mathbb{Z}}$ tel que $b=a+kn$.

On écrit : $a\equiv b \left[n\right]$

IV- Congruence module $n$

4-1/ Congruences module $n$

Applications

1. Compléter chacune des égalités suivantes par un entier naturel convenable :

$5\equiv 0 \left[\_\_\right] ; 5\equiv -5 \left[\_\_\right] ; -7\equiv \_\_\_ \left[4\right] ; -1\equiv \_\_\_ \left[3\right]$

2. Déterminer la valeur de vérité de chacune des propositions suivantes $\left(n\in \mathrm{\mathbb{N}}*\right)$ :

$P : « 3\equiv -11 \left[7\right] » ; Q : « 193\equiv 193 \left[2018\right] » ; R : « 2n\equiv -3n \left[5\right] »$

3. Déterminer les valeurs de l’entier relatif $x$ vérifiant l’égalité suivante : $5x\equiv x \left[5\right]$

IV- Congruence module $n$

4-2/ Propriétés de la relation « congruence modulo »

Proposition

Soit $n$ un entier naturel non nul.

La relation « de congruence » est une relation d’équivalence sur $\mathrm{\mathbb{Z}}$, c’est-à-dire :

1) Elle est réflexive : $\left(\forall a\in \mathrm{\mathbb{Z}}\right) a\equiv a \left[n\right]$

2) Elle est symétrique : $\left(\forall \left(a;b\right)\in {\mathrm{\mathbb{Z}}}^2\right) \left(a\equiv b \left[n\right]\Rightarrow b\equiv a \left[n\right]\right)$

3) Elle est transitive : $\left(\forall \left(a;b;c\right)\in {\mathrm{\mathbb{Z}}}^3\right) \left(a\equiv b \left[n\right] et b\equiv c \left[n\right]\right)\Rightarrow a\equiv c \left[n\right]$

IV- Congruence module $n$

4-2/ Propriétés de la relation « congruence modulo »

Proposition

Soit $n$ un entier naturel non nul et $\left(a;b;c;d\right)\in {\mathrm{\mathbb{Z}}}^4$.

Alors :

1) $a\equiv b \left[n\right]\iff$(Les restes respectifs des divisions euclidiennes de $a$ et de $b$ par $n$ sont égaux).

2) Si $a\equiv b \left[n\right]$ et $c\equiv d \left[n\right]$, alors : $a+c\equiv b+d \left[n\right]$ et $ac\equiv bd \left[n\right]$

3) Si $a\equiv b \left[n\right]$ et $k\in \mathrm{\mathbb{Z}}$, alors : $ka\equiv kb \left[n\right]$

4) Si $a\equiv b \left[n\right]$ et $p\in \mathrm{\mathbb{N}}$, alors : $a^p\equiv b^p \left[n\right]$

IV- Congruence module $n$

4-2/ Propriétés de la relation « congruence modulo »

Applications

Soit $a$ et $b$ deux entiers relatifs tels que $17$ est le reste de la division euclidienne de $a$ par $19$, et $15$ est le reste de la division euclidienne de $b$ par $19$.

1. Déterminer le reste de la division euclidienne de chacun des nombres suivants par $19$ :

$a+b ; ab ; 2a-5b ; a^2{b}^3 ; a^2+b^2 ; 2a+3b$

2. Montrer que le reste de la division euclidienne du nombre $N={\left(2018\right)}^{102}$ par $5$ est égale à $4$.

3. Déterminer que le reste de la division euclidienne du nombre $2^{2018}$ par $7$.

4. a- Déterminer les restes de la division euclidienne par $7$ des nombres suivants :

$5 ; 5^2 ; 5^3 ; 5^4 ; 5^5 ; 5^6 ; 5^7$

4. b- En déduire, selon les valeurs de l’entier naturel $n$, le reste de la division euclidienne de $5^n$ par $7$.

5. Déterminer l’ensemble des entiers naturels $n$ pour lesquels $3$ divise le nombre ${45671}^n+{11569}^n$.

V- L’ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$

5-1/ Classes d'équivalence

Définition

Soit $n$ un élément de $\mathrm{\mathbb{N}}*$.

- L'ensemble des entiers relatifs qui ont le même reste $r$ de la division euclidienne par $n$ est appelé la classe d’équivalence de $r$, et on la note $\overline{r}$ .

C'est la classe d’équivalence de $r$ modulo $n$ dans $\mathrm{\mathbb{Z}}$.

- Généralisation : soit $a\in \mathrm{\mathbb{Z}}$ et $n\in \mathrm{\mathbb{N}}*$.

La classe d’équivalence de $a$ est l’ensemble défini par :

$\overline{a}=\left\{x\in \mathrm{\mathbb{Z}}/x\equiv a \left[n\right]\right\}=\left\{a+kn/k\in \mathrm{\mathbb{Z}}\right\}$

V- L’ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$

5-1/ Classes d'équivalence

Applications

1. Déterminer la classe d’équivalence modulo $12$ de chacun des nombres :

$116 ; 1979 ; 2018$

V- L’ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$

5-1/ Classes d'équivalence

Proposition

Soit $n$ un entier naturel non nul.

Pour tout $x\in \mathrm{\mathbb{Z}}$, on désigne par $\overline{x}$ la classe d'équivalence de $x$ modulo $n$.

Alors :

1) $\left(\forall a\in \mathrm{\mathbb{Z}}\right) \left(\exists !r\in \left\{0;1;...;n-1\right\}\right) \overline{a}=\overline{r}$

2) Si $0\le r<n$ et $0\le r\text{'}<n$, alors : $\overline{r}=\overline{r\text{'}}\iff r=r\text{'}$ et $r\ne r\text{'}\iff \overline{r}\cap \overline{r\text{'}}=\varnothing$.

3) $\left(\forall x\in \mathrm{\mathbb{Z}}\right) \left(\exists !r\in \left\{0;1;...;n-1\right\}\right) x=\overline{r}$ ($r$ étant le reste de la division euclidienne de $x$ par $n$)

4) $\mathrm{\mathbb{Z}}=\overline{0}\cup \overline{1}\cup \overline{2}\cup ....\cup \overline{n-1}$

5) Par définition $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}=\left\{\overline{0};\overline{1};\overline{2};....;\overline{n-1}\right\}$. On a : $Card\left(\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}\right)=n$

V- L’ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$

5-2/ Opérations dans l'ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$$\mathrm{}$

Définition

Soit $n$ un entier naturel non nul.

- On définit l’addition dans $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$ comme suit : Pour tous $\overline{x}$ et $\overline{y}$ de $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$ : $\overline{x}+\overline{y}=\overline{x+y}$

- On définit la multiplication dans $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$ comme suit : Pour tous $\overline{x}$ et $\overline{y}$ de $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$ : $\overline{x}\times \overline{y}=\overline{x\times y}$

V- L’ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$

5-2/ Opérations dans l'ensemble $\mathrm{\mathbb{Z}}/n\mathrm{\mathbb{Z}}$$\mathrm{}$

Applications

1. Montrer que pour tout $n\in \mathrm{\mathbb{N}}*$ :

$$\begin{gathered} \boxed{1} {\left(n+1\right)}^{2018}-1\equiv 0 \left[n\right] \\ \boxed{2} 4^{2n+2}\equiv 1 \left[15\right] \end{gathered}$$

2. Résoudre dans $\mathrm{\mathbb{Z}}/6\mathrm{\mathbb{Z}}$ les équations :