Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Divisibilité et congruences

1. Division euclidienne

Définition

Soient aa et bb deux entiers relatifs tels qu'il existe un entier relatif kk tel que a=bka=bk.

On dit alors que :

  • bb divise aa ;

  • bb est un diviseur de aa ;

  • aa est un multiple de bb.

Ceci se note bab|a

Exemple

15=3×515=3\times 5 donc :

  • 3 divise 15.

  • 3 est un diviseur de 15.

  • 15 est un multiple de 3.

Remarques

  • 0 est un multiple de tout entier relatif.

  • 1 et -1 sont des diviseurs de tout entier relatif.

  • aa et a - a ont les mêmes diviseurs.

Propriétés

  • Si aa divise bb et bb divise aa, alors aa et bb sont égaux ou opposés.

  • Si aa divise bb et bb divise cc, alors aa divise cc.

  • Si cc divise aa et cc divise bb, alors cc divise toute combinaison linéaire de aa et bb (c'est-à-dire tout nombre de la forme au+bv;uZ,vZau+bv ; u\in \mathbb{Z}, v\in \mathbb{Z}).

Théorème et définitions

Division euclidienne dans Z\mathbb{Z}

Soient aa et bb deux entiers relatifs avec b0b\neq 0.

Il existe un et un seul couple d'entiers relatifs (q,r)\left(q,r\right) tels que :

a=bq+ra=bq+r et 0r<b0 \leqslant r < |b|.

qq et rr s'appelle respectivement le quotient et le reste de la division euclidienne de aa par bb.

Exemple

-14=3×\times (-5)+1 et 0\leqslant 1< < 3

La division euclidienne de -14 par 3 donne un quotient de -5 est un reste de 1.

Remarques

  • Attention ! Ne pas oublier la condition 0r<b0 \leqslant r < |b|. La seule égalité a=bq+ra=bq+r ne suffit pas à prouver que qq et rr sont les quotient et reste dans la division euclidienne de aa par bb.

  • aa est divisible par bb si et seulement si le reste de la division de aa par bb est égal à zéro.

2. Congruences

Définition

On dit que deux entiers relatifs aa et bb son congrus modulo nn ( nNn\in \mathbb{N}^* ) et l'on écrit ab[n]a\equiv b \left[n\right] si et seulement si aa et bb ont le même reste dans la division par nn.

Exemple

1823[5]18\equiv 23 \left[5\right] car 18 et 23 ont tous les deux 3 comme reste dans la division par 5.

Propriétés

  • ab[n]a\equiv b \left[n\right] si et seulement si nn divise aba - b en particulier a0[n]a\equiv 0 \left[n\right] si et seulement si nn divise aa.

  • Si ab[n]a\equiv b \left[n\right] et bc[n]b\equiv c \left[n\right], alors ac[n]a\equiv c \left[n\right].

Propriétés (Congruences et opérations)

Soient quatre entiers relatifs a,b,c,da, b, c, d tels que ab[n]a\equiv b \left[n\right] et cd[n]c\equiv d \left[n\right]. Alors :

  • a+cb+d[n]a+c\equiv b+d \left[n\right] et acbd[n]a - c\equiv b - d \left[n\right].

  • acbd[n]ac\equiv bd \left[n\right].

  • kakb[n]ka\equiv kb \left[n\right] pour tout entier relatif kk.

  • ambm[n]a^{m}\equiv b^{m} \left[n\right] pour tout entier naturel mm.

Propriété

rr est le reste de la division euclidienne de aa par bb si et seulement si :

{ra[b]r<b\left\{ \begin{matrix} r\equiv a \left[b\right] \\ r < |b| \end{matrix}\right.

Exemple

On cherche à déterminer le reste de la division euclidienne de 200920092009^{2009} par 5.

20091[5]2009\equiv - 1 \left[5\right] car 2009-(-1)=2010 est divisible par 5.

Donc :

20092009(1)2009[5]2009^{2009}\equiv \left( - 1\right)^{2009} \left[5\right] c'est-à-dire 200920091[5]2009^{2009}\equiv - 1 \left[5\right]

Or 14[5] - 1\equiv 4 \left[5\right] donc 200920094[5]2009^{2009}\equiv 4 \left[5\right]

Comme 04<50\leqslant 4 < 5, le reste de la division euclidienne de 200920092009^{2009} par 5 est 4.