La divisibilité et la congruence Cours

La divisibilité

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 :

\(\displaystyle{a = kb}\)

On a :

\(\displaystyle{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 \(\displaystyle{- b}\) divise a.

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

En effet, en prenant \(\displaystyle{k=-4}\) :

\(\displaystyle{\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 \(\displaystyle{ka + k'b}\), avec k et k' entiers relatifs.

4 divise 16 et 24, donc, par exemple, en prenant \(\displaystyle{k=3}\) et \(\displaystyle{k'=5}\) :

4 divise \(\displaystyle{3 \times 16 + 5 \times 24}\)

Donc 4 divise 168.

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 \(\displaystyle{- 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).

La division euclidienne

Division euclidienne

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

\(\displaystyle{a = bq + r}\) et \(\displaystyle{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 :

\(\displaystyle{103 = 12 \times\color{Red}{8} + \color{Blue}{7}}\)

Dans cet exemple, \(\displaystyle{\color{Red}{q = 8}}\) et \(\displaystyle{\color{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.

Les congruences

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 \(\displaystyle{\left(a - b\right)}\) est multiple de n. On note :

\(\displaystyle{a \equiv b \left[n\right]}\)

On a :

\(\displaystyle{51-27 = 24}\)

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

\(\displaystyle{51 \equiv 27 \left[6\right]}\)

Soient a et b deux entiers, et n un entier naturel supérieur ou égal à 2. \(\displaystyle{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 :

\(\displaystyle{55=9\times 6 +1}\)
\(\displaystyle{28=9\times3+1}\)

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

\(\displaystyle{55\equiv28\left[9\right]}\)

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

Les opérations

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

\(\displaystyle{a + b \equiv a' + b' \left[n\right]}\)

\(\displaystyle{a - b \equiv a' - b' \left[n\right]}\)

\(\displaystyle{ab \equiv a'b' \left[n\right]}\)

\(\displaystyle{a^{k} \equiv a'^{k} \left[n\right]}\) ( \(\displaystyle{k}\) entier naturel non nul)

Si \(\displaystyle{a\equiv5\left[6\right]}\) et \(\displaystyle{b\equiv1\left[6\right]}\) alors :

\(\displaystyle{a+b\equiv5+1\left[6\right]\equiv6\left[6\right]\equiv0\left[6\right]}\)
\(\displaystyle{a-b\equiv5-1\left[6\right]\equiv4\left[6\right]}\)
\(\displaystyle{ab\equiv5\times 1\left[6\right]\equiv5\left[6\right]}\)
\(\displaystyle{a^2\equiv5^2\left[6\right]\equiv25\left[6\right]\equiv1\left[6\right]}\)