NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 31/10/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

THÉORIE DES NOMBRES

 

Débutants

Général

DIVISEURS ET MULTIPLES

 

Glossaire

Général

 

 

INDEX

 

Calcul

 

Théorie des nombres

 

PGCD

PPCM

Premiers entre eux

Algorithme d'Euclide

PGCD / PPCM / Racine

 

Sommaire de cette page

>>> Algorithme d'Euclide

>>> Disposition pratique

>>> Exemple expliqué

>>> Démonstration

>>> Préparation de la programmation

>>> Organigramme

>>> Programme

>>> Formation d'une expression linéaire

 

 

 

 

 

ALGORITHME D'EUCLIDE

pour le calcul du PGCD

 Plus Grand Commun Diviseur

 

Description de l'algorithme d'Euclide.

Exemple de présentation d'un algorithme. 

Voir Algorithme d'Euclide (Terminale)

 

 

 

ALGORITHME D'EUCLIDE 

 

*    Il s'agit de divisions en cascade: les résultats de l'une servent à poser la suivante:

*      Le diviseur B devient le dividende; et

*      Le reste r1 devient le diviseur.

 

*    Arrêt lorsque le reste de la division est nul.

 

*    Le reste trouvé avant le reste nul est le PGCD.

 

 

 

 

Disposition pratique 

 

*    Au lieu de mettre le quotient q en bas, on le place au-dessus du diviseur de manière à laisser la place au reste de la division suivante.

 

 

Principe et exemple

 

 

 

Exemple complet expliqué

 

 

A = 33 810     = 1 x 2 x 3 x 5 x 7 x 7       x 23

B =   4 116     = 1 x 2 x 3 x       7 x 7 x 7

PGCD (A, B)  = 1 x 2 x 3 x       7 x 7                 = 294

 

 

 

Démonstration   On note: g = PGCD(A, B) avac A >B

Départ

Division de A par B.

A = Bq + r

1 – Cas n°1

Si r = 0

Alors B divise A.

g = B

2 – Cas n°2

Si r  0

Si g existe, il divise A (a= g.a) et B (B=g.b)

Or, tout diviseur g, commun à A et B, divise aussi r, selon la démonstration ci-contre.

A – Bq = r

g.a – g.b.q = r

g(a – b.q) = r

g(a – b.q) = g.s

r = g.s

Autrement dit

Tout diviseur g, commun à B et r, divise aussi A.

Bq + r = A

31 – Nouveau problème

 

Cherchez les diviseurs communs à B et r.

Tous deux sont plus petits que les nombres A et B initiaux.

Le problème est simplifié.

r < B < A

Poursuivons

On réalise les divisions successives.

Les restes vont en diminuant.

A = Bq + r

B = rq1 + r1

r = r1 q2 + r2

r1 = r2 q3 + r3

rn-1 = rn qn+1 + rn+1

32 – Deux cas possibles

 

Si rn+1 = 0

Les diviseurs cherchés sont ceux de rn

rn divise rn-1

 

Et …

g = rn

Si rn+1 = 1

Les diviseurs communs à A et B

sont les diviseurs communs à rn et à 1.

A et B  sont premiers entre eux.

g = 1.

 

 

  

RAPPEL pour préparer la programmation

 

Rappel du principe avec ces exemples

 

La division de A

par B

donne un reste  R

8 136

492

264

492

264

228

264

228

36

228

36

12

36

12

0

 

On a bien:

8 136         = 12      x 678

   492         = 12      x   41

 

 

La division de A

par B

donne un reste C

123 456 789

467 769

433 542

467 769

433 542

34 227

433 542

34 227

22 818

34 227

22 818

11 409

22 818

11 409

0

 

On a bien

123 456 789

= 11 409

x 10 821

467 769

= 11 409

x 41

 

 

On note la simplicité

 

*           À chaque ligne suivante:

*           A prend la valeur de B,

*           B celle de R.

*           Et, on recommence la division avec ces nouvelles valeurs de B et R.

On s'arrête lorsque R est nul.

Le PGCD est égal au B final.

 

Illustration

 

 

 

 

 

ORGANIGRAMME

 

Organigramme - Anglais: flow chart

 

*           Les symboles utilisés ici sont les plus courantes.

*           Les rectangles correspondent à des ordres à exécuter.

*           On parcourt les instructions dans le sens des flèches.

*           Les aiguillages sont symbolisés par un losange.

*           On emprunte la flèche qui correspond au résultat du test.

 

 

 

PROGRAMME selon l'organigramme ci-dessus

 

A := 8136:

B := 492:

C := 1:

 

while C<>0 do

         C := A mod(B):

     lprint(A,B,C):

         A := B:

         B := C:

 od:

 

8136, 492, 264

492, 264, 228

264, 228, 36

228, 36, 12

36, 12, 0

 

 

Autre exemple d'exécution

454545545454, 531441, 338067

531441, 338067, 193374

338067, 193374, 144693

193374, 144693, 48681

144693, 48681, 47331

48681, 47331, 1350

47331, 1350, 81

1350, 81, 54

81, 54, 27

54, 27, 0

 

 

 

*  Le calcul du reste de la division est remplacé par son équivalent : le calcul du modulo: C = A modulo B.
(C est alors le reste de la division de A par B)

 

*  On imprime le résultat à chaque itération pour obtenir le résultat présenté comme en indiqué ci-dessus.

*  Notez que:

*      L'instruction while se poursuit tant que

C est différent de 0.

*      Il est donc important de lancer le programme avec une valeur de C différente de 0.

*      Ici, on a choisi de forcer C à 1.
 

Langage type Mapple: voir Convention de notations / Programmation

 

 

Exemple avec expression linéaire

 

Appliquez l'algorithme d'Euclide pour trouver:

 

 

g = PGCD (2059, 2581) = ?

g = f(2059, 2581) = ?

 

Suite des opérations.

PGCD

g = 29

 

En remontant la chaine.

 

 

 

 

Suite

*       Algorithme d'Euclide (page voisine)

*       PGCD / PPCM / Racine

Voir

*       Algorithmes

*       Diviseurs: calculs et facteurs premiers

*       Division

*       Théorie des nombres

Cette page

http://villemin.gerard.free.fr/ThNbDemo/AlgoEucl.htm