Arithmétique/Divisibilité et congruences dans Z

Une page de Wikiversité.

**Divisibilité et congruences dans Z**
Leçon : Arithmétique

Chapitre 1
Retour au	sommaire
Chap. suiv. :	PGCD

En raison de limitations techniques, la typographie souhaitable du titre, « Arithmétique : Divisibilité et congruences dans Z
Arithmétique/Divisibilité et congruences dans Z », n'a pu être restituée correctement ci-dessus.

Sommaire

1 Multiples d'un entier relatif
2 Divisibilité dans Z
3 Division euclidienne
4 Congruences
- 4.1 Propriétés des congruences

[modifier] Multiples d'un entier relatif

Définition

L'entier relatif $a\,$ est un multiple de l'entier relatif $b\,$ si et seulement si $\exists q \in \mathbb{Z}^*, a = bq$ .

Remarques :

Tout entier relatif est multiple de $1\,$ et de $-1\,$
$0\,$ n'admet qu'un multiple : lui-même
$0\,$ est multiple de tout entier

[modifier] Divisibilité dans Z

Définition

$a\,$ et $b\,$ désignent 2 entiers relatifs.
Dire que $b\,$ divise $a\,$ signifie qu'il existe un entier relatif $c\,$ tel que $a = bc\,$ .

Vocabulaire : « b divise a » $\Leftrightarrow$ « b est un diviseur de a » $\Leftrightarrow$ « a est un multiple de b ».

Notation : « b divise a » $\Leftrightarrow$ $b|a\,$

Exemples :

17 divise -153 car $-153 = 17\times(-9)$
$\forall n \in \mathbb{Z}, (n+1)|(n^2-1)$

Démonstration

$(n-1) \in \mathbb{Z}$ et $n^2-1 = (n-1)(n+1)\,$

Propriété

Soient $(a,b,c) \in \mathbb{Z}^{*3}$

$\begin{align} a|a \\ 1|a \\ -1|a \\ -a|a \end{align}$
$a|b\,$ et $b|a \Leftrightarrow a = b$ ou $a = -b\,$

Démonstration

$a|b \Leftrightarrow \exists q_1 \in \mathbb{Z}^*, b = q_1a$
$b|a \Leftrightarrow \exists q_2 \in \mathbb{Z}^*, a = q_2b$
d'où $b = q_1(q_2b) \Leftrightarrow b(1-q_1q_2) = 0 \Rightarrow 1-q_1q_2 = 0 \Rightarrow q_1q_2 = 1$
d'où $q_1\,$ et $q_2\,$ sont des diviseurs de 1 $\Rightarrow q_1 \in \left \{ -1;1 \right \}, q_2 \in \left \{ -1;1 \right \}$

Propriété

transitivité $\forall (a,b,c) \in \mathbb{Z}^{*3}$

Si $a|b\,$ et $b|c\,$ , alors $a|c\,$ .

Démonstration

$a|b \Leftrightarrow b = aq_1$ avec $q_1 \in \mathbb{Z}^*$
$b|c \Leftrightarrow c = bq_2$ avec $q_2 \in \mathbb{Z}^*$
$\Rightarrow c = aq_1q_2 \Rightarrow a|c$

Propriété

combinaison linéaire $\forall (a,b) \in \mathbb{Z}^2$ et $\forall q \in \mathbb{Z}^*$

Si $q|a\,$ et $q|b\,$ alors

$q|(a+b)\,$
$q|(a-b)\,$
plus généralement, $\forall (m,n) \in \mathbb{Z}^2, q|(ma+nb)$ .

[modifier] Division euclidienne

Définition

Pour tout dividende « a » entier relatif et diviseur « b » entier relatif non nul, il existe un unique quotient « q » et un unique reste « r » tels que le dividende soit égal à la multiplication du diviseur par le quotient plus le reste avec le reste positif et strictement inférieur à la valeur absolue du diviseur.

En langage mathématiques, cette définition est $\forall (a,b) \in (\mathbb{Z} \times {\mathbb{Z}}^*), \exists !(q,r) \in (\mathbb{Z} \times \mathbb{N})$ tels que $\begin{cases} a = b \times q + r \\ 0 \le r < |b| \end{cases}$

Démonstration de l'unicité du couple (q, r)

