Divisibilité et congruence

Divisibilité

Dans toute la suite de cette section, on notera par Z\mathbb{Z} l’ensemble des nombres entiers relatifs (i.e. Z={,2,1,0,1,2,}\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}) et par N\mathbb{N} l’ensemble des nombres entiers naturels (i.e. N={0,1,2,}\mathbb{N} = \{0, 1, 2, \dots\}).

Définition

Soient aa et bb deux entiers relatifs. On dit que bb divise aa (ou que aa est un multiple de bb) s’il existe kZk \in \mathbb{Z} tel que a=kba = kb. On note ceci par bab \mid a.

Propriétés

  • Tout entier relatif bb divise 00 (car 0=0×b0 = 0 \times b).

  • 11 divise tout entier relatif aa (car a=a×1a = a \times 1).

  • Si cac \mid a et cbc \mid b alors c(au+bv)c \mid (au + bv) pour tout uu, vZv \in \mathbb{Z}.

Division euclidienne

La division euclidienne est une notion mathématique que l’on aborde très tôt au cours de notre scolarité (dès la classe de CM1). Nous allons tenter de formaliser ceci :

Théorème de la division euclidienne

Soient aa, bZb \in \mathbb{Z}. On suppose b0b \neq 0. On appelle division euclidienne de aa par bb, l’opération qui à (a,b)(a, b), associe le couple d’entiers relatifs (q,r)(q, r) tel que a=bq+ra = bq + r0r<b0 \leq r < |b|. Un tel couple existe forcément et est unique.

Vocabulaire

En reprenant les notations du théorème, aa s’appelle le dividende, bb le diviseur, qq le quotient et rr le reste de la division euclidienne.

Donnons enfin une propriété qui nous sera utile dans la section suivante.

Propriété

Soit nNn \in \mathbb{N} tel que n0n \neq 0. Deux entiers relatifs aa et bb ont le même reste dans la division euclidienne par nn si et seulement si aba-b est un multiple de nn.

Congruences dans Z\mathbb{Z}

Définition

On dit que deux entiers relatifs aa et bb sont congrus modulo nn (où nn est un entier naturel supérieur ou égal à 22) si aa et bb ont le même reste dans la division euclidienne par nn. On note alors abmodna \equiv b \mod n.

On signale que la congruence est une relation d’équivalence.

Propriétés

Soit n2n \geq 2. Pour tout aa, bb, cZc \in \mathbb{Z} :

  • aamodna \equiv a \mod n (réflexivité)

  • Si abmodna \equiv b \mod n, alors bamodnb \equiv a \mod n (symétrie)

  • Si abmodna \equiv b \mod n, et si bcmodnb \equiv c \mod n, alors acmodna \equiv c \mod n (transitivité)

De plus, la congruence est compatible avec les opérations usuelles sur les entiers relatifs.

Propriétés

Soit n2n \geq 2. Soient aa, bb, cc et dZd \in \mathbb{Z} tels que abmodna \equiv b \mod n et cdmodnc \equiv d \mod n. Alors on a la compatibilité avec :

  • L’addition : a+cb+dmodna + c \equiv b + d \mod n.

  • La multiplication : acbdmodnac \equiv bd \mod n.

  • Les puissances : pour tout kNk \in \mathbb{N}, akbkmodna^k \equiv b^k \mod n.

PGCD et théorème de Bézout

Plus Grand Commun Diviseur

Définition

Soient aa, bZb \in \mathbb{Z} non tous nuls. Le Plus Grand Commun Diviseur de aa et bb (noté PGCD(a;b)\operatorname{PGCD}(a; b)) est le plus grand entier positif qui les divise simultanément.

Avec cette définition, on peut dégager quelques propriétés.

Propriétés

Soient aa, bZb \in \mathbb{Z} non tous nuls.

  • PGCD(a;b)=PGCD(b;a)\operatorname{PGCD}(a; b) = \operatorname{PGCD}(b; a)

  • PGCD(a;1)=1\operatorname{PGCD}(a; 1) = 1

  • PGCD(a;0)=a\operatorname{PGCD}(a; 0) = a

  • Pour tout kNk \in \mathbb{N}, PGCD(ka;kb)=kPGCD(a;b)\operatorname{PGCD}(ka; kb) = k \operatorname{PGCD}(a; b)

  • Si bab \mid a, alors PGCD(a;b)=b\operatorname{PGCD}(a; b) = |b|

Il existe une manière de déterminer le PGCD\operatorname{PGCD} de deux entiers naturels non nuls aa et bb avec b<ab < a appelée Algorithme d’Euclide.

Algorithme d’Euclide

Soient aa, bZb \in \mathbb{Z} non tous nuls. Pour obtenir PGCD(a;b)\operatorname{PGCD}(a; b), on procède comme suit :

  1. On fait la division euclidienne de aa par bb et on appelle rr le reste.

  2. Si r=0r = 0, alors PGCD(a;b)=b\operatorname{PGCD}(a; b) = b.

  3. Sinon on recommence l’étape 1 en remplaçant aa par bb et bb par rr.

