Rejoignez la communauté !
Co-construisez les ressources dont vous avez besoin et partagez votre expertise pédagogique.
Nombres complexes
Ch. 1
Nombres complexes, point de vue algébrique
Ch. 2
Nombres complexes, point de vue géométrique
Arithmétique
Ch. 3
Divisibilité dans Z
Ch. 4
PGCD et applications
Ch. 5
Nombres premiers
Graphes et matrices
Ch. 6
Calcul matriciel et applications aux graphes
Ch. 7
Suites et matrices
Annexes
Cahier d'algorithmique et de programmation
Chapitre 4
Cours 3
Théorème de Gauss et applications
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
AThéorème de Gauss
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Théorème
Soient a, b et c trois entiers relatifs non nuls.
Si a | b c et si a et b sont premiers entre eux, alors a | c.
Si a | b c et si a et b sont premiers entre eux, alors a | c.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
La condition a et b premiers entre eux est essentielle.
Par exemple, 4 divise le produit 2 \times 6=12 mais 4 ne divise ni 2 ni 6.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Démonstration
Supposons que a divise bc et que a et b sont premiers entre eux.
Alors \operatorname{PGCD}(a \:; b)=1 donc d'après le théorème de Bézout, il existe (u \:; v) \in \mathbb{Z}^{2} tel que au + bv = 1.
On a donc a u c+b v c=c. Or a | bc par hypothèse et a | auc donc a |(a u c+b v c).
Ainsi, a | c.
Alors \operatorname{PGCD}(a \:; b)=1 donc d'après le théorème de Bézout, il existe (u \:; v) \in \mathbb{Z}^{2} tel que au + bv = 1.
On a donc a u c+b v c=c. Or a | bc par hypothèse et a | auc donc a |(a u c+b v c).
Ainsi, a | c.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Exemple
Soit n un diviseur impair de 210=105 \times 2. Comme n est premier avec 2 (car n est impair), le théorème de Gauss permet d'affirmer que n divise 105.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Application et méthode - 7
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Énoncé
1. Déterminer le \text{PGCD} de 65 et \text{91}.
2. Résoudre dans \mathbb{Z}^{2} l'équation 65 \mathrm{X}=91 \mathrm{Y}.
2. Résoudre dans \mathbb{Z}^{2} l'équation 65 \mathrm{X}=91 \mathrm{Y}.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
1. On applique l'algorithme d'Euclide : le dernier
reste non nul est le \text{PGCD} cherché.
2. On simplifie l'équation par le \text{PGCD} pour obtenir deux nombres premiers entre eux et on utilise alors le théorème de Gauss pour obtenir une expression de \text{X} et \text{Y}.
On vérifie que le couple obtenu est bien solution de l'équation.
2. On simplifie l'équation par le \text{PGCD} pour obtenir deux nombres premiers entre eux et on utilise alors le théorème de Gauss pour obtenir une expression de \text{X} et \text{Y}.
On vérifie que le couple obtenu est bien solution de l'équation.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Solution
1. On applique l'algorithme d'Euclide : 91=65 \times 1+26 ;
65=26 \times 2+13 et 26=13 \times 2+0 donc \operatorname{PGCD}(91 \:; 65)=13.
2. En divisant par 13 on obtient 65 \mathrm{X}=91 \mathrm{Y} \Leftrightarrow 5 \mathrm{X}=7 \mathrm{Y}.
Or 5 \mathrm{X}=7 \mathrm{Y} \Rightarrow 7 | 5 \mathrm{X}, et 5 et 7 sont premiers entre eux donc, d'après le théorème de Gauss, 7|5 \mathrm{X} \Rightarrow 7| \mathrm{X}.
Ainsi, si (\mathrm{X}\:; \mathrm{Y}) est solution de \left(\mathrm{E}_{0}\right), alors il existe k \in \mathbb{Z} tel que \mathrm{X} = 7k. Donc, si 5 \mathrm{X}=7 \mathrm{Y}, on a 5 \times 7 k=7 \times \mathrm{Y}, d'où \mathrm{Y}=5 k.
Réciproquement, on vérifie que, pour tout k \in \mathbb{Z}, (7 k\:; 5 k) est un couple solution : 65 \times 7 k=455 k et 91 \times 5 k=455 k.
Donc, pour tout entier k, (7 k\:; 5 k) est un couple solution.
Finalement, l'ensemble des solutions de \left(\mathrm{E}_{0}\right) est \{(7 k\:; 5 k), k \in \mathbb{Z}\}.
65=26 \times 2+13 et 26=13 \times 2+0 donc \operatorname{PGCD}(91 \:; 65)=13.
2. En divisant par 13 on obtient 65 \mathrm{X}=91 \mathrm{Y} \Leftrightarrow 5 \mathrm{X}=7 \mathrm{Y}.
Or 5 \mathrm{X}=7 \mathrm{Y} \Rightarrow 7 | 5 \mathrm{X}, et 5 et 7 sont premiers entre eux donc, d'après le théorème de Gauss, 7|5 \mathrm{X} \Rightarrow 7| \mathrm{X}.
Ainsi, si (\mathrm{X}\:; \mathrm{Y}) est solution de \left(\mathrm{E}_{0}\right), alors il existe k \in \mathbb{Z} tel que \mathrm{X} = 7k. Donc, si 5 \mathrm{X}=7 \mathrm{Y}, on a 5 \times 7 k=7 \times \mathrm{Y}, d'où \mathrm{Y}=5 k.
Réciproquement, on vérifie que, pour tout k \in \mathbb{Z}, (7 k\:; 5 k) est un couple solution : 65 \times 7 k=455 k et 91 \times 5 k=455 k.
Donc, pour tout entier k, (7 k\:; 5 k) est un couple solution.
Finalement, l'ensemble des solutions de \left(\mathrm{E}_{0}\right) est \{(7 k\:; 5 k), k \in \mathbb{Z}\}.
Pour s'entraîner
Exercices et p. 133.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
BCorollaire du théorème de Gauss
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Corollaire
Soient a, b et c trois entiers relatifs non nuls.
Si b et c sont premiers entre eux et divisent tous les deux a, alors bc divise a.
Si b et c sont premiers entre eux et divisent tous les deux a, alors bc divise a.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Comme pour le théorème de Gauss, la condition b et c sont premiers entre eux est primordiale. Par exemple, 15 divise 45 et 9 divise 45, mais 9 \times 15=135 ne divise pas 45.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Démonstration
Soient b et c deux diviseurs de a premiers entre eux et b' et c' les entiers tels que bb' = a et cc' = a.
Alors bb' = cc', donc b | cc'.
Comme b et c sont premiers entre eux, alors, d'après le théorème de Gauss, b divise c'.
Soit alors m l'entier tel que c' = bm. On a donc a = cc' = cbm. D'où bc divise a.
Alors bb' = cc', donc b | cc'.
Comme b et c sont premiers entre eux, alors, d'après le théorème de Gauss, b divise c'.
Soit alors m l'entier tel que c' = bm. On a donc a = cc' = cbm. D'où bc divise a.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Exemple
Soit n \in \mathbb{N}. n\left(n^{2}-1\right)=n(n-1)(n+1)=(n-1) n(n+1) est le produit de 3 entiers consécutifs, donc n\left(n^{2}-1\right) est divisible par 2 et par 3.
Comme 2 et 3 sont premiers entre eux, alors le corollaire de Gauss énoncé ci-dessus affirme que n\left(n^{2}-1\right) est divisible par 6.
Comme 2 et 3 sont premiers entre eux, alors le corollaire de Gauss énoncé ci-dessus affirme que n\left(n^{2}-1\right) est divisible par 6.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Application et méthode - 8
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Énoncé
Montrer que, pour tout entier naturel n, 5 n^{2}\left(n^{2}+11\right) est un multiple de 30.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Il faut montrer que, pour tout entier naturel n, 5 n^{2}\left(n^{2}+11\right) est un multiple de 6 et de 5.
On utilise une table de congruence modulo 6.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Solution
Pour tout n \in \mathbb{N}, 5n^2 (n^2 + 11) est un multiple de 5. Écrivons la table de congruence par 6.
Finalement, pour tout entier naturel n, 5 n^{2}\left(n^{2}+11\right) est un multiple de 6.
Or, c'est aussi un multiple de 5.
Comme 5 et 6 sont premiers entre eux, le corollaire du théorème de Gauss ci-dessus donne que 5 n^{2}\left(n^{2}+11\right) un multiple de 30.
| Reste de \boldsymbol{n} (mod \bold{6}) | 0 | 1 | 2 | 3 | 4 | 5 |
| Reste de \boldsymbol{n^2} (mod \bold{6}) | 0 | 1 | 4 | 3 | 4 | 1 |
| Reste de \boldsymbol{n^2+11} (mod \bold{6}) | 5 | 0 | 3 | 2 | 3 | 0 |
| Reste de \boldsymbol{5n^2(n^2+11)} (mod \bold{6}) | 0 | 0 | 60 \equiv 0 | 30 \equiv 0 | 60 \equiv 0 | 0 |
Finalement, pour tout entier naturel n, 5 n^{2}\left(n^{2}+11\right) est un multiple de 6.
Or, c'est aussi un multiple de 5.
Comme 5 et 6 sont premiers entre eux, le corollaire du théorème de Gauss ci-dessus donne que 5 n^{2}\left(n^{2}+11\right) un multiple de 30.
Pour s'entraîner
Exercices et p. 133.
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.
Oups, une coquille
j'ai une idée !
Nous préparons votre pageNous vous offrons 5 essais
YolèneÉmilieJean-PaulFatimaSarah