Divisibilité et congruences : cours de maths · Terminale expertes

Divisibilité dans les entiers

Pour $a,b\in\mathbb Z$, $a\mid b$ signifie qu'il existe $k\in\mathbb Z$ tel que $b=ak$. Changer les signes ne change pas la divisibilité. Tout entier divise $0$ ; $0$ ne divise que $0$.

Si $b\ne0$, ses diviseurs sont non nuls, en nombre fini, et vérifient $|a|\leq|b|$. Préciser si l'on cherche les diviseurs positifs ou tous les diviseurs relatifs.

Si $a\mid b$ et $b\mid c$, alors $a\mid c$. Si $a\mid b$ et $a\mid c$, alors $a\mid(mb+pc)$ pour tous $m,p\in\mathbb Z$.

Pour $42=1\times42=2\times21=3\times14=6\times7$, les diviseurs positifs sont $1,2,3,6,7,14,21,42$ ; les relatifs comprennent aussi leurs opposés.

Division euclidienne

Pour $a\in\mathbb Z$ et $n\geq1$ entier, il existe un unique couple d'entiers $(q,r)$ tel que :

a=nq+r,\qquad0\leq r<n.

$q$ est le quotient et $r$ le reste. Le quotient peut être négatif ; le reste ne l'est jamais. Par exemple, $-53=7\times(-8)+3$, donc le reste est $3$.

Le dividende -53 se situe entre les multiples consécutifs -56 et -49 ; sa distance au multiple inférieur -56 vaut 3, qui est le reste normalisé.

$n\mid a$ si et seulement si $r=0$. Les restes possibles $0,\ldots,n-1$ donnent les formes $nq,nq+1,\ldots,nq+n-1$.

Congruences et opérations

Pour $a,b\in\mathbb Z$ et un même module $n\geq1$, $a\equiv b\pmod n$ signifie $n\mid(a-b)$, ou que $a,b$ ont le même reste euclidien. Une congruence n'est pas une égalité : $53\equiv-3\equiv4\pmod7$, mais le reste est $4$.

On peut enchaîner les congruences. Si $a\equiv b\pmod n$ et $c\equiv d\pmod n$, alors :

a+c\equiv b+d,\qquad a-c\equiv b-d,\qquad ac\equiv bd\pmod n.

Pour $p\geq1$ entier, $a^p\equiv b^p\pmod n$. Choisir un représentant simple aide à calculer une puissance : $23\equiv-1\pmod8$, puis utiliser la parité de l'exposant. Ramener le résultat entre $0$ et $n-1$.

Un entier naturel est divisible par $3$ ou $9$ si et seulement si la somme de ses chiffres l'est. Pour un entier négatif, appliquer le test à sa valeur absolue.

Comprendre pourquoi — Pourquoi les tests par 3 et 9 utilisent les chiffres

En base dix, $N=\sum c_k10^k$. Puisque $10\equiv1$ modulo $3$ et modulo $9$, $N\equiv\sum c_k$ pour chacun de ces modules. Le nombre et sa somme de chiffres ont un reste nul simultanément. Pour un entier négatif, appliquer le test à sa valeur absolue.

Résoudre une congruence

Pour résoudre $ax\equiv b\pmod n$ avec $a,b\in\mathbb Z$, $n\geq1$, tester les restes $r=0,\ldots,n-1$. Chaque reste qui convient donne tous les $x=r+nk$, $k\in\mathbb Z$. Il peut y avoir aucun, un ou plusieurs restes solutions. Modulo $1$, tout entier convient.

Par exemple, $6x\equiv3\pmod9$ admet les restes $2,5,8$. Les solutions sont $x=2+9k$, $5+9k$ ou $8+9k$ ; elles se regroupent en $x=2+3k$, $k\in\mathbb Z$.

Utiliser un inverse modulaire

Un inverse de $a$ modulo $n\geq1$ est un entier $u$ tel que $au\equiv1\pmod n$. Il faut que $a,n$ soient premiers entre eux, c'est-à-dire que leur seul diviseur positif commun soit $1$. Pour un petit module $n\geq2$, on peut tester les restes pour trouver $u$. Tous les inverses sont congrus entre eux.

ax\equiv b\pmod n\quad\Longleftrightarrow\quad x\equiv ub\pmod n\qquad\text{si }au\equiv1\pmod n.

Ne pas diviser une congruence par un facteur quelconque : $2\times1\equiv2\times4\pmod6$, alors que $1\not\equiv4\pmod6$. Utiliser seulement un inverse vérifié.

Comprendre pourquoi — Pourquoi on peut multiplier par un inverse

À partir de $au\equiv1\ [n]$, multiplier $ax\equiv b$ par $u$ donne $x\equiv ub$. Réciproquement, multiplier $x\equiv ub$ par $a$ redonne $ax\equiv b$. Si $u$ et $v$ sont deux inverses, $u\equiv uav\equiv v\ [n]$ : ils ont le même reste, sans être nécessairement le même entier.