Nombres premiers entre eux
Définition
Soient a et b deux entiers relatifs non nuls.
a et b sont premiers entre eux signifie que PGCD(a;b)=1.
Exemple
6 et 25 sont premiers entre eux car PGCD(6;25)=1.
Propriété
Soient a et b deux entiers relatifs non nuls.
Si PGCD(a;b)=d, alors il existe deux entiers a' et b' tels que a=da' et b=db' et PGCD(a';b')=1.
Exemple
On a PGCD(12;50)=2. De plus 12=2\times 6 et 50=2\times 25 et PGCD(6;25)=1.
Exercice n°1
Déterminer les diviseurs positifs de 1237 et de -120 et indiquer si 1237 et -120 sont premiers entre eux.
Exercice n°2
Déterminer les diviseurs positifs de 1286 et de 1070 et indiquer si 1286 et 1070 sont premiers entre eux.
Exercice n°3
n désigne un nombre entier naturel tel que n\geq 2.
On pose : a=n^2+2n-3 et b=n^2+4n+3.
- Factoriser a=n^2+2n-3 et b=n^2+4n+3.
2. Déterminer PGCD(n-1;n+1) en distinguant les cas n pair et n impair.
3. Exprimer alors PGCD(a;b) en fonction de n.
Identité de Bezout
Identité de Bezout
Soient a et b deux entiers relatifs non nuls.
Si PGCD(a;b)=d alors il existe deux entiers u et v tels que au+bv=d.
Exemple
- Déterminer PGCD(58;24) à l’aide de la calculatrice.
2. En déduire un couple d’entiers relatifs (x;y) tel que 58x-24y=2.
Comme le PGCD(58;24)=2 alors il existe un couple d’entiers relatifs (x;y) tel que 58x-24y=2.
On écrit l’algorithme d’Euclide en rajoutant une colonne.
On écrit la dernière égalité de la dernière colonne :
2=10-2\times 4
On remplace 4 par 24-2\times 10
2=10-2\times (24-2\times 10)
On développe
2=10-2\times 24+4\times 10
On réduit
2=5\times 10-2\times 24
On remplace 10 par 58-2\times 24
2=5\times (58-2\times 24)-2\times 24
On développe
2=5\times 58-10\times 24-2\times 24
On réduit
2=5\times 58-12\times 24
Donc x=58 et y=12.
Le couple cherché est (58;12).
Exercice n°4
On donne a=145 et b=55
1. Déterminer le PGCD(a;b) avec l’algorithme d’Euclide.
2. En déduire un couple d’entiers relatifs (u;v) tel que au+bv=PGCD(a;b).
Exercice n°5
1. Déterminer le PGCD(559;325) avec l’algorithme d’Euclide.
2. En déduire qu’il existe un couple d’entiers relatifs (u;v) tel que 559u+325v=13 et le déterminer.
Exercice n°6
1. Déterminer le PGCD(564;235) avec l’algorithme d’Euclide.
2. En déduire qu’il existe un couple d’entiers relatifs (u;v) tel que 564u+235v=47 et le déterminer.
Théorème de Bezout
Théorème de Bezout
Soient a et b deux entiers relatifs non nuls.
a et b sont premiers entre eux si et seulement si il existe deux entiers u et v tels que au+bv=1.
Déterminer u et v à l’aide de la TI 83 Premium CE
Déterminer u et v tels que 28u-33v=1.
On exprime une des deux inconnues, par exemple v en fonction de u.
v=\frac{28}{33}u-\frac{1}{33}.
Au clavier
A l’écran
Appuyer sur la touche f(x) puis saisir à côté de Y1 , \frac{28}{33}x-\frac{1}{33}. Valider avec entrer.
Appuyer sur la touche 2nde puis la touche graphe. Au besoin paramétrer le tableur : 2nde fenêtre, DébutTBL=0 et Tbl=1.
Puis chercher la première valeur entière dans la seconde colonne en parcourant le tableur.
On peut conclure :
A l’aide de la calculatrice u=13 et v=11.
Exercice n°7
- A l’aide de la calculatrice, déterminer deux entiers u et v tels que 99u+58v=1.
2. En déduire le PGCD(99;58).
Exercice n°8
- A l’aide de la calculatrice, déterminer deux entiers u et v tels que 11u+19v=1.
2. En déduire le PGCD(11;19).
Exercice n°9
- A l’aide de la calculatrice, déterminer deux entiers x et y tels que 89x+37y=1.
2. En déduire le PGCD(89;37).
Déterminer u et v à l’aide de l’algorithme d’Euclide
Déterminer u et v tels que 38u+15v=1.
On écrit l’algorithme d’Euclide en rajoutant une colonne.
On écrit la dernière égalité de la dernière colonne :
1=8-1\times 7
On remplace 7 par 15-1\times 8
1=8-1\times (15-1\times 8)
On réduit
1=8-15+8
1=2\times 8-15
On remplace 8 par 38-2\times 15
1=2\times (38-2\times 15)-15
On développe
1=2\times 38-4\times 15-15
On réduit
1=2\times 38-5\times 15
Donc u=38 et v=-5
Exercice n°10
- A l’aide de l’algorithme d’Euclide, déterminer deux entiers x et y tels que 29x+12y=1.
2. En déduire le PGCD(29;12).
Exercice n°11
- A l’aide de l’algorithme d’Euclide, déterminer deux entiers u et v tels que 31u+70v=1.
2. En déduire le PGCD(31;70).
Exercice n°12
- A l’aide de l’algorithme d’Euclide, déterminer deux entiers u et v tels que 27u+11v=1.
2. En déduire le PGCD(27;11).
On veut déterminer les diviseurs positifs de 1237 et de -120.
On ne peut pas décomposer 1237 en produit de facteurs premiers car il est premier.
Donc le seul diviseur positif de 1237 est 1.
Donc le seul diviseur positif commun à 1237 et -120 est 1.
Donc PGCD(1237;-120)=1.
Donc 1237 et -120 sont premiers entre eux.
On veut déterminer les diviseurs positifs de 1286 et de 1070.
- On peut décomposer 1286 en produit de facteurs premiers.
1286
643
1
2
643
1286=2\times 643
Les diviseurs positifs sont 1;2;643;1286
- On peut décomposer 1070 en produit de facteurs premiers.
1070
535
107
1
2
5
107
1070=2\times 5\times 107
Les diviseurs de 1070 sont 1;2;5;10;107;214;535;1070.
Les diviseurs communs sont 1;2.
Donc le PGCD(1286;1070)=2.
Donc 1286 et 1070 ne sont pas premiers entre eux.
Factorisons a=n^2+2n-3
n^2+2n est le début du développement de
(n+1)^2, on va remplacer n^2+2n par
(n+1)^2-1
a=(n+1)^2-1-3
a=(n+1)^2-4
On utilise l’identité remarquable
a^2-b^2=(a-b)(a+b) pour factoriser.
a=(n+1)^2-2^2
a=(n+1-2)(n+1+2)
a=(n-1)(n+3)
Factorisons b=n^2+4n+3
n^2+4n est le début du développement de
(n+2)^2, on va remplacer n^2+4n par
(n+2)^2-4
b=(n+2)^2-4+3
b=(n+2)^2-1
On utilise l’identité remarquable
a^2-b^2=(a-b)(a+b) pour factoriser.
b=(n+2)^2-1^2
b=(n+2-1)(n+2+1)
b=(n+1)(n+3)
On veut déterminer PGCD(n-1;n+1) en distinguant les cas n pair et n impair.
Le PGCD(n-1;n+1) divise (n+1)-1\times(n-1) c’est-à-dire 2.
Les diviseurs positifs de 2 sont 1 et 2.
Donc PGCD(n-1;n+1)=1 ou PGCD(n-1;n+1)=2.
cas n°1 : supposons que n est pair
Comme n est pair, n-1 et n+1 sont impairs. Comme PGCD(n-1;n+1) divise n-1 et n+1 , il ne peut pas être égal à 2. Donc il est égal à 2.
cas n°2 : Supposons que n est impair
Comme n est impair, n-1 et n+1 sont pairs. Soit PGCD(n-1;n+1) divise n-1 et n+1 donc il est égal à 2.
Conclusion :
Si n est pair, PGCD(n-1;n+1)=1
Si n est impair, PGCD(n-1;n+1)=2
On a montré dans la question précédente que
Si n est pair, PGCD(n-1;n+1)=1
Si n est impair, PGCD(n-1;n+1)=2
On va multiplier par n+3
Si n est pair, PGCD((n+3)\times (n-1);(n+3)\times(n+1))=(n+3)\times 1 donc PGCD(a;b)=n+3.
Si n est impair, PGCD((n+3)\times (n-1);(n+3)\times(n+1))=(n+3)\times 2 donc PGCD(a;b)=2n+6.
Après avoir utilisé l’Algorithme d’Euclide, le dernier reste non nul trouvé est 5 donc PGCD(a;b)=5
On veut en déduire un couple d’entiers relatifs (u;v) tel que au+bv=PGCD(a;b).
On écrit la dernière égalité de la dernière colonne :
5=20-1\times 15
On remplace 15 par 35-1\times 20
5=20-1\times (35-1\times 20)
On développe
5=20-1\times 35+1\times 20
On réduit
5=2\times 20-35
On remplace 20 par 55-1\times 35
5=2\times (55-1\times 35)-35
On développe
5=2\times 55-2\times 35-35
On réduit
5=2\times 55-3\times 35
On remplace 35 par 145-2\times 55
5=2\times 55-3\times (145-2\times 55)
On développe
5=2\times 55-3\times 145+6\times 55\\5=-3\times 145+8\times 55
Donc u=38 et v=-5
Donc le couple d’entiers relatifs est (38;-5) et 38a-5b=5.
Après avoir utilisé l’Algorithme d’Euclide, le dernier reste non nul trouvé est 5 donc PGCD(a;b)=5
Le dernier reste non nul est 13 donc PGCD(559;325)=13.
On veut en déduire un couple d’entiers relatifs (u;v) tel que au+bv=PGCD(a;b).
On écrit la dernière égalité de la dernière colonne :
13=52-1\times 39
On remplace 39 par 91-1\times 52
13=52-1\times (91-1\times 52)
On développe
13=52-1\times 91+1\times 52
On réduit
13=2\times 52-91
On remplace 52 par 234-2\times 91
13=2\times (234-2\times 91)-91
On développe
13=2\times 234-4\times 91-91
On réduit
13=2\times 234-5\times 91
On remplace 91 par 325-1\times 234
13=2\times 234-5\times (325-1\times 234)
On développe
13=2\times 234-5\times 325+5\times 234
On réduit
13=7\times 234-5\times 325
On remplace 234 par 559-1\times 325
13=7\times (559-1\times325)-5\times 325
On développe
13=7\times 559-7\times325-5\times 325
On réduit
13=7\times 559-12\times325
Donc u=7 et v=-12
Donc le couple d’entiers relatifs est (7;-12) et 7\times 559-12\times325=13.
Le dernier reste non nul est 47 donc PGCD(564;235)=47.
On veut en déduire un couple d’entiers relatifs (u;v) tel que 564u+235v=47.
On écrit la dernière égalité de la dernière colonne :
47=235-2\times 94
On remplace 94 par 564-2\times 235
47=235-2\times (564-2\times 235)
On développe
47=235-2\times 564+4\times 235
On réduit
47=-2\times 564+5\times 235
Donc u=-2 et v=5
Donc le couple d’entiers relatifs est (-2;5) et -2\times 564+5\times235=47.
On veut déterminer u et v tels que 99u+58v=1.
On exprime une des deux inconnues, par exemple v en fonction de u.
v=-\frac{99}{58}u+\frac{1}{58}.
On programme la TI 83 Premium CE.
Au clavier
A l’écran
Appuyer sur la touche f(x) puis saisir à côté de Y1 , -\frac{99}{58}x+\frac{1}{58}. Valider avec entrer.
Appuyer sur la touche 2nde puis la touche graphe. Au besoin paramétrer le tableur : 2nde fenêtre, DébutTBL=0 et Tbl=1.
Puis chercher la première valeur entière dans la seconde colonne en parcourant le tableur.
A l’aide de la calculatrice, on a trouvé u=17 et v=-29 tels que 99u+58v=1.
C’est-à-dire que 99\times 17+58\times (-29)=1
Dans la question 1, on a trouvé un couple d’entiers relatifs (17;-29) tel que
99\times17+58\times(-29)=1 donc, d’après le théorème de Bezout, PGCD(99;58)=1.
On veut déterminer u et v tels que 11u+19v=1.
On exprime une des deux inconnues, par exemple v en fonction de u.
v=-\frac{11}{19}u+\frac{1}{19}.
On programme la TI 83 Premium CE.
Au clavier
A l’écran
Appuyer sur la touche f(x) puis saisir à côté de Y1 , -\frac{11}{19}x+\frac{1}{19}. Valider avec entrer.
Appuyer sur la touche 2nde puis la touche graphe. Au besoin paramétrer le tableur : 2nde fenêtre, DébutTBL=0 et Tbl=1.
Puis chercher la première valeur entière dans la seconde colonne en parcourant le tableur.
On a trouvé u=7 et v=-4.
Dans la question 1, on a trouvé un couple d’entiers relatifs (7;-4) tel que
11\times 7+19\times(-4)=1 donc, d’après le théorème de Bezout, PGCD(11;19)=1.
On veut déterminer x et y tels que 89x+37y=1.
On exprime une des deux inconnues, par exemple y en fonction de x.
y=-\frac{89}{37}x+\frac{1}{37}.
On programme la TI 83 Premium CE.
Au clavier
A l’écran
Appuyer sur la touche f(x) puis saisir à côté de Y1 , -\frac{99}{58}x+\frac{1}{58}. Valider avec entrer.
Appuyer sur la touche 2nde puis la touche graphe. Au besoin paramétrer le tableur : 2nde fenêtre, DébutTBL=0 et Tbl=1.
Puis chercher la première valeur entière dans la seconde colonne en parcourant le tableur.
A l’aide de la calculatrice, on a trouvé x=5 et y=-12 tels que 89x+37y=1.
C’est-à-dire que 89\times 5+37\times (-12)=1
Dans la question 1, on a trouvé un couple d’entiers relatifs (5;-12) tel que
89\times 5+37\times(-12)=1 donc, d’après le théorème de Bezout, PGCD(89;37)=1.
On veut déterminer x et y tels que 29x+12y=1.
On écrit l’algorithme d’Euclide en rajoutant une colonne.
On écrit la dernière égalité de la dernière colonne :
1=5-2\times 2
On remplace 2 par 12-2\times 5
1=5-2\times (12-2\times 5)
On développe
1=5-2\times 12+4\times 5)
On réduit
1=5\times 5-2\times 12
On remplace 5 par 29-2\times 12
1=5\times (29-2\times 12)-2\times 12
On développe
1=5\times 29-10\times 12-2\times 12
On réduit
1=5\times 29-12\times 12
Donc x=5 et y=-12.
Dans la question 1, on a trouvé un couple d’entiers relatifs (5;-12) tel que
29\times 5+12\times(-12)=1 donc, d’après le théorème de Bezout, PGCD(29;12)=1.
On veut déterminer u et v tels que 31u+70v=1.
On écrit l’algorithme d’Euclide en rajoutant une colonne.
On écrit la dernière égalité de la dernière colonne :
1=8-1\times 7
On remplace 7 par 31-3\times 8
1=8-1\times (31-3\times 8)
On développe
1=8-31+3\times 8
On réduit
1=4\times 8-31
On remplace 8 par 70-2\times 31
1=4\times (70-2\times 31)-31
On développe
1=4\times 70-8\times 31-31
On réduit
1=4\times 70-9\times 31
Donc u=-9 et v=4.
Dans la question 1, on a trouvé un couple d’entiers relatifs (-9;4) tel que
31\times (-9)+70\times 4=1 donc, d’après le théorème de Bezout, PGCD(31;70)=1.
On veut déterminer u et v tels que 27u+11v=1.
On écrit l’algorithme d’Euclide en rajoutant une colonne.
On écrit la dernière égalité de la dernière colonne :
1=11-2\times 5
On remplace 5 par 27-2\times 11
1=11-2\times (27-2\times 11)
On développe
1=11-2\times 27+4\times 11
On réduit
1=-2\times 27+5\times 11
Donc u=-2 et v=5.
Dans la question 1, on a trouvé un couple d’entiers relatifs (-2;5) tel que
27\times (-2)+11\times 5=1 donc, d’après le théorème de Bezout, PGCD(27;11)=1.