# Arithmétique/Divisibilité et congruences dans Z

Soient $a$, $b$ et $c$ trois entiers (relatifs).

## Multiples d’un entier relatif, divisibilité dans Z

On dit que
    « a est un multiple de b », ou que « b est un diviseur de a », ou encore que « b divise a »,
et l’on note
    b | a
si :
    il existe un entier q tel que a = b×q.
* 3 divise –12, car –12 = 3×(–4).
* $\forall n\in \mathbb {Z} \quad (n+1)\mid (n^{2}-1)$, car $n^{2}-1=(n-1)(n+1)$ et $n-1\in \mathbb {Z}$.
* a est multiple de 1, a, –1 et –a, car a = 1×a = a×1 = (–1)×(–a) = (–a)×(–1).
* Zéro n'admet qu'un multiple : lui-même, car $\forall q\in \mathbb {Z} \quad 0\times q=0.$
* Zéro est multiple de tout entier, car $\forall b\in \mathbb {Z} \quad 0=b\times 0.$
* Les seuls diviseurs de 1 sont 1 et –1.
$\left(a\mid b{\text{ et }}b\mid a\right)\Leftrightarrow \left(a=b{\text{ ou }}a=-b\right)$.
Si a et b sont égaux ou opposés, on a déjà remarqué que chacun divise l'autre.
Réciproquement, supposons que chacun divise l'autre et montrons qu’ils sont égaux ou opposés.
* S'ils sont tous deux nuls, c’est immédiat.
* Si l'un au moins est non nul, par exemple b non nul, alors : $b\neq 0{\text{ et }}\exists q_{1},q_{2}\in \mathbb {Z} ,b=q_{1}a{\text{ et }}a=q_{2}b$ d'où $b=q_{1}(q_{2}b)=(q_{1}q_{2})b$ donc (en simplifiant par b, qui est non nul) $q_{1}q_{2}=1$. Par conséquent, $q_{2}$ est égal à 1 ou à –1, donc a est égal à b ou à –b.
    $\left(a\mid b{\text{ et }}b\mid c\right)\Rightarrow a\mid c$.
Si $b=aq_{1}$ et $c=bq_{2}$ alors, $c=aq$ pour $q=q_{1}q_{2}$.
Tout diviseur commun à deux entiers $a$ et $b$ est un diviseur de leur somme et, plus généralement, de $au+bv$, quels que soient les entiers $u$ et $v$.
Si $a=nq_{1}$ et $b=nq_{2}$ alors, $au+bv=nq_{1}u+nq_{2}v=n(q_{1}u+q_{2}v)$.

## Division euclidienne

Si $b\neq 0$, il existe un unique couple d'entiers $(q,r)$, tel que :
* le « dividende » $a$ soit égal au produit du « diviseur » $b$ par le « quotient » $q$ plus le « reste » $r$ et
* le reste soit positif et strictement inférieur à la valeur absolue du diviseur.
Formellement, cette définition s'écrit :
    $\forall (a,b)\in \mathbb {Z} \times {\mathbb {Z} }^{*}\quad \exists !(q,r)\in \mathbb {Z} \times \mathbb {Z} \quad {\begin{cases}a=b\times q+r\\0\leq r<|b|.\end{cases}}$
