Démontrer une divisibilité à l’aide de combinaisons linéaires
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
Pour démontrer qu'un entier $c$ divise un entier $N$, on cherche à exprimer $N$ comme une combinaison linéaire d'entiers dont $c$ est un diviseur commun, en utilisant la propriété :
- Étape 1 : identifier deux multiples de $c$ visibles ou faciles à obtenir à partir de l'énoncé.
- Étape 2 : écrire $N$ comme combinaison linéaire de ces deux multiples : $N = au + bv$.
- Étape 3 : appliquer la propriété de combinaison linéaire pour conclure.
Divisibilité d'une combinaison
Soient $n$ un entier relatif. On suppose que $7$ divise $3n + 2$ et $7$ divise $5n + 4$.
Démontrer que $7$ divise $n$.
Étape 1 : on dispose de deux multiples de $7$ : $A = 3n + 2$ et $B = 5n + 4$.
Étape 2 : on cherche à éliminer le terme constant. On calcule :
Étape 3 : $7$ divise $A$ et $7$ divise $B$, donc $7$ divise toute combinaison linéaire de $A$ et $B$.
En particulier, $7$ divise $\color{red}{2A - B}\color{black} = n$.
Conclusion : $7$ divise $\mathbf{n}$.
Diviseurs communs de deux entiers
Soit $n$ un entier naturel. Démontrer que tout diviseur commun à $n + 3$ et $2n + 1$ divise $5$.
Étape 1 : soit $d$ un diviseur commun à $A = n + 3$ et $B = 2n + 1$.
Étape 2 : on élimine la variable $n$ par combinaison linéaire :
Étape 3 : $d$ divise $A$ et $d$ divise $B$, donc $d$ divise $2A - B = 5$.
Conclusion : tout diviseur commun à $n + 3$ et $2n + 1$ divise $\mathbf{5}$. Les diviseurs communs possibles sont donc $1$, $-1$, $5$ et $-5$.
Remarque
Cette méthode est très utile pour étudier les diviseurs communs de deux entiers (préparation au calcul du PGCD) ou pour démontrer qu'un nombre donné divise une expression dépendant d'un paramètre.
L'idée centrale est de combiner astucieusement les multiples connus pour faire apparaître exactement l'expression visée.
Attention
La propriété ne fonctionne que si les coefficients $u$ et $v$ sont des entiers relatifs. Diviser une combinaison linéaire (par exemple par $2$) peut faire perdre la propriété de divisibilité par $c$.
Par exemple : $4$ divise $8$ et $4$ divise $12$, donc $4$ divise $8 + 12 = 20$. En revanche, $4$ ne divise pas forcément $\dfrac{8 + 12}{2} = 10$.