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.

Les meilleurs professeurs de Maths disponibles
1er cours offert !
Laurent
4,9
4,9 (86 avis)
Laurent
50€
/h
1er cours offert !
Anis
4,9
4,9 (79 avis)
Anis
90€
/h
1er cours offert !
Greg
5
5 (96 avis)
Greg
110€
/h
1er cours offert !
Grégory
5
5 (83 avis)
Grégory
110€
/h
1er cours offert !
Ahmed
4,9
4,9 (79 avis)
Ahmed
40€
/h
1er cours offert !
Jean-charles
5
5 (20 avis)
Jean-charles
20€
/h
1er cours offert !
Minh duc
5
5 (49 avis)
Minh duc
100€
/h
1er cours offert !
Pierre-thomas
5
5 (42 avis)
Pierre-thomas
80€
/h
1er cours offert !
Laurent
4,9
4,9 (86 avis)
Laurent
50€
/h
1er cours offert !
Anis
4,9
4,9 (79 avis)
Anis
90€
/h
1er cours offert !
Greg
5
5 (96 avis)
Greg
110€
/h
1er cours offert !
Grégory
5
5 (83 avis)
Grégory
110€
/h
1er cours offert !
Ahmed
4,9
4,9 (79 avis)
Ahmed
40€
/h
1er cours offert !
Jean-charles
5
5 (20 avis)
Jean-charles
20€
/h
1er cours offert !
Minh duc
5
5 (49 avis)
Minh duc
100€
/h
1er cours offert !
Pierre-thomas
5
5 (42 avis)
Pierre-thomas
80€
/h
1er cours offert>

La divisibilité dans Z

Multiples et diviseurs

Qu'est ce que des multiples et des diviseurs ?
Commençons par définir les termes importants.
  • 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=b\times 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,

    \[a\times 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,

    \[a\times 1=a\]

donc 1 divise a et

    \[a\times (-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=b\times m\]

Alors

    \[a=(-b)\times (-m)\]

  où -m est bien un entier relatif. Donc -b divise a.

Si b divise a alors

    \[\mid b\mid\leq\mid a\mid\]

Si a divise b et b divise a alors a=b ou a=-b. En effet, si a divise b alors

    \[\mid a\mid\leq\mid b\mid\]

et si b divise a alors

    \[\mid b\mid\leq\mid a\mid\]

Donc

    \[\mid a\mid=\mid b\mid\]

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=a\times m\]

et il existe un entier relatif m' tel que

    \[c=b\times m'\]

Donc

    \[c=a\times m\times m'\]

Ainsi, il existe m'' dans Z tel que

    \[c=a\times 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=a\times m\]

d'où

    \[b\times c=a\times c\times m\]

Ainsi, on a bien ac divise bc.

Où trouver des cours de maths pour réviser avant une épreuve ?

Division euclidienne

Comment effectuer une division euclidienne ?
Regardons ce qu'est une division euclidienne et comment l'effectuer.
  • 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=b\times q+r\]

    \[0\leq 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=8\times 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=b\times q+r\]

    \[0\leq 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)(2\times 3p+1)=3\times q\]

    \[q=p(3p+1)(6p+1)\]

A est alors un multiple de 3.

Si n=3p+1,

    \[A=\]

    \[(3p+1)(3p+1+1)(2\times (3p+1)+1)\]

    \[=(3p+1)(3p+2)(6p+3)\]

    \[=(3p+1)(3p+2)3(2p+1)\]

    \[=3q'\]

    \[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)(2\times (3p+2)+1\]

    \[=(3p+2)3(p+1)(6p+5)=3q''\]

    \[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

Qu'est ce que le PGCD et comment le trouver ?
Qu'est ce que le PGCD ?

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

Qu'est ce que l'algorithme d'Euclide ?
Comment déterminer le 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=48\times 1+36\]

    \[48=36\times 1+12\]

    \[36=12\times 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

Qu'est ce que les théorèmes de Gauss et de Bezout ?
Regardons les théorèmes que l'on obtient grâce au 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.

    \[11\times2+(-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=7\times 1+4\]

C'est à dire

    \[a=b\times1+4\]

d'où

    \[a-b=4\]

Ensuite

    \[7=4\times 1+3\]

C'est à dire

    \[b=(a-b)\times1+3\]

d'où

    \[3=2b-a\]

Enfin

    \[4=3\times 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=2\times 11 - 3\times7\]

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.

    \[11\times (-5)+7\times 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.

Besoin d'un professeur de Maths ?

Vous avez aimé l’article ?

Aucune information ? Sérieusement ?Ok, nous tacherons de faire mieux pour le prochainLa moyenne, ouf ! Pas mieux ?Merci. Posez vos questions dans les commentaires.Un plaisir de vous aider ! :) 5,00/5 - 1 vote(s)
Loading...

Elise

Freelancer, superprof et étudiante en mathématiques, je souhaite partager et étendre mes connaissances grâce à vous !