Deux entiers $q$ et $r$ vérifient ces deux conditions si et seulement si :
* $r=a-bq$ ;
* $0\leq a-bq<|b|$.
La condition 1 détermine $r$ en fonction de $q$, et en posant $q={\tfrac {|b|}{b}}q'$ (c'est-à-dire $q=\pm q'$, selon le signe de $b$), la condition 2 devient :
    ${\begin{aligned}0\leq a-bq<|b|&\Leftrightarrow 0\leq a-|b|q'<|b|\\&\Leftrightarrow |b|q'\leq a<|b|(q'+1)\\&\Leftrightarrow q'{\text{ est}}\end{aligned}}$
                   le plus grand élément de l'ensemble $E:=\{k\in \mathbb {Z} \mid |b|k\leq a\}$.
Un tel entier $q'$ (donc un tel couple $(q,r)$) existe et est unique, car $E$ est un ensemble d'entiers non vide (il contient $-|a|$) et majoré (par $|a|$).
* Si $b>0$ alors $q$ est la partie entière du nombre rationnel ${\frac {a}{b}}$.
* Si de plus $a\geq 0$ alors $q\geq 0$, et l'on retrouve la division euclidienne dans les entiers naturels.
$101=4\times 25+1$ est la division euclidienne de 101 par 4 ou la division euclidienne de 101 par 25.
$34=2\times 10+14$ ne constitue pas la division euclidienne de 34 par 10. En effet, on n'a pas l'inégalité $r<b$.
$-37=-4\times 11+7$ est la division euclidienne de -37 par 11 mais n’est pas la division euclidienne de –37 par –4.

## Congruences

La relation de congruence ne ressemble pas aux relations habituelles, en effet les relations que nous utilisons depuis que nous faisons des mathématiques (=, <, > …) comparent deux nombres alors que la relation de congruence compare les restes des deux nombres étudiés.
Soit $n$ un entier strictement positif.
$a$ et $b$ sont dits congrus modulo $n$ s'ils ont même reste dans la division euclidienne par $n$. Formellement :
$a\equiv b~[n]\Leftrightarrow \exists (q_{1},q_{2},r)\in \mathbb {Z} ^{3}{\begin{cases}a=nq_{1}+r\\b=nq_{2}+r\\0\leq r<n.\end{cases}}$
Les notations changent d’un ouvrage à l'autre mais désignent toutes la même chose :
* $a\equiv b~[n]$ ;
* $a\equiv b~(n)$ ;
* $a\equiv b{\pmod {n}}$ ;
* $a\equiv b~(\operatorname {modulo} n).$
$a$ et $b$ sont congrus modulo $n$ si et seulement si $n$ divise leur différence. Formellement :
$a\equiv b~[n]\Leftrightarrow n\mid (a-b)$
Soient $a=nq_{1}+r_{1}$ et $b=nq_{2}+r_{2}$ les divisions euclidiennes de $a$ et $b$ par $n$. Alors,
$a-b=(nq_{1}+r_{1})-(nq_{2}+r_{2})=n(q_{1}-q_{2})+(r_{1}-r_{2})$
donc (d'après la propriété « Combinaison linéaire » ci-dessus) $n$ divise $a-b$ si et seulement s'il divise $r_{1}-r_{2}$, c'est-à-dire (puisque $|r_{1}-r_{2}|<n$) si et seulement si $r_{1}=r_{2}$.
Quel est le reste de $2^{16}$ dans la division par 7 ?
On a $2^{16}=65536$ et $65536=7\times 9362+2$ Donc $2^{16}\equiv 2~[7].$

### Propriétés des congruences

* $a\equiv b~[n]\Leftrightarrow b\equiv a~[n].$
* Si $a\equiv b~[n]$ et $b\equiv c~[n]$, alors $a\equiv c~[n].$
* Si $a_{1}\equiv a_{2}~[n]$ et $b_{1}\equiv b_{2}~[n]$, alors :
** (1) $a_{1}+b_{1}\equiv a_{2}+b_{2}~[n]$ et plus généralement,
*** $\forall u,v\in \mathbb {Z} ,a_{1}u+b_{1}v\equiv a_{2}u+b_{2}v~[n]$ ;
** (2) $a_{1}b_{1}\equiv a_{2}b_{2}~[n]$ ;
** (3) $\forall p\in \mathbb {N} ^{*},a_{1}^{p}\equiv a_{2}^{p}~[n].$ Attention : $\forall p\in \mathbb {N} ^{*},p^{a_{1}}\equiv p^{a2}~[n]$ n'est pas vrai.
* n divise a – b si et seulement s'il divise son opposé, b – a.
* Si n divise a – b et b – c alors il divise leur somme, a – c.
* Notons respectivement $a$ et $b$ les différences $a_{1}-a_{2}$ et $b_{1}-b_{2}$. Par hypothèse, n divise $a$ et $b$.
(1) Montrons qu’il divise aussi le nombre $(a_{1}u+b_{1}v)-(a_{2}u+b_{2}v)$ (quels que soient les entiers u et v). Ce nombre est égal à $(a_{1}-a_{2})u+(b_{1}-b_{2})v=au+bv$, donc la propriété « Combinaison linéaire » ci-dessus permet de conclure.
(2) Montrons maintenant qu’il divise le nombre $a_{1}b_{1}-a_{2}b_{2}$. Ce nombre est égal à $a_{1}b_{1}-a_{2}b_{1}+a_{2}b_{1}-a_{2}b_{2}=(a_{1}-a_{2})b_{1}+a_{2}(b_{1}-b_{2})=ab_{1}+ba_{2}$ donc, à nouveau, la propriété « Combinaison linéaire » permet de conclure.
(3) se démontre par récurrence, en appliquant (2) à $b_{1}=a_{1}^{p}$ et $b_{2}=a_{2}^{p}$. On peut aussi montrer directement que n divise $a_{1}^{p}-a_{2}^{p}$, en utilisant l'identité remarquable suivante :
    $x^{p}-y^{p}=(x-y)(x^{p-1}+x^{p-2}y+...+x^{p-k}y^{k-1}+...+y^{p-1})$
pour $x$ et $y$ quelconques et $p\in \mathbb {N} ^{*}.$
Il suffit pour démontrer celle-ci de développer le membre de droite ; après simplification, on obtient bien le membre de gauche de l'égalité.
Cette égalité prouve que $a_{1}^{p}-a_{2}^{p}$ est multiple de $a_{1}-a_{2}$, qui est lui-même multiple de n par hypothèse. La propriété « Transitivité » ci-dessus permet de conclure.
Méthode plus simple pour calculer le reste de la division de 2$^{16}$ par 7 :
On remarque que $2^{3}=8\equiv 1~[7]$ et que $16=3\times 5+1.$
Donc modulo 7, $2^{16}=2^{3\times 5+1}=(2^{3})^{5}\times 2\equiv 1^{5}\times 2=2.$
Le reste de la division de 2$^{16}$ par 7 est donc égal à celui de la division de 2 par 7, c'est-à-dire à 2.
| Sommaire | PGCD |