Terminale – Cours – Divisibilité dans Z et congruences

Divisibilité dans $\boldsymbol{Z}$ et congruences

I Divisibilité dans $\boldsymbol{Z}$

Définition 1 : On considère deux entiers relatifs $a$ et $b$.
On dit que $\boldsymbol{a}$ divise $\boldsymbol{b}$ s’il existe un entier relatif $k$ tel que $b=ka$.
On dit alors que $a$ un diviseur de $b$ et que $b$ est un multiple de $a$.

Remarques :

  • Si $a$ divise $b$ on le note $a\mid b$.
  • Si $a$ divise $b$ on dit également que $b$ est divisible par $a$.

Exemples : 

  • $2$ divise $12$
  • $3$ est un diviseur de $15$
  • $20$ est un multiple de $4$
  • $36$ est divisible par $6$
  • $-5$ divise $100$
  • $7$ divise $-56$
Propriété 1 :

  • $1$ et $-1$ divisent tout entier relatif $a$.
  • $0$ est un multiple de tout entier relatif $a$.

Preuve Propriété 1

  • Pour tout entier relatif $a$ on a $a=1\times a$ et $a=(-1)\times (-a)$
    Donc $1$ et $-1$ divisent $a$.
  • Pour tout entier relatif $a$ on a $0\times a=0$.
    Donc $0$ est un multiple de $a$.
    $\quad$

[collapse]

$\quad$

Propriété 2 : On considère deux entiers relatifs $a$ et $b$, tel que $b\neq 0$.
Si $a$ divise $b$ alors $|a|\pp |b|$.
Preuve Propriété 2

$a$ divise $b$. Il existe un entier relatif $k$ tel que $b=ka$. Ainsi $|b|=|k|\times|a|$.
Puisque $b$ est non nul on a $|k|\pg 1$.
En multipliant les deux membres de l’inégalité par $|a|$ on obtient $|a|\times |k|\pg |a|$.
Par conséquent $|b|\pg |a|$.
$\quad$

[collapse]

$\quad$

Propriété 3 (conséquence) : On considère un entier relatif $a$ non nul.
$a$ possède un nombre fini de diviseurs tous compris entre $-|a|$ et $|a|$.
Propriété 3

D’après la propriété précédente, les diviseurs $p$ de $a$ vérifient $|p|\pp |a|$.
Ainsi $-|a| \pp p \pp |a|$.

Il y a exactement $2|a|+1$ entiers relatifs compris entre $-|a|$ et $|a|$.
Ainsi le nombre de diviseurs de $|a|$ est inférieur ou égal à $2|a|+1$. Il est donc fini.
$\quad$

[collapse]

$\quad$

Propriété 4 : On considère un entier relatif $a$.
$a$ et $-a$ ont les mêmes diviseurs.
Preuve Propriété 4

$p$ divise $a$
$\ssi$ il existe un entier relatif $k$ tel que $a=kp$
$\ssi$ il existe un entier relatif $k$ tel que $-a=(-k)p$ $\qquad \left((-k)\in \Z\right)$
$\ssi$ $p$ divise $-a$
$\quad$

[collapse]

$\quad$

Propriété 5 : On considère deux entiers relatifs $a$ et $b$ non nuls.
Si $a$ divise $b$ et si $b$ divise $a$ alors $a=b$ ou $a=-b$.
Preuve Propriété 5

$a$ divise $b$ donc $|a|\pp |b|$
$b$ divise $a$ donc $|b|\pp |a|$
Par conséquent $|a|=|b|$ c’est-à-dire $a=b$ ou $a=-b$.
$\quad$

[collapse]

$\quad$

Propriété 6 (transitivité) : On considère trois entiers relatifs $a$, $b$ et $c$.
Si $a$ divise $b$ et si $b$ divise $c$ alors $a$ divise également $c$.
Preuve Propriété 6

$a$ divise $b$ : il existe donc un entier relatif $k$ tel que $b=ka$
$b$ divise $c$ : il existe donc un entier relatif $k’$ tel que $c=k’b$
Par conséquent :
$\begin{align*} c&=k’b\\
&=k’\times ka\\
&=\left(k’k\right)a\end{align*}$
$k’k$ est un entier relatif donc $a$ divise $c$.
$\quad$

[collapse]

$\quad$

Exemple : $3$ divise $6$ et $6$ divise $48$ donc $3$ divise $48$.

Propriété 7 : On considère trois entiers relatifs $a$, $b$ et $c$ tels que $a$ divise $b$ et $c$.
Pour tous entiers relatifs $m$ et $n$, $a$ divise $mb+nc$.
En particulier $a$ divise $bc$, $b+c$ et $b-c$.
Preuve Propriété 7

