La divisibilité et la congruenceCours

I

La divisibilité

A

Les diviseurs

Entier divisible

Soient a et b deux entiers relatifs, avec b non nul. L'entier a est divisible par b si et seulement s'il existe un entier relatif k tel que :

a = kb

On a :

24=8\times3

Donc 24 est divisible par 3.

On peut aussi en déduire que 24 est divisible par 8.

Soient a et b deux entiers relatifs, avec b non nul. Les propositions suivantes sont équivalentes :

  • a est divisible par b ;
  • b est un diviseur de a ;
  • b divise a.

Soient a et b deux entiers relatifs, avec b non nul. Si b divise a, alors - b divise a.

4 divise 16, donc −4 divise également 16.

En effet, en prenant k=-4 :

\left(-4\right)\times\left(-4\right)=16

Soient a, b et d trois entiers relatifs avec d non nul. Si d divise les entiers a et b, il divise alors toute combinaison linéaire de a et de b du type ka + k'b, avec k et k' entiers relatifs.

4 divise 16 et 24, donc, par exemple, en prenant k=3 et k'=5 :

4 divise 3 \times 16 + 5 \times 24

Donc 4 divise 168.

B

Les multiples

Multiple

Soient a et b deux entiers relatifs, avec b non nul. L'entier a est un multiple de b si et seulement si b est un diviseur de a.

81 est un multiple de 9, et 9 est un diviseur de 81.

Soient a et b deux entiers relatifs, avec b non nul.

  • Si a est un multiple de b, alors - a est un multiple de b.
  • La somme et/ou la différence de multiples de b est un multiple de b.
  • Si a est un multiple de b, alors ka est un multiple de b (avec k entier relatif).
C

La division euclidienne

Division euclidienne

Soient a et b deux entiers relatifs, avec b non nul. Il existe un unique couple d'entiers relatifs \left(q ; r\right) tel que :

a = bq + r et 0 \leq r \lt \left| b \right|

  • L'entier q est le quotient de la division euclidienne de a par b.
  • L'entier r est le reste de la division euclidienne de a par b.

La division euclidienne de 103 par 12 est :

103 = 12 \times\textcolor{Red}{8} + \textcolor{Blue}{7}

Dans cet exemple, \textcolor{Red}{q = 8} et \textcolor{Blue}{r = 7}.

Soient a et b deux entiers relatifs, avec b non nul. On dit que a est multiple de b et que b divise a si et seulement si le reste de la division euclidienne de a par b est nul.

II

Les congruences

A

La caractérisation

Congruence

Soient a et b deux entiers et n un entier naturel supérieur ou égal à 2. On dit que a est congru à b modulo n si et seulement si \left(a - b\right) est multiple de n. On note :

a \equiv b \left[n\right]

On a :

51-27 = 24

Or 24 est multiple de 6, donc \left(51-27\right) est également un multiple de 6. Ainsi, on peut écrire :

51 \equiv 27 \left[6\right]

Soient a et b deux entiers, et n un entier naturel supérieur ou égal à 2. a \equiv b \left[n\right] si et seulement si a et b ont le même reste dans la division euclidienne par n.

On a :

  • 55=9\times 6 +1
  • 28=9\times3+1

Donc 55 et 28 ont le même reste dans la division euclidienne par 9. On peut ainsi écrire :

55\equiv28\left[9\right]

L'entier a est divisible par l'entier b (supérieur ou égal à 2) si et seulement si a \equiv 0 \left[b\right].

B

Les opérations

Soient n un entier naturel supérieur ou égal à 2, a, a', b et b' des entiers relatifs tels que a \equiv a' \left[n\right] et b \equiv b' \left[n\right], alors :

  • a + b \equiv a' + b' \left[n\right]
  • a - b \equiv a' - b' \left[n\right]
  • ab \equiv a'b' \left[n\right]
  • a^{k} \equiv a'^{k} \left[n\right] ( k entier naturel non nul)

Si a\equiv5\left[6\right] et b\equiv1\left[6\right] alors :

  • a+b\equiv5+1\left[6\right]\equiv6\left[6\right]\equiv0\left[6\right]
  • a-b\equiv5-1\left[6\right]\equiv4\left[6\right]
  • ab\equiv5\times 1\left[6\right]\equiv5\left[6\right]
  • a^2\equiv5^2\left[6\right]\equiv25\left[6\right]\equiv1\left[6\right]

Soient a, b et k des entiers relatifs et n un entier supérieur ou égal à 2.

Si a\equiv b\left[n\right], alors ka\equiv kb\left[n\right].

Attention, la réciproque est fausse.