Terminons cette section par une définition.

Nombres premiers entre eux

On dit que deux nombres sont premiers entre eux si leur PGCD\operatorname{PGCD} est égal à 1.

Théorème de Bézout

Un résultat fondamental de l’arithmétique est le théorème de Bachet-Bézout (que l’on rencontre parfois sous le nom d’identité de Bézout).

Théorème de Bachet-Bézout

Soient aa et bb deux entiers relatifs non nuls. On note dd leur PGCD. Alors il existe deux entiers relatifs uu et vv tels que ua+vb=dua + vb = d.

Théorème de Bézout

Une conséquence de ce théorème est que aa et bb sont premiers entre eux si et seulement s’il existe deux entiers relatifs uu et vv tels que ua+vb=1ua + vb = 1.

Résolution d’une congruence simple

Supposons que l’on souhaite résoudre une congruence du type axbmodnax \equiv b \mod n d’inconnue xx. On pose d=PGCD(a;n)d = \operatorname{PGCD(a; n)}. Alors :

  1. Si dd ne divise pas bb, on cherche deux entiers uu et vv tels que au+nv=1au + nv = 1 (avec l’algorithme d’Euclide étendu par exemple). Les solutions de la congruence sont alors les entiers xx vérifiant xubmodnx \equiv ub \mod n.

  2. Si dbd \mid b, cela revient à résoudre la congruence adxbdmodnd\displaystyle{\frac{a}{d}x \equiv \frac{b}{d} \mod \frac{n}{d}}, et on se ramène au cas 1 (avec la nouvelle congruence à résoudre).

Lemme de Gauss

Lemme de Gauss

Soient aa, bb et cc trois entiers non nuls. Si cabc \mid ab et cc est premier avec aa, alors cbc \mid b.

Corollaire

Soient aa, bb et cc trois entiers non nuls. Si bab \mid a, cac \mid a et que bb et cc sont premiers entre eux, alors bcabc \mid a.

Équations diophantiennes

Définition

Une équation diophantienne linéaire en deux variables xx et yy est une équation de la forme (E):ax+by=c(E) : ax + by = c où les coefficients aa, bb et cc sont des entiers relatifs et où les solutions sont également des entiers relatifs.

Solutions de (E)(E)

En reprenant les notations précédentes, on pose d=PGCD(a;b)d = \operatorname{PGCD}(a; b). Alors :

  • Si dcd \mid c, on cherche une solution particulière à (E)(E) que l’on note (x0;y0)(x_0; y_0). Alors les solutions de (E)(E) sont les couples (xk;yk)(x_k; y_k)xk=x0+kbd\displaystyle{x_k = x_0 + k\frac{b}{d}} et yk=y0kad\displaystyle{y_k = y_0 - k\frac{a}{d}}.

  • Sinon, (E)(E) n’a pas de solution.

Nombres premiers

Définition

Commençons cette section par définir ce qu’est un nombre premier. Il s’agit là d’une notion dont entend parler très tôt au cours de notre scolarité, sans pour autant vraiment rentrer dans le sujet. Détaillons donc un peu tout ceci.

Nombre premier

Un nombre entier p2p \geq 2 est dit premier si ses seuls diviseurs positifs sont 11 et lui-même.

Propriétés

Voici quelques propriétés basiques que possèdent les nombres premiers.

Propriétés

Soit nNn \in \mathbb{N} supérieur ou égal à 2, alors on a les propriétés suivantes :

  • Si nn n’admet aucun diviseur premier inférieur ou égal à n\sqrt{n}, alors nn est premier.

  • Si nn n’est pas premier alors nn admet au moins un diviseur premier inférieur ou égal à n\sqrt{n}.

  • Si nn est premier et nn ne divise pas un entier mm, alors nn et mm sont premiers entre eux.

Lemme d’Euclide

Soit pp un nombre premier et aa et bb deux entiers. Si pabp \mid ab alors pap \mid a ou pbp \mid b.

On donne enfin un résultat fondamental (mais qui reste très simple) sur l’ensemble des nombres premiers.

Infinité de nombres premiers

Il existe une infinité de nombres premiers.

Petit théorème de Fermat

Soit pp un nombre premier et aa un entier non divisible par pp. Alors ap11modpa^{p-1} \equiv 1 \mod p.

Décomposition de nombres

Passons maintenant à un résultat fondamental de l’arithmétique : le principe de décomposition en produit de facteurs premiers (il s’agit même là d’un théorème qui est sobrement intitulé théorème fondamental de l’arithmétique).

Théorème fondamental de l’arithmétique

Soit nNn \in \mathbb{N} supérieur ou égal à 2, alors nn peut s’écrire de la façon suivante :

n=p1α1×p2α2××pnαnn = p_{1}^{\alpha_1} \times p_{2}^{\alpha_2} \times \dots \times p_{n}^{\alpha_n}

p1p_1, p2p_2, ... , pnp_n des nombres premiers tels que p1<p2<<pnp_1 < p_2 < \dots < p_n et α1\alpha_1, α2\alpha_2, ... , αn\alpha_n des entiers naturels non nuls.