Chapitres
- 01. Introduction
- 02. La divisibilité dans Z
- 03. Le PGCD
Introduction
Division euclidienne, PGCD, trop facile ? Et bien non. Derrière des notions simples se cachent en faite des théorèmes bien plus compliqués. Théorème de Gauss, de Bezout et algorithme d'Euclide, regardons tout ce que le monde des mathématiques peut nous faire découvrir.
La divisibilité dans Z
Multiples et diviseurs
- Définitions
Z est l'ensemble des entiers relatifs, c'est à dire l'ensemble des entiers positifs et négatifs. On prend a et b dans Z.
Par définition, a est un multiple de b si et seulement si il existe un entier relatif m tel que [a=btimes m]
Les multiples de 3 sont tous les nombres de la forme 3m (où m est dans Z) : 6, 9, 12, 36, etc...
Cela revient exactement à dire que b divise a (noté b/a) ou encore que a est divisible par b ou que b est un diviseur de a.
Ainsi, les nombres de la forme 3m sont des diviseurs de 3.
Déterminons tous les diviseurs de 48 et de 84.
[48 = 1 times 48= 2 times 24= 3 times 16] [= 4 times 12= 6 times 8]
Les diviseurs de 48 sont 1, 2, 3, 4, 6, 8, 12, 16, 24 et 48.
[84 = 1 times 84= 2 times 42= 3 times 28] [= 4 times 21= 6 times 14= 7 times 12]
Les diviseurs de 84 sont 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42 et 84.
- Propriétés
Soient a et b dans Z.
On sait que la somme, la différence et le produit de deux entiers relatifs est un entier relatif. Ceci est faux pour la division.
Si b divise a alors tout diviseur de b est un diviseur de a.
Tout nombre divise 0 donc 0 est un multiple de tout nombre entier. En effet, [atimes 0=0] Par contre, le chiffre 0 ne divise aucun entier à part lui même.
Les nombres 1 et -1 divisent tout entier de Z. En effet, [atimes 1=a] donc 1 divise a et [atimes (-1)=-a] donc -1 divise a.
Si b divise a alors -b divise a. En effet, b divise a implique qu'il existe un entier relatif m tel que [a=btimes m] Alors [a=(-b)times (-m)] où -m est bien un entier relatif. Donc -b divise a.
Si b divise a alors [mid bmidleqmid amid]
Si a divise b et b divise a alors a=b ou a=-b. En effet, si a divise b alors [mid amidleqmid bmid] et si b divise a alors [mid bmidleqmid amid] Donc [mid amid=mid bmid] ce qui implique a=b ou a=-b.
Soit c dans Z. Si a divise b et si b divise c alors a divise c. En effet, il existe un entier relatif m tel que [b=atimes m] et il existe un entier relatif m' tel que [c=btimes m'] Donc [c=atimes mtimes m'] Ainsi, il existe m'' dans Z tel que [c=atimes m''] et don
c a divise c.
De même, si a divise b et a divise c alors a divise ub+vc quelque soit u et v dans Z.
Enfin, si a divise b alors ac divise bc. En effet, si a divise b alors [b=atimes m] d'où [btimes c=atimes ctimes m] Ainsi, on a bien ac divise bc.
Où trouver des cours de maths pour réviser avant une épreuve ?
Division euclidienne
- Définitions
Commençons par définir la division euclidienne dans N où N est l'ensemble des entiers naturels (entiers positifs).
Soient a et b des entiers positifs dans N où b est non nul. Alors il existe un unique couple (q,r) d'entiers naturels tel que [a=btimes q+r] où [0leq r<b]
On appelle a le dividende, b le diviseur, r le reste et q le quotient.
Effectuons la division euclidienne de 116 par 8 : [116=8times 14+4]
Si b divise a alors le reste de la division euclidienne de a par b est nul.
De même, on peut définir la division euclidienne dans Z.
Soient a et b des entiers relatifs où b est non nul. Alors il existe un unique couple (q,r) où q est un entier relatif et r un entier naturel tel que [a=btimes q+r] où [0leq r<|b|]
- Exercice
Démontrons que [A=n(n+1)(2n+1)] est divisible par 3 pour tout n appartenant à N.
Les restes possibles dans la division euclidienne par 3 sont 0, 1 ou 2. On va donc écrire, pour p appartient à N, n=3p, n=3p+1 ou n=3p+2.
Si n=3p, [A=3p(3p+1)(2times 3p+1)=3times q] où [q=p(3p+1)(6p+1)] A est alors un multiple de 3.
Si n=3p+1, [A=] [(3p+1)(3p+1+1)(2times (3p+1)+1)] [=(3p+1)(3p+2)(6p+3)] [=(3p+1)(3p+2)3(2p+1)] [=3q'] où [q'=(3p+1)(3p+2)(2p+1)] Dans ce cas, A est un multiple de 3.
Si n=3p+2, [A=(3p+2)(3p+2+1)(2times (3p+2)+1] [=(3p+2)3(p+1)(6p+5)=3q''] où [q''=(3p+2)(p+1)(6p+5)] Ici A est encore un multiple de 3.
Dans chacune des trois possibilités, A est un multiple de 3. Donc pour tout n appartenant à N, A est toujours divisible par 3.
Vous cherchez des cours de maths seconde ?
Le PGCD
Définition
On se place dans N.
On appelle D(a) l'ensemble des diviseurs de a. Ainsi, les éléments de D(a) sont tous inférieurs ou égaux à a. Lorsque a>1, D(a) contient au moins 1 et a. Le plus petit élément de D(a) et 1 et le plus grand est a.
On note alors D(a,b) l'ensemble des diviseurs communs à a et b. On a quelques propriétés :
D(a,a)=D(a)
D(a,b)=D(b,a)
[D(a,b)=D(a)cap D(b)]
D(a,b) n'est jamais nul puisqu'il contient au moins 1. Tous ses éléments sont inférieurs ou égaux à a et à b. Donc D(a,b) contient un plus grand élément qu'on appelle le PGCD.
D(0,a)=D(a). En effet, [D(0,a)=D(0)cap D(a)=D(a)]
Soit b non nul, si b divise a alors D(a,b)=D(b).
On appelle PGCD de deux nombres le plus grand commun diviseur à ces deux nombres.
De cette façon, si b divise a, alors PGCD(a,b)=b.
Tout diviseur de deux entiers a et b est un diviseur de leur PGCD et réciproquement.
On cherche les diviseurs communs à 48 et 84. On a vu précédemment que D(48)={1, 2, 3, 4, 6, 8, 12, 16, 24, 48} et D(84)={1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84}. Ainsi, les diviseurs communs à 48 et 84 sont 1, 2, 3, 4, 6, et 12. On note [D(48,84)={1, 2, 3, 4, 6, 12}]
Le plus grand diviseur commun à 48 et 84 est 12. Donc 12 est le PGDC de 84 et 48. On note [PGCD (48, 84) = 12]
Le PGCD est utile dans différents cas. Commençons par regarder comment le déterminer.
Où trouver des cours de maths terminale s ?
Détermination du PGCD
- Méthode des soustractions successives
On montre que D(a,b)=D(b,a-b) avec a>b.
Montrons que si d appartient à D(a,b) alors d appartient à D(b,a-b). Si d appartient à D(a,b) alors d divise a et d divise b alors d divise b et d divise a-b (car d divise au+bv avec ici u=1 et v=-1) alors d appartient à D(b,a-b). Ainsi, [D(a,b)subset D(b,a-b)]
A l'inverse, si d appartient à D(b,a-b) alors d divise b et d divise a-b donc d divise a-b+b d'où d divise b et d divise a. Alors d appartient à D(a,b) et donc [D(b,a-b)subset D(a,b)]
Finalement, on obtient que [D(a,b)=D(b,a-b)]
Étudions un exemple. Déterminons par la méthode des soustractions successives le PGCD de 306 et 108.
D(306, 108) = D(108, 306 – 108) = D(108, 198) = D(198, 108) = D(108, 198 – 108) = D (108, 90) = D(90, 108-90) = D(90, 18) = D(18, 90 – 18) = D(18, 72) = D(72, 18) = D(18, 72-18) = D(18, 54) = D(54,18) = D(18, 54 – 18) = D(18, 36) = D(36,18) = D(18, 36-18) = D(18, 18) = D(18).
Donc PGCD(306, 108)=18.
- Algorithme d'Euclide
Il existe une méthode efficace pour déterminer le PGCD de deux nombres. On appelle ça l'algorithme d'Euclide. Il consiste à faire des divisions euclidiennes successives.
Pour cela, on montre que D(a,b)=D(b,r) où 0<b<a et r est le reste de la division euclidienne de a par b.
Si d appartient à D(a,b) alors d divise a et d divise b alors d divise a et d divise bq alors d divise b et d divise a-bq. Ainsi d appartient à D(b,r) puisque r=a-bq et donc [D(a,b)subset D(b,r)]
Inversement, si d appartient à D(b,r) alors d divise b et d divise r. Ainsi, d divise b et d divise a-bq alors d divise b et d divise bq donc d divise a+bq-bq et d divise b donc d divise a et d divise b. Ainsi, d appartient à D(a,b) et [D(b,r)subset D(a,b)]
Finalement, D(a,b)=D(b,r).
Regardons un exemple. Cherchons le PGCD de 48 et 84 par l'algorithme d'Euclide.
[84=48times 1+36]
[48=36times 1+12]
[36=12times 3+0]
Le PGCD est le dernier reste non nul. En effet, si r=0, b divise a et D(a,b)=D(b).
Ainsi PGCD(84,48)=12.
Regardons un deuxième exemple. Cherchons le PGCD de 306 et 108.
[306 = 108 times 2 + 90]
[108 = 90 times 1 + 18]
[90 = 18 times 5 + 0]
Donc PGCD(306,108)=18.
Propriétés du PGCD
- Théorème de Bezout
Deux entiers naturels sont dits premiers entre eux lorsque leur PGCD est égal à 1. Ils n'ont alors que 1 comme diviseur commun.
Deux entiers relatifs sont dits premiers entre eux s'ils n'ont pour diviseurs communs que 1 et -1.
Suite à ces définitions, nous pouvons énoncer notre théorème :
Deux entiers naturels a et b sont premiers entre eux si et seulement si il existe deux entiers u et v dans Z tels que au+bv=1.
Cela implique que si a est premier avec b et avec c alors il est premier avec bc.
Par exemple, 7 et 11 sont premiers entre eux. [11times2+(-3)times7=1] Avec u=2 et v=-3, on a bien le théorème ci dessus de vérifié.
Mais comment déterminer u et v ?
On utilise l'algorithme d'Euclide.
[11=7times 1+4] C'est à dire [a=btimes1+4] d'où [a-b=4]
Ensuite [7=4times 1+3] C'est à dire [b=(a-b)times1+3] d'où [3=2b-a]
Enfin [4=3times 1+1] C'est à dire [a-b=(2b-a)times 1+1] d'où [1=a-b-2b+a=2a-3b]
On a alors [1=2times 11 - 3times7] On a bien u=2 et v=-3.
Les entiers u et v ne sont pas uniques. En effet, on observe que u=-5 et v=8 fonctionne également. [11times (-5)+7times 8=1]
- Caractérisation du PGCD
Soient a, b et g dans N*. On a équivalence entre les trois propositions suivantes :
(1) g=PGCD(a,b)
(2) g est un diviseur de a et de b et [\frac{a}{g}] et [\frac{b}{g}] sont premiers entre eux
(3) g est un diviseur de a et de b et il existe deux entiers relatifs u et v tel que au+bv=g.
Par conséquent, si g=PGCD(a,b) alors pour tout c appartenant à N, gc=PGCD(ac,bc)
En effet, si g=PGCD(a,b) alors g divise a et g divise b alors il existe deux entiers relatifs u et v tels que au+bv=g. Ainsi, gc divise ac et gc divise bc et alors il existe deux entiers relatifs u et v tels que u(ac)+v(bc)=(gc). Finalement, gc=PGCD(ac,bc).
De manière analogue, [\frac{g}{c}=PGCD(\frac{a}{c},\frac{b}{c})]
- Théorème de Gauss
Énonçons le théorème :
Soient a, b et c dans N*. Si a divise bc et si a est premier avec b alors a divise c.
Ce théorème implique que si a divise n et b divise n avec a et b premiers entre eux alors ab divise n.
- Fraction irréductible
Une fraction est un nombre de la forme [\frac{a}{b}] où a est dans Z et b dans Z*. Lorsque a et b sont premiers entre eux, on dit que [\frac{a}{b}] est une fraction irréductible (simplifiée au maximum). Toute fraction est égale à une fraction irréductible.
Ainsi, pour obtenir la forme irréductible d'une fraction, il faut la simplifier par le PGCD de a et de b.
Si vous désirez une aide personnalisée, contactez dès maintenant l’un de nos professeurs !