Arithmétique/Divisibilité et congruences dans Z

Début de la boite de navigation du chapitre

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

fin de la boite de navigation du chapitre

Multiples d’un entier relatif, divisibilité dans Z

Définition

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.

Début de l'exemple

Exemples

• 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}$.

Fin de l'exemple

Remarque

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

Éléments associés

$\left(a\mid b{\text{ et }}b\mid a\right)\Leftrightarrow \left(a=b{\text{ ou }}a=-b\right)$.

Démonstration

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.

 

Transitivité

$\left(a\mid b{\text{ et }}b\mid c\right)\Rightarrow a\mid c$.

Démonstration

Si $b=aq_{1}$ et $c=bq_{2}$ alors, $c=aq$ pour $q=q_{1}q_{2}$.

 

Combinaison linéaire

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

Démonstration

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

Définition

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}}$

Démonstration

Deux entiers $q$ et $r$ vérifient ces deux conditions si et seulement si :

1. $r=a-bq$ ;
2. $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|$).

 

Remarques

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

Début de l'exemple

Exemples

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

Fin de l'exemple

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.

Définition

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

Proposition

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

Démonstration

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}$.

 

Début de l'exemple

Exemple de congruence

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].$

Fin de l'exemple

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.

Démonstration

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

 

Début de l'exemple

Exemple de congruence (suite)

Méthode plus simple pour calculer le reste de la division de 2¹⁶ 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¹⁶ par 7 est donc égal à celui de la division de 2 par 7, c'est-à-dire à 2.

Fin de l'exemple