Divisibilité, division euclidienne et PGCD

Diviseurs de 132. $132$ $=1\times 132$ $=2\times 66$ $=3\times 44$ $=4\times 33$ $=6\times 22$ $=11\times 12$, tandis que $5$, $7$, $8$, $9$ et $10$ ne divisent pas $132$. On s’arrête à $11$, car $12\times 12=144>132$. Les $12$ diviseurs positifs de $132$ sont $1$, $2$, $3$, $4$, $6$, $11$, $12$, $22$, $33$, $44$, $66$ et $132$.

Critères. $7452$ se termine par $2$ : il est pair. $52=4\times 13$ : il est divisible par $4$. $7+4+5+2=18$ : il est divisible par $3$ et par $9$. Il ne se termine ni par $0$ ni par $5$ : il n’est pas divisible par $5$.

Démontrer qu’une expression est un multiple. Deux entiers impairs consécutifs s’écrivent $2k+1$ et $2k+3$ avec $k\in \mathbb{Z}$. Leur somme vaut $4k+4=4(k+1)$, et $k+1$ est un entier : c’est un multiple de $4$.

Disjonction des cas. Montrons que $n^2+n+1$ est impair pour tout entier $n$. Si $n=2k$ : $n^2+n+1$ $=4k^2+2k+1$ $=2(2k^2+k)+1$. Si $n=2k+1$ : $n^2+n+1$ $=(4k^2+4k+1)+(2k+1)+1$ $=2(2k^2+3k+1)+1$. Dans les deux cas, le nombre s’écrit $2K+1$ avec $K$ entier : il est impair.

Avec la définition. $17\mid -391$, car $-391=17\times (-23)$ et $-23\in \mathbb{Z}$. En revanche, $17$ ne divise pas $400$ : $17\times 23=391$ et $17\times 24=408$, donc $400$ est strictement compris entre deux multiples consécutifs de $17$.

Démonstration : combinaisons linéaires. Il existe des entiers $k$ et $k\prime$ tels que $a=kd$ et $b=k\prime d$. Alors $au+bv$ $=kdu+k\prime dv$ $=d(ku+k\prime v)$, et $ku+k\prime v$ est un entier : $d$ divise $au+bv$.

Démonstration : $|b|⩽|a|$. Si $a=kb$ avec $a\ne 0$, alors $k\ne 0$, donc $|k|⩾1$ et $|a|=|k|\times |b|⩾|b|$.

Une équation de divisibilité. Cherchons les entiers relatifs $n$ tels que $n+2$ divise $3n+11$. On écrit $3n+11=3(n+2)+5$. Comme $n+2$ divise $3(n+2)$, il divise $3n+11$ si et seulement s’il divise $5$ (sens direct : par différence ; réciproque : par somme). Les diviseurs de $5$ dans $\mathbb{Z}$ sont $-5$, $-1$, $1$ et $5$, d’où $n+2\in \{-5;-1;1;5\}$ et $n\in \{-7;-3;-1;3\}$. Contrôle pour $n=3$ : $3n+11=20=5\times 4$.

Démonstration du théorème (classique, non exigible). Existence : les multiples de $b$ inférieurs ou égaux à $a$ forment un ensemble non vide (il contient $-|a|\times b$) et majoré par $a$ ; il a donc un plus grand élément $bq$. On pose $r=a-bq$, qui est positif ou nul. Si l’on avait $r⩾b$, le multiple $b(q+1)=bq+b$ serait encore inférieur ou égal à $a$ et plus grand que $bq$ : impossible. Donc $0⩽r<b$. Unicité : si $bq+r=bq\prime +r\prime$ avec $0⩽r<b$ et $0⩽r\prime <b$, alors $b(q-q\prime )=r\prime -r$ : $b$ divise $r\prime -r$, avec $-b<r\prime -r<b$. Le seul multiple de $b$ strictement compris entre $-b$ et $b$ est $0$ : $r=r\prime$, puis $q=q\prime$.

Un dividende positif. $47\times 63=2961$ et $47\times 64=3008>3000$, donc $3000=47\times 63+39$ avec $0⩽39<47$ : quotient $63$, reste $39$.

Un dividende négatif. En changeant les signes, $-3000=47\times (-63)-39$, mais $-39$ n’est pas un reste. On descend d’un multiple de $47$ : $-3000=47\times (-64)+8$, avec $0⩽8<47$. Quotient $-64$, reste $8$ (et $8=47-39$).

Disjonction des cas selon le reste. Montrons que le reste de $n^2$ dans la division par $3$ vaut $0$ ou $1$. Tout entier $n$ s’écrit $3k$, $3k+1$ ou $3k+2$ avec $k\in \mathbb{Z}$. Si $n=3k$ : $n^2=3\times 3k^2$, le reste vaut $0$. Si $n=3k+1$ : $n^2$ $=9k^2+6k+1$ $=3(3k^2+2k)+1$, le reste vaut $1$. Si $n=3k+2$ : $n^2$ $=9k^2+12k+4$ $=3(3k^2+4k+1)+1$, le reste vaut $1$. Le reste $2$ n’apparaît jamais.

Changer de diviseur. Le reste de $N$ dans la division par $60$ vaut $53$ : $N=60q+53$. Comme $60=12\times 5$ et $53=12\times 4+5$, on obtient $N=12(5q+4)+5$ avec $0⩽5<12$ : le reste de $N$ par $12$ vaut $5$.

