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 !

Divisibilité dans Z\mathbb Z et division euclidienne

Nous étendons ici les définitions et les propriétés connues depuis le collège à l’ensemble des entiers relatifs.

  • 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.
  • 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.

Un entier relatif est divisible par… si et seulement si…
22 son chiffre des unités est 00, 22, 44, 66 ou 88
33 la somme de ses chiffres est divisible par 33
44 le nombre formé par son chiffre des dizaines et celui des unités est divisible par 44
55 son chiffre des unités est 00 ou 55
99 la somme de ses chiffres est divisible par 99
1010 son chiffre des unités est 00
  • Soit aa, bb et cc des entiers relatifs.
  • Si bb divise aa et si cc divise bb, alors cc divise aa.
  • Si cc divise aa et bb, alors pour tous les entiers relatifs nn et nn^{\prime}, cc divise na+nbna+n^{\prime} b.
  • Autrement dit, si cc divise aa et bb, alors il divise toutes les combinaisons linéaires entières de aa et bb.
  • 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.
  • L’entier relatif aa est le dividende et bb est le diviseur.
  • L’entier relatif qq s’appelle le quotient et rr s’appelle le reste de la division euclidienne de aa par bb.

Congruences dans Z\mathbb{Z}

  • 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.
  • Les notations possibles sont :
  • ab modna\equiv b\ \text{mod}\,n,
  • ou ab(n)a\equiv b\,(n),
  • ou encore ab[n]a\equiv b\,\lbrack n\rbrack.
  • Nous avons les propriétés suivantes (aa, aa^\prime, bb, bb^\prime et cc des entiers relatifs, nn un entier naturel) :

aa[n]a\equiv a\,\lbrack n\rbrack
Si ab[n]a\equiv b\,\lbrack n\rbrack ba[n]b\equiv a\,\lbrack n\rbrack
Pour tout kZk\in\mathbb Z :

k+ak+b[n]kakb[n]\begin{aligned} k+a&\equiv k+b\,\lbrack n\rbrack \ ka &\equiv kb\,\lbrack n\rbrack \end{aligned}

aa est congru à 00 modulo nn si et seulement si aa est un multiple de nn
Tout nombre pair est congru à 00 modulo 22, et tout nombre impair est congru à 11 modulo 22
Tout entier relatif est congru à son chiffre des unités modulo 1010
Tout entier relatif est congru modulo nn au reste de sa division euclidienne par nn
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
Si ab[n]a\equiv b\,\lbrack n\rbrack et bc[n]b\equiv c\,\lbrack n\rbrack ac[n]a\equiv c\,\lbrack n\rbrack
Si ab[n]a\equiv b\,\lbrack n\rbrack et ab[n]a^{\prime}\equiv b^{\prime}\,\lbrack n\rbrack a+ab+b[n]aabb[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 \ aa^{\prime}&\equiv bb^{\prime}\,\lbrack n\rbrack \end{aligned}
Si ab[n]a\equiv b\,\lbrack n\rbrack Pour tout pNp\in\mathbb N : apbp[n]a^p\equiv b^p\,\lbrack n\rbrack
  • 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 étudions ensuite, pour chaque cas, ax modulo nax \text{ modulo } n et nous remplissons un tableau avec les résultats trouvés ;
  • nous lisons dans le tableau réalisé, à la colonne concernée, l’ensemble solution cherché.
  • Ainsi, par exemple, pour l’équation 3x4[5]3x \equiv 4\,\lbrack 5\rbrack, nous obtenons le tableau suivant :

x modulo 5x \text{ modulo }5 00 11 22 33 44
3x modulo 53x \text{ modulo }5 00 33 11 4\red 4 22
  • S={3+5k ;kZ}S=\lbrace 3+5k\ ;\,k\in\mathbb Z\rbrace.