Médaille
N°1 pour apprendre & réviser du collège au lycée.
Divisibilité et congruences dans Z

Déjà plus de

1 million

d'inscrits !

Introduction :

Ce premier cours d’arithmétique concerne les congruences dans Z\mathbb{Z} : en partant de la notion de divisibilité dans Z\mathbb{Z} et en utilisant la division euclidienne – qui ont toutes les deux été vues au collège –, nous allons définir la notion de congruences dans Z\mathbb{Z} et en donner les principales propriétés. 

Dans un premier temps, nous allons revoir la notion de divisibilité dans Z\mathbb{Z} et la division euclidienne qui sera étendue aux nombres entiers relatifs. Nous verrons la notion de congruences dans Z\mathbb{Z}, qui est une nouveauté, et ses principales propriétés. 

Divisibilité dans Z\mathbb Z

Définitions

Commençons par quelques rappels simples, étendus à l’ensemble des entiers relatifs.

bannière definition

Définition

Divisibilité dans Z\mathbb Z :

Soit aa et bb des entiers relatifs, bb étant non nul. On dit que bb est un diviseur de aa, et on note bab\vert a, lorsqu’il existe un entier relatif kk tel que a=k×ba=k\times b.

  • On peut dire aussi que :
  • aa est divisible par bb ;
  • aa est un multiple de bb ;
  • bb divise aa.
bannière à retenir

À retenir

  • Les diviseurs de 11 ou 1-1 sont 1-1 et 11.
  • 11 et 1-1 sont des diviseurs de n’importe quel entier relatif.
  • 00 est multiple de n’importe quel entier relatif, et ne divise aucun entier relatif.
  • Les entiers relatifs pairs sont les multiples de 22, c’est-à-dire ceux qui s’écrivent sous la forme 2k2k avec kZk\in\mathbb Z.
  • Les entiers relatifs impairs sont les entiers qui ne sont pas multiples de 22, c’est-à-dire ceux qui s’écrivent sous la forme 2k+12k+1 avec kZk\in\mathbb Z.

Rappelons aussi les règles de divisibilité.

bannière à retenir

À retenir

  • Un entier relatif est divisible par 22 si et seulement si son chiffre des unités est 00, 22, 44, 66 ou 88.
  • Un entier relatif est divisible par 33 si et seulement si la somme de ses chiffres est divisible par 33.
  • Un entier relatif est divisible par 44 si et seulement si le nombre formé par son chiffre des dizaines et celui des unités est divisible par 44.
  • Un entier relatif est divisible par 55 si et seulement si son chiffre des unités est 00 ou 55.
  • Un entier relatif est divisible par 99 si et seulement si la somme de ses chiffres est divisible par 99.
  • Un entier relatif est divisible par 1010 si et seulement si son chiffre des unités est 00.

Propriétés

Revoyons maintenant les principales propriétés de la divisibilité dans l’ensemble Z\mathbb Z.

bannière propriete

Propriété

Transitivité :

Soit aa, bb et cc des entiers relatifs.
Si bb divise aa et si cc divise bb, alors cc divise aa.

bannière demonstration

Démonstration

Comme bb divise aa, il existe un entier relatif kk tel que a=bka=bk.
Comme cc divise bb, il existe un entier relatif kk^{\prime} tel que b=ckb=c k^{\prime}.

Ainsi, nous avons :