Soient $(q,r),~(q',r')$ dans $\mathbb{Z}^2$ tels que : $\begin{cases} a = b \times q + r \\ 0 \le r < b \end{cases}$ et $~\begin{cases} a = b \times q' + r' \\ 0 \le r' < b \end{cases}$
Alors $b \times (q - q') = r' - r$ ,
et $~-b < r' - r < b$ ,
d'où $~-1 < q - q' < 1$ ,
et donc $~q' = q$ , $~r' = r$

Division euclidienne

$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 traduit pas la division euclidienne de 34 par 10. En effet, on a pas l'inégalité $0 \le r < b$ .

[modifier] 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.

Définition

Deux entiers relatifs sont congrus modulo n (avec n un entier naturel) si et seulement s'ils ont même reste dans la division euclidienne par n.

En langage mathématique, $\text{Pour }n \in \mathbb{N},\text{ pour }(a,b) \in \mathbb{Z}^2, \exists (q_1, q_2, r) \in \mathbb{N}^3, a \equiv b [n] \Leftrightarrow \begin{cases} b = n \times q_1 + r \\ a = n \times q_2 + r \\ 0 \le r < n \end{cases}$

Les notations changent d'un professeur à l'autre mais elles désignent toutes la même chose:

$a \equiv b [n]$
$a \equiv b (n)$
$a \equiv b (\text{mod n})$
$a \equiv b (\text{modulo n})$

Il existe une seconde définition qui est parfois utilisée.

Définition

Deux entiers relatifs sont congrus modulo n (avec n un entier naturel) si et seulement si n divise la différence de ces deux nombres.

En langage mathématique, $\text{Pour }n \in \mathbb{N},\text{ pour }(a,b) \in \mathbb{Z}^2, a \equiv b [n] \Leftrightarrow n |(a-b)$

De la même manière, comme il a été précisé dans le paragraphe Divisibilité dans Z, on peut tout autant dire:

n divise a-b
a-b est multiple de n

Démonstration de la seconde définition

$\forall (r,n) \in (\mathbb{N\times N^*}), \forall (q_1,q_2) \in \mathbb{Z}^2$

On sait que $a \equiv b [n] \Leftrightarrow \begin{cases} b = n \times q_1 + r \\ a = n \times q_2 + r \\ 0 \le r < n \end{cases}$ .

On a $a - b = n (q_1 - q_2) + r - r = n (q_1 - q_2)\,$ et $q_1 - q_2\,$ est un entier car les quotients sont des entiers, donc a - b est un multiple de n.

On peut vérifier que r soit bien le même reste pour les deux divisions euclidiennes.

$a - b = k \times n$ (avec $k \in \mathbb{Z}$ ) et $a = n \times q_1 + r$ (avec $0 \le r < n$ ).

On remplace a, $b = a - k \times n = n \times q_1 + r - k \times n = n \times (q_1 - k) + r = n \times q_2 + r$ (avec $0 \le r < n$ ).

r est bien le reste de b dans la division euclidienne par n.

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

[modifier] 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 \equiv b[n]$ et $c \equiv d[n]$ , alors :

(1) $a+c \equiv b+d[n]$
$a-c \equiv b-d[n]$
(2) $ac \equiv bd[n]$
(3) $\forall p \in \mathbb{N}, a^p \equiv b^p[n]$

Démonstration

(1) $a \equiv b [n] \Leftrightarrow a-b=qn$ (avec $q \in \mathbb{Z} )$
$c \equiv d [n] \Leftrightarrow c-d=q'n$ (avec $q' \in \mathbb{Z} )$
En sommant, on obtient :
$a-b+c-d=qn+q'n\,$
$a+c-(b+d)=n(q+q')\,$
Ainsi, $a+c-(b+d)\,$ est divisible par $n\,$ .
Donc $a+c \equiv b+d [n]$
(2) Reprenons les notations du (1) et évaluons $ac-bd\,$ .
$ac-bd=ac-bc+bc-bd\,$
$=(a-b)c+b(c-d)=qnc+q'bn\,$
$=(qc+q'b)n\,$ .
Par conséquent $ac-bd\,$ est divisible par $n \,$ .
Donc $ac \equiv bd [n]$

(3) On utilise l'égalité suivante:
$a^p - b^p=(a-b)(a^{p-1}+a^{p-2}b+ ... +a^{p-k}b^{k-1}+ ... +b^{p-1})\,$ pour $a\,$ et $b\,$ 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é.
Puisque $a \equiv b[n]$ , $a-b \,$ est un multiple de $n\,$ . Le membre de droite de l'égalité ci-dessus est par conséquent un multiple de $n\,$ comme multiple de $a-b\,$ .
On a montré que $a^{p} - b^{p}\,$ est un multiple de $n\,$ .
Donc $a^p \equiv b^p[n]$ .
Autre démonstration. On applique la propriété (2) $p\,$ fois avec $c=a\,$ et $d=b\,$ .

Exemple de congruence

Quel est le reste de la division de $2^{16}\,$ par 7 ?
$2 \equiv 2[7] \Rightarrow 2^3 \equiv 8[7] \Rightarrow 2^3 \equiv 1[7]$
$16 = 3\times 5+1 \Rightarrow 2^{16} = 2^{3\times 5+1} = (2^3)^5 \times 2$
Or $(2^3)^5 \equiv 1^5[7] \Leftrightarrow (2^3)^5 \equiv 1[7]$ et $2 \equiv 2[7]$
En multipliant membre à membre : $(2^3)^5\times 2 \equiv 1\times 2[7] \Leftrightarrow 2^{16} \equiv 2[7]$
Le reste de la division de $2^{16}\,$ par 7 est donc 2.