Arithmétique & structures

Arithmétique des entiers — division, PGCD, Bézout, congruences

Idée. L'arithmétique étudie la divisibilité dans $\mathbb Z$ . Deux outils structurent tout : la division euclidienne (qui engendre l'algorithme d'Euclide et le PGCD) et les congruences (l'arithmétique « modulo $n$ », où l'on calcule sur les restes).

A. Division euclidienne

Pour $a\in\mathbb Z$ et $b\in\mathbb N^*$ , il existe un unique couple $(q,r)$ tel que

a=bq+r,\qquad 0\le r<b.

q

est le quotient,

r

le reste. On dit que

b

divise

a

(noté

b\mid a

) lorsque

r=0

Exemple. $2024=17\times119+1$ : quotient $119$ , reste $1$ . Attention au signe : $-47=6\times(-8)+1$ (le reste reste dans $[0,b[$ , donc $1$ , pas $-5$ ).

B. PGCD, algorithme d'Euclide, PPCM

Le PGCD $\operatorname{pgcd}(a,b)$ est le plus grand diviseur commun. Algorithme d'Euclide : $\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)$ , on itère jusqu'au reste nul.

Exemple. $\operatorname{pgcd}(252,198)$ : $252=198\cdot1+54$ , $198=54\cdot3+36$ , $54=36\cdot1+18$ , $36=18\cdot2+0$ . Donc $\operatorname{pgcd}=18$ .

Le PPCM vérifie la relation fondamentale

\operatorname{pgcd}(a,b)\times\operatorname{ppcm}(a,b)=|ab|.

a

b

sont premiers entre eux lorsque

\operatorname{pgcd}(a,b)=1

Rectangle de trente sur dix-huit decoupe en carres emboites de cotes dix-huit, douze, six et six, chaque carre correspondant a une etape des divisions successives ; le cote du plus petit carre vaut le plus grand commun diviseur des deux dimensions. — L'algorithme d'Euclide **est** un pavage. Découper un rectangle $30\times18$ en carrés aussi grands que possible reproduit exactement les divisions successives : $30=1\times18+12$ , puis $18=1\times12+6$ , puis $12=2\times6+0$ — et le côté du **dernier** carré est le pgcd, ici $6$ . C'est la raison géométrique pour laquelle l'algorithme s'arrête et pour laquelle il rend bien le pgcd. Contrôle : $18^2+12^2+6^2+6^2=540=30\times18$ , le pavage est exact.

C. Nombres premiers & factorisation

Un entier $p\ge2$ est premier s'il n'a pas d'autre diviseur que $1$ et $p$ . Théorème fondamental de l'arithmétique : tout entier $\ge2$ s'écrit de façon unique $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ .

De la factorisation on lit : le nombre de diviseurs $\prod(\alpha_i+1)$ , le PGCD ( $\min$ des exposants), le PPCM ( $\max$ des exposants).

Exemple. $360=2^3\cdot3^2\cdot5$ : $(3{+}1)(2{+}1)(1{+}1)=24$ diviseurs.

D. Théorème de Bézout & théorème de Gauss

Bézout. Si $d=\operatorname{pgcd}(a,b)$ , il existe $u,v\in\mathbb Z$ tels que $au+bv=d$ . Plus précisément, les entiers de la forme $au+bv$ sont exactement les multiples de $d$ ; en particulier $a,b$ premiers entre eux $\iff \exists\,u,v,\ au+bv=1$ . Hors du cas $1$ , la réciproque est fausse : $2\cdot1+4\cdot1=6$ , alors que $\operatorname{pgcd}(2,4)=2$ . Pour conclure $d=\operatorname{pgcd}(a,b)$ d'une égalité $au+bv=d$ , il faut de plus que l'entier $d\geq1$ divise $a$ et $b$ . Les coefficients $(u,v)$ s'obtiennent en remontant l'algorithme d'Euclide.

Théorème de Gauss. Si $a\mid bc$ et $\operatorname{pgcd}(a,b)=1$ , alors $a\mid c$ .

E. Congruences

$a\equiv b\pmod n$ signifie $n\mid(a-b)$ (même reste modulo $n$ ). Les congruences sont compatibles avec $+$ et $\times$ : on peut remplacer chaque entier par son reste avant de calculer.

Exemple. $123\cdot456\pmod 7$ : $123\equiv4$ , $456\equiv1$ , donc $123\cdot456\equiv4\cdot1=4\pmod 7$ .

Critères de divisibilité. $10\equiv1\pmod 9$ $\Longrightarrow$ $n\equiv$ (somme de ses chiffres) $\pmod 9$ . $10\equiv-1\pmod{11}$ $\Longrightarrow$ $n\equiv$ (somme alternée des chiffres, en partant des unités avec le signe $+$ ) $\pmod{11}$ .

Cadran circulaire portant les douze classes de zero a onze regulierement reparties ; une fleche en spirale part de zero, fait un tour complet puis avance de cinq crans pour aboutir a la position cinq, illustrant que dix-sept est congru a cinq modulo douze. — Arithmétique modulaire sur le cercle : les entiers s'enroulent autour d'un cadran à $n=12$ positions ( $\mathbb Z/12\mathbb Z$ ). Réduire modulo $12$ revient à compter le reste après un ou plusieurs tours : $17\equiv5\pmod{12}$ (un tour complet $+5$ ). C'est aussi le groupe cyclique $(\mathbb Z/12\mathbb Z,+)$ , analogue des racines $12$ -ièmes de l'unité.

F. Équations diophantiennes & congruences linéaires

L'équation $ax+by=c$ a des solutions entières $\iff \operatorname{pgcd}(a,b)\mid c$ . On trouve une solution particulière par Bézout, puis la solution générale $x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$ .

Une congruence linéaire $ax\equiv b\pmod n$ se résout, lorsque $\operatorname{pgcd}(a,n)=1$ , en multipliant par l'inverse de $a$ modulo $n$ .