En Python. 3000 // 47 renvoie $63$ et 3000 % 47 renvoie $39$ ; -3000 // 47 renvoie $-64$ et -3000 % 47 renvoie $8$.

Démonstration de la propriété clé. Soit $d$ un diviseur commun de $a$ et $b$. Il divise la combinaison linéaire $a-bq=r$ : c’est un diviseur commun de $b$ et $r$. Réciproquement, si $d$ divise $b$ et $r$, il divise $bq+r=a$ : c’est un diviseur commun de $a$ et $b$. Les deux couples ont les mêmes diviseurs communs, donc le même plus grand.

Calcul de pgcd(3 542 ; 2 464).

Le dernier reste non nul est $154$ : $\text{pgcd}(3542;2464)=154$. Contrôle : $3542=154\times 23$ et $2464=154\times 16$.

Pourquoi la conséquence est vraie. D’après la propriété clé, les diviseurs communs restent les mêmes d’une ligne à l’autre : ce sont ceux de $3542$ et $2464$, puis de $2464$ et $1078$, …, enfin de $154$ et $0$, c’est-à-dire les diviseurs de $154$. Les diviseurs communs positifs de $3542$ et $2464$ sont donc ceux de $154=2\times 7\times 11$ : $1$, $2$, $7$, $11$, $14$, $22$, $77$ et $154$.

En Python : le couple $(a;b)$ est remplacé par $(b;r)$ tant que $b\ne 0$.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

L’appel pgcd(3542, 2464) renvoie $154$.

Démonstration du facteur commun. On multiplie par $k$ chaque ligne de l’algorithme d’Euclide appliqué à $(a;b)$ : $a=b{q}_1+r_1$ devient $ka=(kb)q_1+k{r}_1$, avec $0⩽k{r}_1<kb$, et ainsi de suite. On obtient exactement l’algorithme d’Euclide appliqué à $(ka;kb)$ : mêmes quotients, restes multipliés par $k$. Son dernier reste non nul est donc $k\times \text{pgcd}(a;b)$.

Démonstration de l’écriture de référence. D’après le facteur commun, $d$ $=\text{pgcd}(da\prime ;db\prime )$ $=d\times \text{pgcd}(a\prime ;b\prime )$ ; comme $d\ne 0$, $\text{pgcd}(a\prime ;b\prime )=1$. La réciproque se lit dans la même égalité : si $\text{pgcd}(a\prime ;b\prime )=1$, alors $\text{pgcd}(a;b)=d\times 1=d$.

Premiers entre eux sans être premiers. $36=1\times 25+11$, $25=2\times 11+3$, $11=3\times 3+2$, $3=1\times 2+1$ et $2=2\times 1+0$ : $\text{pgcd}(25;36)=1$. Les entiers $25$ et $36$ sont premiers entre eux, alors qu’aucun des deux n’est un nombre premier.

Rendre une fraction irréductible. Pour ${\displaystyle \frac{1771}{2737}}$ : $2737=1\times 1771+966$ ; $1771=1\times 966+805$ ; $966=1\times 805+161$ ; $805=5\times 161+0$. Le PGCD vaut $161$, et $1771=161\times 11$, $2737=161\times 17$. Donc ${\displaystyle \frac{1771}{2737}}={\displaystyle \frac{11}{17}}$, fraction irréductible d’après l’écriture de référence.

PGCD et somme imposés. Cherchons les couples $(a;b)$ d’entiers naturels tels que $a⩽b$, $a+b=96$ et $\text{pgcd}(a;b)=12$. On écrit $a=12a\prime$ et $b=12b\prime$ avec $a\prime$ et $b\prime$ premiers entre eux et $a\prime ⩽b\prime$ ; alors $12(a\prime +b\prime )=96$, soit $a\prime +b\prime =8$. Parmi $(1;7)$, $(2;6)$, $(3;5)$ et $(4;4)$, seuls $(1;7)$ et $(3;5)$ sont formés d’entiers premiers entre eux. Les solutions sont $(12;84)$ et $(36;60)$.

Premiers entre eux pour tout $n$. Soit $n\in \mathbb{N}$ et $d$ un diviseur commun de $5n+3$ et $3n+2$. Alors $d$ divise $3(5n+3)-5(3n+2)$ $=15n+9-15n-10$ $=-1$, donc $d=1$ ou $d=-1$ : $5n+3$ et $3n+2$ sont premiers entre eux pour tout $n$. De même, deux entiers consécutifs $n$ et $n+1$ sont premiers entre eux, car tout diviseur commun divise $(n+1)-n=1$.

Un PGCD qui dépend de $n$. Pour $n\in \mathbb{N}$, on pose $A=n+7$ et $B=2n+5$. Un diviseur commun $d$ divise $2A-B=2n+14-2n-5=9$, donc $\text{pgcd}(A;B)\in \{1;3;9\}$. Comme $B=2A-9$, tout diviseur de $9$ qui divise $A$ divise aussi $B$.

• $9$ divise $A=n+7$ si et seulement si $n=9k+2$ ($k\in \mathbb{N}$) : le PGCD vaut alors $9$.
• $3$ divise $A$ sans que $9$ le divise pour $n=9k+5$ et $n=9k+8$ : le PGCD vaut $3$.
• Pour les autres valeurs de $n$, $3$ ne divise pas $A$, donc pas le PGCD : il vaut $1$.

Contrôle : pour $n=2$, $A=B=9$ ; pour $n=5$, $A=12$ et $B=15$, de PGCD $3$ ; pour $n=0$, $A=7$ et $B=5$, de PGCD $1$.