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.

Si on a bb divise aa, alors b-b divise aa. Par exemple, comme 66 divise 1212, alors 6-6 divise également 1212.

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.

Exemple

On souhaite effectuer la division euclidienne de 314314 par 77. Posons-la : image

  • On cherche combien de fois 77 est contenu dans 3131 (cela ne sert à rien de commencer par 33 car 3<73 < 7). On a 4×7=284 \times 7 = 28 et 5×7=355 \times 7 = 35 donc on écrit 44 sous le diviseur et le reste 3128=331 - 28 = 3. Puis, on abaisse le chiffre des unités qui est 44.

  • On recommence : combien de fois 77 est-il contenu dans 3434 ? Comme 4×7=284 \times 7 = 28 et 5×7=355 \times 7 = 35, 77 est contenu 44 fois dans 3434 et il reste 3428=634 - 28 = 6.

  • Comme 6<76 < 7, la division euclidienne est terminée : on a 314=7×44+6314 = 7 \times 44 + 6.

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 remarque que aa est un multiple de nn si et seulement si a0modna \equiv 0 \mod n.

Exemple

Par exemple, 147mod31 \equiv 4 \equiv 7 \mod 3. image

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.

Exemple

Comme 73mod47 \equiv 3 \mod 4, et 51mod45 \equiv 1 \mod 4, on a 35=5×71×5mod435 = 5 \times 7 \equiv 1 \times 5 \mod 4.

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.

Petite remarque : si on note dd le PGCD\operatorname{PGCD} de deux nombres aa et bb, alors ad\frac{a}{d} et bd\frac{b}{d} sont deux nombres premiers entre eux.

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.

Exemple

Calculons PGCD(250;150)\operatorname{PGCD}(250; 150) et déduisons-en deux entiers relatifs uu et vv tels que 50=250u+150v50 = 250u + 150v. Commençons par calculer le PGCD\operatorname{PGCD} de 250250 et 150150 par l’algorithme d’Euclide :

La division euclidienne de 250250 par 150150 donne 250=150×1+100250 = 150 \times 1 + 100. La division euclidienne de 150150 par 100100 donne 150=100×1+50150 = 100 \times 1 + 50. La division euclidienne de 100100 par 5050 donne 100=5×2+0100 = 5 \times 2 + 0.

On a PGCD(250;150)=50\operatorname{PGCD}(250;150) = 50. Déterminons uu et vv :

250=150×1+100    150=1×2501×100250 = 150 \times 1 + 100 \iff 150 = 1 \times 250 - 1 \times 100 150=1×100+50    50=1501×100150 = 1 \times 100 + 50 \iff 50 = 150 - 1 \times 100

Donc 50=1×2501×1001×100=1×2502×10050 = 1 \times 250 - 1 \times 100 - 1 \times 100 = 1 \times 250 - 2 \times 100.

On a par conséquent u=1u = 1 et v=2v = -2. L’algorithme que l’on vient d’utiliser pour trouver uu et vv s’appelle l’algorithme d’Euclide étendu.

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

Exemple

On souhaite résoudre la congruence 6x6mod96x \equiv 6 \mod 9. Alors, comme d=PGCD(6;9)=3d = \operatorname{PGCD}(6; 9) = 3, on a d6d \mid 6. On se ramène donc à résoudre 2x2mod32x \equiv 2 \mod 3 (où 22 et 33 sont premiers entre eux).

On écrit l’identité de Bézout appliquée à 22 et 33 : 2×2+3×1=12 \times 2 + 3 \times -1 = 1. Donc les solutions à la congruence du début sont les entiers xx vérifiant x4mod31mod3x \equiv 4 \mod 3 \equiv 1 \mod 3 (i.e. les xx de la forme x=3k+1x = 3k + 1kZk \in \mathbb{Z}).

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.

Exemple