$a$ divise $b$ : il existe un entier relatif $k$ tel que $b=ka$
$a$ divise $c$ : il existe un entier relatif $k’$ tel que $c=k’a$.
Pour tous entiers relatifs $m$ et $n$ on a :
$\begin{align*} mb+nc&=m(ka)+n\left(k’a\right) \\
&=\left(mk+nk’\right)a\end{align*}$
$mk+nk’$ est un entier relatif donc $a$ divise $nb+nc$.

Si $m=c$ et $n=0$ alors $a$ divise $bc$
Si $m=1$ et $n=1$ alors $a$ divise $b+c$
Si $m=1$ et $n=-1$ alors $a$ divise $b-c$
$\quad$

[collapse]

$\quad$

Remarque : On dit que $a$ divise toute combinaison linéaire de $b$ et $c$.

Exemple : On considère un entier relatif $k$ non nul. On suppose que, pour tout entier naturel $n$, $k$ divise $3n-7$ et $15-6n$.
$k$ divise donc $2(6n-7)+(15-6n)$.
Or $2(6n-7)+(15-6n)=1$.
Donc $k$ divise $1$.
Par conséquent $k=1$ ou $k=-1$.
$\quad$

$\quad$

II Division euclidienne

Propriété 8 : On considère un entier naturel $b$ non nul. Pour tout entier naturel $a$ il existe un entier naturel $n$ tel que $a<nb$.
On dit que $\N$ est archimédien.
Preuve Propriété 8

$b$ est un entier naturel non nul, donc $b\pg 1$.

  • Si $a=0$ on peut alors prendre $n=1$. On a en effet alors $nb\pg 1$ donc $a<nb$.
  • Si $a=1$ on peut prendre $n=2$. On a en effet alors $nb \pg 2$ donc $a<nb$.
  • Dans tous les autres cas, on peut prendre $n=a+1$.
    $nb=ab+b$. Or $b\pg 1$ donc $ba\pg a$ et par conséquent $ba+b\pg a+1$ soit $ba+b>a$.
    $\quad$

[collapse]

$\quad$

Propriété 9 : Toute partie non vide $\N$ possède un plus petit élément.

Propriété admise

Théorème 1 : On considère un entier relatif $a$ et un entier naturel $b$ non nul.
Il existe un unique couple $(q;r)$ d’entiers relatifs tels que $a=bq+r$ et $0\pp r<b$.
Cette relation est appelée division euclidienne de $a$ par $b$.
On dit que :

  • $r$ est le reste de la division euclienne;
  • $b$ est le diviseur de la division euclidienne;
  • $a$ est le dividende de la division euclidienne.