a=bk=(ck)k=c(kk)=cK (avec K=kk)\begin{aligned} a&=b k\ &=(ck^{\prime})k\ &=c(k^{\prime}k)\ &=cK \footnotesize{\textcolor{#A9A9A9}{\text{ (avec $K=kk^{\prime}$)}}} \end{aligned}

KK étant le produit deux entiers relatifs, c’est un entier relatif.

  • cc divise aa.
bannière propriete

Propriété

Combinaisons linéaires entières :

Soit aa, bb et cc des entiers relatifs.
Si cc divise aa et bb, alors pour tous les entiers relatifs nn et nn^{\prime}, cc divise na+nbna+n^{\prime} b.

bannière à retenir

À retenir

Autrement dit, si cc divise aa et bb, alors il divise toutes les combinaisons linéaires entières de aa et bb.

bannière demonstration

Démonstration

Comme cc divise aa et bb, il existe deux entiers relatifs kk et kk^{\prime} tels que a=kca=k c et b=kcb=k^{\prime} c.

Alors, avec nn et nn^{\prime} deux entiers relatifs :

na+nb=n(kc)+n(kc)=(nk+nk)c=Kc (avec K=nk+nk)\begin{aligned} na+n^{\prime}b&= n(kc)+n^{\prime}(k^{\prime}c) \ &=(nk+n^{\prime}k^{\prime})c \ &=Kc \footnotesize{\textcolor{#A9A9A9}{\text{ (avec $K= nk+n^{\prime}k^{\prime}$)}}} \end{aligned}

KK étant la somme de deux produits d’entiers relatifs, c’est un entier relatif.

  • Ainsi, cc divise na+nbn a+n^{\prime} b.

Division euclidienne

Après avoir revu la notion de divisibilité dans Z\mathbb Z, revoyons la division euclidienne, que nous allons étendre aux nombres entiers relatifs.

Définitions

bannière definition

Définition

Division euclidienne :

Soit aa et bb deux entiers naturels avec bb non nul.
Il existe un unique couple (q,r)(q,\,r) d’entiers naturels tels que :

a=bq+r et 0r<ba=bq+r \text{ et } 0\leq r < b

  • L’entier naturel aa est le dividende et bb est le diviseur.
  • L’entier naturel qq s’appelle le quotient et rr s’appelle le reste de la division euclidienne de aa par bb.
bannière exemple

Exemple

  • La division euclidienne de 343343 par 1212 donne :

343=12×28+7 (avec 07<12)343=12\times 28+7 \footnotesize{\textcolor{#A9A9A9}{\text{ (avec $0\leq 7 < 12$)}}}

  • La division euclidienne de 15261\,526 par 1111 donne :

1526=11×138+8 (avec 08<11)1\,526=11\times 138+8 \footnotesize{\textcolor{#A9A9A9}{\text{ (avec $0\leq 8 < 11$)}}}

Nous pouvons étendre la division euclidienne sur les entiers naturels à celle d’un entier relatif par un entier naturel non nul.

bannière propriete

Propriété

Soit aa un entier relatif et b0b\neq 0 un entier naturel.
Il existe un unique couple (q,r)(q, r), avec qZq\in \mathbb Z et rNr\in \mathbb N, tels que :

a=bq+r et 0r<ba=bq+r \text{ et } 0\leq r < b

Une différence entre la division euclidienne d’un élément de Z\mathbb Z et la division euclidienne d’un élément de N\mathbb N est que le quotient peut être négatif.

bannière exemple

Exemple

  • La division euclidienne de 431-431 par 1717 donne :

431=17b×(26)q<0+11r (avec 011<17)-431=\underbrace{17}b\times \underbrace{(-26)}{q<0}+\underbrace{11}_r \footnotesize{\textcolor{#A9A9A9}{\text{ (avec $0\leq 11 < 17$)}}}

  • La division euclidienne de 121-121 par 99 :

121=9×(14)+5 (avec 05<9)-121=9\times (-14) +5 \footnotesize{\textcolor{#A9A9A9}{\text{ (avec $0\leq 5 < 9$)}}}

Une application dans la vie quotidienne

On se sert par exemple de la division euclidienne lorsque qu’on nous attribue notre numéro de Sécurité sociale.
Ce numéro est constitué de 15 chiffres :

  • le premier chiffre est 11 s’il s’agit d’un homme, 22 s’il s’agit d’une femme ;
  • les deux chiffres suivants sont les deux derniers chiffres de l’année de naissance ;
  • viennent ensuite les deux chiffres du mois de naissance ;
  • les cinq chiffres suivants désignent le lieu de naissance (numéro du département et code de la commune de naissance, ou 9999 si la naissance est à l’étranger, suivi du code du pays) ;
  • les trois chiffres d’après désignent le numéro d’ordre de la naissance dans le mois et la commune ;
  • les deux derniers chiffres enfin résultent d’un calcul.
  • Voici comment faire ce calcul.

Il faut effectuer la division euclidienne des 1313 premiers chiffres par 9797.
Ensuite, on calcule la différence entre 9797 et le reste obtenu. On a ainsi les deux derniers chiffres, qui constituent une clé de contrôle.

  • Le calcul du numéro de Sécurité sociale fait donc appel à la division euclidienne.
bannière astuce

Astuce

La clé est comprise entre 0101 et 9797 (ne pas prendre le reste lui-même permet d’éviter d’avoir une clé nulle).

  • Il s’agit d’un code correcteur d’erreur, très utilisé en informatique, qui permet de localiser une erreur et même de la corriger.

Pour avoir un exemple, très simplifié, d’un code correcteur, vous pouvez regarder ce petit cours sur le code de Hamming (7,4,3)(7,\,4,\,3).

La divisibilité dans Z\mathbb Z et la division euclidienne de deux entiers relatifs vont nous permettre de travailler sur une nouvelle notion, qui est la congruence dans Z\mathbb Z.

Congruences dans Z\mathbb{Z}

Commençons par donner la définition de cette nouvelle notion.

Définition

Regardons la suite de nombres suivante :

11+38+35+32+31+34+37+310-11 \xrightarrow{+3}-8\xrightarrow{+3}-5\xrightarrow{+3}-2\xrightarrow{+3}1\xrightarrow{+3}4\xrightarrow{+3}7\xrightarrow{+3}10

Si l’on prend 22 nombres, n’importe lesquels, parmi cette suite, nous voyons facilement que leur différence sera toujours un multiple de 33.

  • Par exemple, nous voyons que, pour « passer » de 8-8 à 77, nous ajoutons 55 fois 33 :

8+5×3=77(8)=5×3-8+5\times 3 = 7 \Leftrightarrow 7-(-8) = 5\times3

  • Pour autre exemple, nous voyons que, pour « passer » de 11 à 5-5, nous soustrayons 22 fois 33 :

12×3=551=2×31-2\times 3 = -5 \Leftrightarrow -5-1 = -2\times3

Comme ils sont égaux à un multiple de 33 près, on dit que :

  • 77 et 8-8 sont congrus modulo 33 ;
  • 5-5 et 11 sont congrus modulo 33.
bannière definition

Définition

Congruence :

nn désigne un entier naturel non nul, aa et bb sont des entiers relatifs.
On dit que aa et bb sont congrus modulo nn lorsque la différence aba - b est un multiple de nn, ou bien que nn divise aba - b, ce qui est équivalent.

  • On dit aussi que aa et bb sont égaux modulo nn.

Les notations possibles sont les suivantes :

  • ab modna\equiv b\ \text{mod}\,n,
  • ou ab(n)a\equiv b\,(n),
  • ou encore ab[n]a\equiv b\,\lbrack n\rbrack.
  • Dans ce cours, nous choisissons d’utiliser cette dernière notation.
bannière à retenir

À retenir

  • On peut ajouter ou multiplier membre à membre des congruences modulo nn.
  • Si ab[n]a\equiv b\,\lbrack n\rbrack, avec aa et bb des entiers relatifs, et nn un entier naturel non nul, alors, pour tout kZk\in \mathbb Z :

k+ak+b[n]kakb[n]ab[n] (avec k=1)\begin{aligned} k+a&\equiv k+b\,\lbrack n\rbrack \ \ ka &\equiv kb\,\lbrack n\rbrack\ -a&\equiv -b\,\lbrack n\rbrack \footnotesize{\textcolor{#A9A9A9}{\text{ (avec $k=-1$)}}} \end{aligned}

  • La relation de congruence est symétrique, c’est-à-dire que, si ab[n]a\equiv b\,\lbrack n\rbrack, on a aussi ba[n]b\equiv a\,\lbrack n\rbrack.
  • En effet, si aba-b est un multiple de nn, bab-a est aussi un multiple de nn.
  • Dernier point, la relation de congruence est réflexive, c’est-à-dire qu’on a toujours aa[n]a\equiv a\,\lbrack n\rbrack.

Prenons quelques exemples pour comprendre cette notion.

bannière exemple

Exemple

  • 19(4)=15-19-(-4)=-15.

Le nombre 15-15 est un multiple de 55, donc 19-19 et 4-4 sont congrus modulo 55 :

194[5]-19\equiv -4\,\lbrack5\rbrack

  • 16(1)=15-16-(-1)=-15.

Donc 16-16 et 1-1 sont congrus modulo 55 :

161[5]-16\equiv -1\,\lbrack5\rbrack

Pour utiliser les propriétés vues plus haut, nous pouvons aussi le déduire de la relation 1 :

194[5]19+34+3[5]161[5](car, si ab[n], alors a+kb+k[n])161[5](car, si ab[n], alors ab[n])116[5] (par symeˊtrie)\begin{aligned} -19 \equiv -4\,\lbrack 5\rbrack &\Leftrightarrow -19 +3\equiv -4+3\,\lbrack 5\rbrack \ &\Leftrightarrow -16 \equiv -1\,\lbrack 5\rbrack \ &\footnotesize{\textcolor{#A9A9A9}{\text{(car, si ab[n]a\equiv b\,\lbrack n\rbrack, alors $ a+k\equiv b+k\,\lbrack n\rbrack $)}}} \ &\Leftrightarrow 16 \equiv 1\,\lbrack 5\rbrack \ &\footnotesize{\textcolor{#A9A9A9}{\text{(car, si ab[n]a\equiv b\,\lbrack n\rbrack, alors $ -a\equiv -b\,\lbrack n\rbrack $)}}} \ &\Leftrightarrow 1 \equiv 16\,\lbrack 5\rbrack \footnotesize{\textcolor{#A9A9A9}{\text{ (par symétrie)}}} \end{aligned}

  • 816=88-16=-8.

Le nombre 8-8 n’est pas un multiple de 55, donc 88 et 1616 ne sont pas congrus modulo 55 :

8≢16[5]8 \not \equiv 16\,\lbrack5\rbrack

En revanche, 8-8 est un multiple de 44, donc 88 et 1616 sont congrus modulo 44.

Les « raccourcis » suivants sont à connaître.

bannière à retenir

À retenir

  • Un entier relatif est congru à 00 modulo nn si et seulement si ce nombre est un multiple de nn.
  • Par exemple 2525 est congru à 00 modulo 55 : 250[5]25\equiv 0\,\lbrack 5\rbrack.
  • Tout nombre pair est congru à 00 modulo 22, et tout nombre impair est congru à 11 modulo 22. On a donc :
  • 12351\,235 est congru à 11 modulo 22 : 12351[2]1\,235\equiv 1\,\lbrack 2\rbrack ;
  • 12361\,236 est congru à 00 modulo 22 : 12360[2]1\,236\equiv 0\,\lbrack 2\rbrack.
  • Tout entier relatif est congru à son chiffre des unités modulo 1010.
  • 3579435\,794 est congru à 44 modulo 1010 : 35 7944[10]35\ 794\equiv 4\,\lbrack 10\rbrack.

Lien entre congruences et division euclidienne

Maintenant que nous savons ce qu’est la congruence, voyons son lien avec la division euclidienne revue en début de cours.

bannière propriete

Propriété

Pour un entier naturel non nul nn, tout entier relatif est congru modulo nn au reste de sa division euclidienne par nn.

bannière demonstration

Démonstration

Si on effectue la division euclidienne d’un entier relatif aa par un entier naturel non nul nn, on sait qu’il existe qq appartenant à l’ensemble des entiers relatifs Z\mathbb Z et rr appartenant à l’ensemble des entiers naturels N\mathbb N tels que a=qn+ra=qn+r, avec 0r<n0\leq r < n.
On a alors ar=qna-r=qn.

  • Donc ara-r est un multiple de nn et ainsi aa est congru à rr modulo nn.

Par conséquent, il advient la propriété suivante pour deux entiers relatifs aa et bb.

bannière propriete

Propriété

  • aa et bb sont congrus modulo nn si et seulement si aa et bb ont le même reste dans la division euclidienne par nn.
  • Si ar[n]a\equiv r\,\lbrack n\rbrack avec rr tel que 0r<n0 \leq r < n, alors rr est le reste de la division euclidienne de aa par nn.

Prenons deux exemples pour illustrer ces propriétés.

bannière exemple

Exemple

Avec la division euclidienne de 551551 par 2626, on obtient : 551=21×26+5551=21\times26+5.

  • Donc 551551 est congru à 55 modulo 2626 :

5515[26]551\equiv 5\,\lbrack 26\rbrack

Avec la division euclidienne de 189189 par 3535, on obtient : 189=5×35+14189=5\times35+14.

  • Donc 189189 est congru à 1414 modulo 3535 :

18914[35]189\equiv 14\,\lbrack 35\rbrack

Voyons maintenant les principales propriétés de la congruence dans Z\mathbb Z.

Propriétés

Soit un entier naturel non nul nn et cinq entiers relatifs aa, bb, cc, aa^{\prime} et bb^{\prime}.

bannière propriete

Propriété

  • Si on a ab[n]a\equiv b\,\lbrack n\rbrack et bc[n]b\equiv c\,\lbrack n\rbrack, alors :

ac[n]a\equiv c\,\lbrack n\rbrack

  • C’est la transitivité.
  • Si on a ab[n]a\equiv b\,\lbrack n\rbrack et ab[n]a^{\prime}\equiv b^{\prime}\,\lbrack n\rbrack, alors :

a+ab+b[n]aabb[n]\begin{aligned} a+a^{\prime}&\equiv b+b^{\prime}\,\lbrack n\rbrack \ a-a^{\prime}&\equiv b-b^{\prime}\,\lbrack n\rbrack \end{aligned}

  • On dit que la congruence est compatible avec l’addition (et la soustraction).
bannière exemple

Exemple

138[5]-13\equiv -8\,\lbrack 5\rbrack et 4621[5]46\equiv 21\,\lbrack 5\rbrack, donc :

3313[5]5929[5]\begin{aligned} 33&\equiv 13\,\lbrack 5\rbrack \ -59&\equiv -29\,\lbrack 5\rbrack \end{aligned}

Les réponses données dans l’exemple ci-dessus sont justes.
Il est tout de même préférable, et fortement recommandé, de se ramener à une congruence b[n]b\,\lbrack n\rbrack0b<n0\leq b.

  • Cela se justifie par le lien entre congruence et division euclidienne.

Pour cela, nous utilisons la propriété – évidente mais à ne jamais oublier – suivante.

bannière propriete

Propriété

Avec kk un entier relatif :

a+kna[n]a+kn \equiv a\,\lbrack n\rbrack

bannière exemple

Exemple

Ainsi, en reprenant les résultats de l’exemple précédent, nous obtenons :

3313[5]3+2×5[5]3[5]5929[5]16×5[5]1[5]\begin{aligned} 33&\equiv 13\,\lbrack 5\rbrack \ &\equiv 3+2\times5\,\lbrack 5\rbrack \ &\equiv 3 \,\lbrack 5\rbrack \ \ -59&\equiv -29\,\lbrack 5\rbrack \ &\equiv 1-6\times5\,\lbrack 5\rbrack \ &\equiv 1 \,\lbrack 5\rbrack \end{aligned}

Nous aurions aussi pu transformer les expressions dès le début, pour arriver au même résultat :

138[5]22×5[5]2[5]4621[5]1+4×5[5]1[5]\begin{aligned} -13&\equiv -8\,\lbrack 5\rbrack \ &\equiv 2-2\times5\,\lbrack 5\rbrack \ &\equiv 2\,\lbrack 5\rbrack \ \ 46&\equiv 21\,\lbrack 5\rbrack \ &\equiv 1+4\times5\,\lbrack 5\rbrack \ &\equiv 1\,\lbrack 5\rbrack \end{aligned}

Continuons à étudier les propriétés des congruences.

bannière propriete

Propriété

La congruence est compatible avec la multiplication.
C’est-à-dire que, si on a $a\equiv b\,\lbrack n\rbrack$ et ab[n]a^{\prime}\equiv b^{\prime} \lbrack n\rbrack, alors :

aabb[n]aa^{\prime}\equiv bb^{\prime}\,\lbrack n\rbrack

bannière attention

Attention

Ce n’est pas valable avec la division ! Par exemple :

255[10] mais 5≢1[10]25\equiv 5\,\lbrack 10\rbrack \text{ mais } 5\not \equiv1\,\lbrack 10\rbrack

De la dernière propriété, nous pouvons tirer une conséquence.

bannière propriete

Propriété

Si on a $a\equiv b\,\lbrack n\rbrack$, alors, pour tout pNp\in\mathbb N :

apbp[n]a^p\equiv b^p\,\lbrack n\rbrack

bannière exemple

Exemple

72[5]7\equiv 2\,\lbrack 5\rbrack, donc 7222[5]7^2 \equiv 2^2\,\lbrack 5\rbrack, c’est-à-dire :

494[5]49\equiv 4\,\lbrack 5\rbrack

bannière astuce

Astuce

Si on a a1[n]a\equiv -1\,\lbrack n\rbrack, alors, pour tout pNp\in \mathbb N :

ap(1)p[n]a^p\equiv(-1)^p\,\lbrack n\rbrack

Nous allons maintenant prendre l’exemple simple d’un raisonnement à mener dans un exercice faisant intervenir les congruences.

bannière exemple

Exemple

Il s’agit de montrer que 6101[11]6^{10} \equiv 1\,\lbrack 11\rbrack.

  • Autrement dit, pour nous figurer plus « concrètement » le raisonnement théorique, il s’agit de montrer que le reste de la division euclidienne de 6106^{10} par 1111 est égal à 11.
  • Nous pouvons commencer par remarquer que 62=366^2 = 36, qui est proche de 3×11=333\times 11 = 33.

Nous avons donc :

62=36=3×11+33[11]D’ouˋ : 610=(62)5 35[11] (car, si ab[n], alors apbp[n])\begin{aligned} 6^2&=36 \ &=3\times11+3 \ &\equiv 3\,\lbrack11\rbrack \ \ \textcolor{#A9A9A9}{\text{D’où\ : }}6^{10} &= \left(6^2\right)^5 \ &\equiv \ 3^5 \,\lbrack 11\rbrack \footnotesize{\textcolor{#A9A9A9}{\text{ (car, si $a\equiv b\,\lbrack n\rbrack$, alors $a^p\equiv b^p\,\lbrack n\rbrack$)}}} \end{aligned}

  • 32=93^2 = 9 est proche de 1111, nous allons donc faire apparaître 323^2 en utilisant le fait que 5=2×2+15 = 2\times 2 + 1 :

610 35[11] 32×2+1[11] (32)2×3[11] 92×3[11]\begin{aligned} 6^{10} &\equiv \ 3^5 \,\lbrack 11\rbrack \ &\equiv \ 3^{2\times 2 + 1}\,\lbrack 11\rbrack \ &\equiv \ {(3^2)}^2 \times 3\,\lbrack 11\rbrack \ &\equiv \ 9^2 \times 3 \,\lbrack 11\rbrack \end{aligned}

  • Nous remarquons enfin que 9(2)=119-(-2)=11 et donc que 92[11]9 \equiv -2 \,\lbrack 11\rbrack.

Nous obtenons ainsi :

610 92×3[11](2)2×3[11] (car 92(2)2[11])4×3[11]12[11]1[11]\begin{aligned} 6^{10} &\equiv \ 9^2 \times 3 \,\lbrack 11\rbrack \ &\equiv \left(-2\right)^2 \times 3 \,\lbrack 11\rbrack \footnotesize{\textcolor{#A9A9A9}{\text{ (car $9^2 \equiv \left(-2\right)^2 \,\lbrack 11\rbrack$)}}} \ &\equiv 4 \times 3 \,\lbrack 11\rbrack \ &\equiv 12 \,\lbrack 11\rbrack \ &\equiv 1 \,\lbrack 11\rbrack \end{aligned}

  • Le reste de la division euclidienne de 6106^{10} par 1111 est égal à 11.

Résolution d’une équation avec des congruences

Nous allons maintenant, à travers un exemple, voir comment nous pouvons résoudre une équation du type axb[n]ax \equiv b \,\lbrack n\rbrack.

bannière exemple

Exemple

Nous souhaitons résoudre l’équation 3x4[5]3x \equiv 4\,\lbrack 5\rbrackxx est un entier relatif.

  • Il s’agit de trouver l’ensemble des xx tels que le division euclidienne de 3x3x par 55 ait pour reste 44.

Pour résoudre cette équation, nous allons remplir un tableau, afin d’étudier les différents cas possibles.

  • Modulo 55, l’entier relatif xx est congru à 00, 11, 22, 33 ou 44 (qui est l’ensemble des restes possibles de la division euclidienne par 55).
  • Nous pouvons donc remplir la première ligne du tableau :

x modulo 5x \text{ modulo }5 00 11 22 33 44
3x modulo 53x \text{ modulo }5
bannière astuce

Astuce

En règle générale, pour résoudre une équation du type axb[n]ax\equiv b\,\lbrack n\rbrack, nous nous assurons que b<nb, puis nous nous intéressons aux valeurs de xx comprises entre 00 et n1n-1.

  • Nous allons maintenant étudier, pour chaque cas, 3x modulo 53x \text{ modulo } 5.
  • Si x0[5]x \equiv 0\,\lbrack 5\rbrack, nous avons :

3x3×0[5]0[5]\begin{aligned} 3x &\equiv 3\times 0\,\lbrack 5\rbrack \ &\equiv0\,\lbrack 5\rbrack \end{aligned}

  • Si x1[5]x \equiv 1\,\lbrack 5\rbrack, nous avons :

3x3×1[5]3[5]\begin{aligned} 3x &\equiv 3\times 1\,\lbrack 5\rbrack \ &\equiv3\,\lbrack 5\rbrack \end{aligned}

  • Si x2[5]x \equiv 2\,\lbrack 5\rbrack, nous avons :

3x3×2[5]6[5]1+5[5]1[5]\begin{aligned} 3x &\equiv 3\times 2\,\lbrack 5\rbrack \ &\equiv6\,\lbrack 5\rbrack \ &\equiv1+5\,\lbrack 5\rbrack \ &\equiv1\,\lbrack 5\rbrack \end{aligned}

  • Si x3[5]x \equiv 3\,\lbrack 5\rbrack, nous avons :

3x3×3[5]9[5]4[5]\begin{aligned} 3x &\equiv 3\times 3\,\lbrack 5\rbrack \ &\equiv9\,\lbrack 5\rbrack \ &\equiv4\,\lbrack 5\rbrack \end{aligned}

  • Si x4[5]x \equiv 4\,\lbrack 5\rbrack, nous avons :

3x3×4[5]12[5]2+2×5[5]2[5]\begin{aligned} 3x &\equiv 3\times 4\,\lbrack 5\rbrack \ &\equiv12\,\lbrack 5\rbrack \ &\equiv2 + 2 \times5\,\lbrack 5\rbrack \ &\equiv2\,\lbrack 5\rbrack \end{aligned}

  • Nous pouvons donc compléter le tableau, en identifiant la valeur (en rouge) et la colonne (en vert) qui nous intéressent :

x modulo 5x \text{ modulo }5 00 11 22 33 44
3x modulo 53x \text{ modulo }5 00 33 11 4\red 4 22
  • En lisant le tableau, nous pouvons conclure que les seules solutions de l’équation 3x4[5]3x \equiv 4\,\lbrack 5] sont donc les nombres entiers relatifs xx congrus à 33 modulo 55.
  • Nous avons donc :

S={3+5k ;kZ}S = \lbrace 3+5k\ ;\,k\in\mathbb Z\rbrace

Conclusion :

Dans ce cours, après avoir rappelé la division euclidienne et l’avoir étendue à l’ensemble des entiers relatifs, nous avons découvert la notion de congruences, où, pour que deux entiers relatifs aa et bb soient congrus modulo nn (un entier naturel non nul), il faut et il suffit que la différence aba - b soit un multiple de nn, ou bien que nn divise aba - b.