On cherche à résoudre l’équation diophantienne (E):25x+10y=15(E) : 25x + 10y = 15. Commençons par chercher une solution particulière (x0;y0)(x_0; y_0).

Comme d=PGCD(25;10)=5d = \operatorname{PGCD}(25; 10) = 5, on a d15d \mid 15. En divisant les deux côtés de l’égalité par 55, on a (E)    5x+2y=3(E) \iff 5x + 2y = 3.

Cherchons une solution particulière à (E)(E). On écrit l’identité de Bézout appliquée à 55 et 22 : 5×1+2×2=15 \times 1 + 2 \times -2 = 1. Ainsi, en multipliant les deux côtés de l’égalité par 33, on obtient : 5×3+2×6=35 \times 3 + 2 \times -6 = 3.

On a trouvé une solution particulière à (E)(E) qui est le couple (x0;y0(x_0; y_0) où x0=3x_0 = 3 et y0=6y_0 = -6. On pourrait appliquer la formule pour donner la forme générale des solutions de (E)(E), mais essayons de ne pas l’utiliser.

Soit (x;y)(x; y) une autre solution de (E)(E). On a 3=5x+2y=5x0+2y03 = 5x + 2y = 5x_0 + 2y_0. D’où 5(xx0)=2(y0y)5(x - x_0) = 2(y_0 - y) (en passant les xx et x0x_0 du même côté de l’égalité et en faisant de même pour yy et y0y_0, puis en factorisant).

Ainsi, on a 52(y0y)5 \mid 2(y_0 - y). Or, 55 et 22 sont premiers entre eux, donc par le lemme de Gauss, 5y0y5 \mid y_0 - y. Il existe donc q1q_1 tel que 5q1=y0y5q_1 = y_0 - y, d’où y=y05q1y = y_0 - 5q_1.

De même, 25(xx0)2 \mid 5(x - x_0) avec 22 et 55 premiers entre eux, donc par le lemme de Gauss, 2xx02 \mid x - x_0. Il existe donc q2q_2 tel que 2q2=xx02q_2 = x - x_0, d’où x=x0+2q2x = x_0 + 2q_2.

En réinjectant tout ça dans (E)(E), on obtient 5(x0+2q2)+2(y0+5q1)=3    5x0+2y0=3+10q210q1=3    q1=q25(x_0 + 2q_2) + 2(y_0 + -5q_1) = 3 \iff \underbrace{5x_0 + 2y_0}_{= 3} + 10q_2 - 10q_1 = 3 \iff q_1 = q_2.

Les solutions de (E)(E) sont donc les couples (xk;yk)(x_k; y_k)xk=x0+2kx_k = x_0 + 2k et yk=y05ky_k = y_0 - 5k (et on a bien les mêmes résultats qu’avec la formule).

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.

Exemple

22, 33, 55, 77, 1111 et 1313 sont des nombres premiers.

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.

Démonstration

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.

Cela revient au même de dire que si aa est un entier quelconque et que pp est un nombre premier, alors apamodpa^p \equiv a \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.

Exemple

Décomposons 200200 en produit de facteurs premiers.

  • 200=2×100200 = 2 \times 100 (22 est le plus petit nombre premier qui divise 200200).

  • 100=2×50100 = 2 \times 50 (22 est le plus petit nombre premier qui divise 100100).

  • 50=2×2550 = 2 \times 25 (22 est le plus petit nombre premier qui divise 5050).

  • 25=5×525 = 5 \times 5 (55 est le plus petit nombre premier qui divise 2525).

  • 5=5×15 = 5 \times 1 (55 est un nombre premier, c’est terminé).

On a donc 200=2×100=2×(2×50)==23×52200 = 2 \times 100 = 2 \times (2 \times 50) = \dots = 2^3 \times 5^2.

Vous avez aimé ce cours ?

Faîtes-le nous savoir dans les commentaires !

Avatar (prévisualisation)
Il n'y a pas de commentaire sur ce cours pour le moment.