Preuve Théorème 1

  • Existence
    On suppose dans un premier que $a$ est un entier naturel.
    – Si $a=0$ alors le couple $(q;r)=(0;0)$ convient
    – Si $a \neq 0$. D’après la propriété 8, il existe un entier naturel $n$ tel que $a<nb$.
    L’ensemble $\mathscr{E}$ des entiers naturels $n$ tels que $a<nb$ est donc non vide.
    D’après la propriété 9, il possède un plus petit élément $n_0$.
    $n_0 \neq 0$ car sinon $a<0\times b$ soit $a<0$ ce qui est absurde puisque $a$ est un entier naturel.
    Pour tout entier naturel $n<n_0$ on a également $nb\pp a$.
    C’est en particulier vrai pour $n=n_0-1$.
    Ainsi $\left(n_0-1\right)b\pp a <n_0b$
    On pose $q=n_0-1$
    On a alors $bq\pp a < b(q+1) \ssi 0\pp a-bq<b$.
    On pose $r=a-bq$.
    On a ainsi $a=bq+r$ et $0\pp r<b$.
    $\quad$
    On suppose maintenant que $a<0$.
    Par conséquent $(-a)$ est un entier naturel. Il existe donc un couple $\left(q’;r’\right)$ tel que $-a=q’b+r’$ avec $0\pp r'<b$.
    – si $r’=0$ alors $-a=q’b$ donc $a=-q’b$ et le couple $\left(-q’;0\right)$ convient.
    – si $r’>0$ on a alors $a=-q’b-r’$ $\quad$ (le couple $\left(-q’;-r’\right)$ ne convient pas puisque $-r'<0$).
    Cependant :
    $\begin{align*} a&=-q’b-r’ \\
    &=-q’b{\textcolor{red}{-b+b}}-r’ \\
    &=\left(-q’-1\right)b+\left(b-r’\right)\end{align*}$
    Or $0< r'<b$ donc $-b<r'< 0$ et par conséquent $0<b-r'<b$.
    Le couple $\left(-q’-1;b-r’\right)$ convient.
    $\quad$
  • Unicité
    On suppose qu’il existe deux couples $(q;r)$ et $\left(q’;r’\right)$ tels que :
    – $a=bq+r$ et $0\pp r<b$
    – $a=bq’+r’$ et $0\pp r'<b$
    On a alors $r=a-bq$ et $r’=a-bq’$
    Donc, par différence, $r-r’=b\left(q’-q\right)$
    Cela signifie par conséquent que $b$ divise de $r-r’$.
    Or $-b<r-r'<b$ donc $r-r’=0$ c’est-à-dire $r=r’$.
    L’égalité $r-r’=b\left(q’-q\right)$ nous donne alors $b\left(q’-q\right)=0$.
    Par hypothèse, $b$ est un entier naturel non nul. Donc $q’-q=0$ c’est-à-dire $q’=q$.
    Le couple $(q;r)$ est par conséquent unique.
    $\quad$

[collapse]

$\quad$

Exemples : 

  • $75=4\times 18+3$ : $3$ est le reste de la division euclidienne de $75$ par $4$ et $18$ est son quotient.
  • $-75=-4\times 18-3$ : le reste ne peut pas être négatif.
    $-75=-4\times 18-4+4-3$ c’est-à-dire $-75=4\times (-19)+1$ : $1$ est le reste de la division euclidienne de $-75$ par $4$ et $-19$ est son quotient.
    $\quad$

III Congruences

Définition 2 : On considère deux entiers relatifs $a$ et $b$ et n entier naturel $n$ non nul.
On dit que $\boldsymbol{a}$ est congru à $\boldsymbol{b}$ modulo $\boldsymbol{n}$ si $a$ et $b$ possède le même reste dans la division euclidienne par $n$.
On note $a\equiv b$ mod $n$ ou $a\equiv b ~[n]$ ou $a\equiv b~(n)$.

Remarque : On dit également que $a$ et $b$ sont congrus modulo $n$.

Exemples :

  • $17=3\times 5 +2$ et $42=8\times 5+2$. Donc $17\equiv 42~[5]$.
  • Tous les nombres pairs sont congrus à $0$ modulo $2$.
  • Tous les nombres impairs sont congrus à $1$ modulo $2$.
Propriété 10 (symétrie) : On considère deux entiers relatifs $a$ et $b$ et un entier naturel $n$ non nul.
Si $a\equiv b~[n]$ alors $b\equiv a~[n]$.
Propriété 11 (réflexivité) : On considère un entier relatif $a$ et un entier naturel $n$ non nul.
On a $a\equiv a~[n]$.

Ces deux propriétés découlent  directement de la définition.

Propriété 12 : On considère deux entiers relatifs $a$ et $b$ et un entier naturel $n$ non nul.
$a\equiv ~[n]$ si, et seulement si, $n$ divise $a-b$.
Preuve Propriété 12

Si $a\equiv b~[n]$ il existe alors deux entiers relatifs $q$ et $q’$ et un entier naturel $r$ tels que $a=qn+r$, $b=q’n+r$ avec $0\pp r<n$.
On a alors $a-b=\left(q-q’\right)n$.
Donc $n$ divise $a-b$.

Réciproquement, si $n$ divise $a-b$.
Il existe deux entiers relatifs $q$ et $q’$ et deux entiers naturels $r$ et $r’$ tels que $a=nq+r$ et $b=nq’+r’$ avec $0\pp r<n$ et $0\pp r'<n$.
On a alors $a-b=n(q-q’)+r-r’$.
Par conséquent $r-r’=a-b-\left(q-q’\right)n$
$n$ divise $a-b$ et $\left(q-q’\right)n$. Donc $n$ divise la combinaison linéaire $a-b-\left(q-q’\right)n$, c’est-à-dire $r-r’$.
Or $-n<r-r'<n$ donc $r-r’=0$, c’est-à-dire $r=r’$.
Par conséquent $a\equiv b~[n]$.
$\quad$

[collapse]

$\quad$

Remarque : On a en particulier $a\equiv 0~[n]$ si, et seulement si, $n$ divise $a$.

Propriété 13 (transitivité) : On considère trois entiers relatifs $a$, $b$ et $c$ et un entier naturel $n$ non nul.
Si $a\equiv b ~[n]$ et $b\equiv c~[n]$ alors $a\equiv c~[n]$.
Preuve Propriété 13

$a\equiv b~[n]$ donc $a$ et $b$ ont le même reste $r$ dans la division euclidienne par $n$.
$b\equiv c~[n]$ donc $b$ et $c$ ont le même reste $r’$ dans la division euclidienne par $n$.
Par unicité du reste on a $r=r’$.
Par conséquent $a$ et $c$ ont le même reste $r$ dans la division euclidienne par $n$, c’est-à-dire $a\equiv c~[n]$.
$\quad$

[collapse]

$\quad$

Exemple : $50\equiv 1~[7]$ et $71\equiv 1~[7]$ donc $50\equiv 71~[7]$.

Propriété 14 (opérations) : On considère quatre entiers relatifs $a$, $b$, $c$ et $d$ et un entier naturel $n$ non nul.

  1. Si $a\equiv b~[n]$ et $c\equiv d~[n]$ alors $a+c\equiv b+d~[n]$.
  2. Si $a\equiv b~[n]$ alors $ac\equiv bc~[n]$.
  3. Si $a\equiv b~[n]$ et $c\equiv d~[n]$ alors $ac\equiv bd~[n]$.
  4. Si $a\equiv b~[n]$ alors, pour tout entier naturel $k$ tel que $(a;k)\neq (0;0)$ et $(b;k)\neq (0;0)$, on a $a^k\equiv b^k~[n]$.

Preuve Propriété 14

  1. $a\equiv b~[n]$ et $c\equiv d~[n]$ donc $n$ divise à la fois $a-b$ et $c-d$.
    $n$ divise donc la combinaison linéaires $(a-b)+(c-d)$, c’est-à-dire $a+c-(b+d)$.
    Donc $a+c\equiv b+d~[n]$.
  2. $a\equiv b~[n]$ donc $n$ divise $a-b$.
    Par conséquent $n$ divise $c(a-b)$, c’est-à-dire $ca-cb$.
    Donc $ca\equiv cb~[n]$.
  3. $a\equiv b~[n]$ donc $ac\equiv bc~[n]$
    $c\equiv d~[n]$ donc $bc\equiv bd~[n]$
    Par conséquent $ac\equiv bd~[n]$
  4. Démontrons cette propriété par récurrence.
    Initialisation : Si $k=1$ alors $a^k=a$ et $b^k=b$ donc $a^k\equiv b^k~[n]$.
    La propriété est vraie au rang $1$.
    $\quad$
    Hérédité : On suppose la propriété vraie au rang $k$, $k\pg 1$. On a donc $a^k\equiv b^k~[n]$.
    Montrons que la propriété est vraie au rang $k+1$, c’est-à-dire $a^{k+1}\equiv b^{k+1}~[n]$.
    On a $a^k\equiv b^k~[n]$ et $a\equiv b~[n]$
    Par conséquent $a^k\times a\equiv b^k\times b~[n]$, c’est-à-dire $a^{k+1}\equiv b^{k+1}~[n]$.
    La propriété est vraie au rang $k+1$.
    $\quad$
    Conclusion : La propriété est vraie au rang $1$ et est héréditaire.
    Par conséquent, pour tout entier naturel $k$ non nul on a $a^k\equiv b^k~[n]$.
    $\quad$
    Si $a\neq 0$ et $b\neq 0$ alors $a^0=1$ et $b^0=1$ donc $a^0\equiv b^0~[n]$.
    Par conséquent, pour tout entier naturel $k$ tel que $(a;k)\neq (0;0)$ et $(b;k)\neq (0;0)$, on a $a^k\equiv b^k~[n]$.
    $\quad$

[collapse]

$\quad$

Exemple : On veut déterminer à quel nombre $17^{251}$ est congru modulo $[5]$.
On a $17\equiv 2~[5]$ car $17=3\times 5+2$
Par conséquent $17^2\equiv 2^2~[5]$, c’est-à-dire $17^2\equiv 4~[5]$ ou encore $17^2\equiv -1~[5]$ car $4\equiv -1~[5]$.
Or $251=2\times 125+1$
Par conséquent $\left(17^2\right)^{125}\equiv (-1)^{125}~[5]$, c’est-à-dire $17^{250}\equiv -1~[5]$.
Or $17^{251}\equiv 2^{250}\times 2~[5]$.
Ainsi $17^{251}\equiv -1\times 2~[5]$ soit $17^{251} \equiv -2~[5]$ et donc $17^{251}\equiv 3~[5]$.

$\quad$