NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 29/04/2020

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths

     

Théorie des Nombres

 

Débutants

Général

DIVISIBILITÉ

 

Glossaire

Général

 

 

INDEX

 

Divisibilité

 

Calcul

 

Théorie des nombres

 

Programme de 3e

PGCD

Algorithme d'Euclide

Premiers entre eux

PPCM

 Sa programmation

Pgcd / Ppcm / Racine

 

Sommaire de cette page

>>> Approche

>>> Notation et exemples

>>> Programmation 

>>> Le triplet: retrouver le 3e

>>> Exploration

>>> Propriétés 

>>> PGCD de plusieurs nombres

>>> PGCD de 3 nombres

>>> PGCD et PPCM

>>> Exemples illustrés

 

 

 

 

PGCD

Plus Grand Commun Diviseur

 

Chaque nombre étant décomposable en facteurs premiers, on détermine le degré de cousinage des nombres en cherchant s'ils ont une tranche commune de facteurs premiers.

Le calcul du PGCD est utile pour simplifier les fractions.

 

Plus simplement dit

k est le PGCD de a et b veut simplement dire que

a et b sont des multiples de k.

Anglais: Greatest Common Divisor -  GCD

Also: Highest Common Factor

 

 

  

Approche

 

*    Avec les nombres 4 et 6, cherchons la plus grande "longueur" commune.

*    Quelle est l'unité de mesure qui permet de mesurer exactement à la fois l'une et l'autre des barres?

 

 

*    Bien évidemment la réponse est: 2. Car, avec 2 comme unité de longueur, je peux mesurer à la fois 4, il faut 2 fois cette unité et 6, il faut 3 fois cette unité. 
 

 

 

Exemples 

 

A = 18

B = 21

PGCD (A, B)

 

A = 25

B = 100

PGCD (A, B)

 

A = 11

B = 21

PGCD (A, B)

 

 

= 1 x 2 x 3 x 3

= 1 x       3       x 7

= 1       x 3 = 3

 

= 1           x  5 x 5

= 1 x 2 x 2 x 5 x 5

= 1             x 5 x 5 = 25

 

= 1           x 11

= 1 x 3 x 7

= 1   (A et B sont premiers entre eux)
 

Simplification des fractions

 

Si  est une fraction, numérateur et dénominateur peuvent être divisés par le PGCD pour obtenir une fraction irréductible.

 

 

Voir Calcul avec l'algorithme d'Euclide

 

 

 

 

 

 

 

Remarque générale sur les notations

Normale

Abrégée

Signification

a.b

ab

*    Multiplication de a par b.

a.b

½ab½

*    Valeur absolue du produit a.b

PGCD (a,b)

(a,b)

*    Plus grand commun diviseur de a et b.

PGCD (a,b) = 1

(a,b) = 1

*    a et b sont premiers entre eux.

*    a et b sont étrangers (autre nom).

PPCM (a,b)

[a,b]

*    Plus petit commun multiple de a et b.

PPCM (a,b) =

 a.b / PGCD (a,b)

*    Formule liant PGCD et PPCM.

 

 

Programmation

Programme complet

Instruction dédiée

Commentaires

Exemples de nombre en x et y.

Boucle (while … do) qui tourne tant que x est différent de y (qui s'arrête lorsque x = y).

Si x est le plus grand on lui retranche y; si y est le plus grand on lui retranche x.

Fin lorsque les soustractions successives donnent une valeur de x égale à celle de y. Y compris x= y = 1.

Fin de boucle (od) et impression de x.

 

Résultat: PGCD(4 200, 36 036) = 84

 

Notez que tout logiciel mathématique comporte une instruction donnant directement le PGCD. Avec Maple, il s'agit de gcd (greatest common divisor).

Voir ProgrammationIndex

 

 

Le triplet – PGCD à trou

 

*    Sachant que 54 est le PGCD de (378 et A), quelles peuvent être les valeurs de A ?

 

*    378 et A sont tous deux des multiples de 54:

378 = 2 x 3 x 3 x 3 x 7

  54 = 2 x 3 x 3 x 3

*    Et A vaut toute valeur multiple de 54

soit A = 54 k

*    À l'exception banale de k = 7, pour laquelle les deux nombres seraient 378 et leur PGCD serait évidemment et banalement 378.
 

 

 

Exploration

A

B

PGCD (A, B)

Premiers entre eux

10

10 est 4 fois premiers

avec les nombres qui lui sont inférieurs.

1

2

3

4

5

6

7

8

9

1

2

1

2

5

2

1

2

1

1

 

1

 

 

 

1

 

1

12

12 est 4 fois premiers

avec les nombres qui lui sont inférieurs.

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

1

6

1

4

3

2

1

1

 

 

 

1

 

1

 

 

 

1

1 000

 

On observe la symétrie par rapport à A = 1 000

pour les nombres premiers avec 1000.

990

991

992

993

994

995

996

997

998

999

1000

1001

1002

1003

1004

1005

1006

1007

1008

1009

1010

10

1

8

1

2

5

4

1

2

1

1000

1

2

1

4

5

2

1

8

1

10

 

1

 

1

 

 

 

1

 

1

 

1

 

1

 

 

 

1

 

1

 

Voir Table des PGCD

  

Propriétés 

Notation normale

Notation abrégée

 PGCD (a, 1)

= 1

  (a, 1)

= 1

 PGCD (a, a)

= a

  (a, a)

= a

PGCD (a, b)

= PGCD (b, a)

 (a, b)

=  (b, a)

PGCD (a , b)

= PGCD (a + b, b)

 (a , b)

=  (a+b , b)

PGCD (a , b)

ou

= PGCD (a – b, b)

= PGCD (a, b – a)

 (a , b)

= (a-b, b) si a>b

= (a, b-a) si a<b

PGCD (a, b)

= PGCD (a + kb, b)

= PGCD (a – kb, b)

(a, b)

= (a + kb, b)

= (a – kb, b)    >>>

PGCD(a, b, c)

= PGCD (PGCD(a, b), c)

= PGCD (a, PGCD(b, c))

(a, b, c)

= ((a, b), c)

= (a, (b, c))

PGCD (am, an)

= a.PGCD (m, n)

(am, an)

= g.(m, n)

Si PGCD (b, c) = 1,

PGCD (a, bc)

 

= PGCD(a, b). PGCD(a, c)

Si (b, c) = 1,

(a, bc)

 

= (a, b) (a, c)  >>>

d = PGCD(a,b)

 PGCD (a/d, b/d) = 1

d = (a,b)

D = ax + by

 PGCD (a, b)  D

D = ax + by

 (a, b)  D

PGCD (a . c, b . c)

= PGCD (a, b) x c

 (a.c , b.c)

=  (a , b) . c

PGCD (a / d, b / d)

= PGCD (a, b) / d

 (a/d , b/d)

=  (a , b) / d

PPCM (a, PGCD (a, b))

= a

[a, (a, b)]

= a

 

g = PGCD (a, b)  <=>  a / g et b / g sont premiers entre eux.

 

Pour qu'un diviseur commun à a et b soit leur PGCD, il faut et il suffit que les quotients par ce diviseur soient premiers entre eux.

 

 

Voir Propriétés des nombres premiers entre eux (PGCD = 1)

 

 

PGCD d'une somme

 

On donne (a, 4 ) = 2 et (b, 4) = 2, montrez que (a + b, 4) = 4.

 

Si (a, 4 ) = 2, cela veut dire que a et 4 sont divisibles par 2, mais que a n'est pas divisible par 4. On peut former la division euclidienne: a = 4k + 2. De même: b = 4k' + 2.

Et leur somme: a + b = 4(k + k') + 4 qui est divisible par 4.

En écriture PGCD: (a + b, 4) = 4.

 

 

Simplification du calcul d'un PGCD

 

Calculez (998, 996).

Utilisation de la propriété: (a, b) = (a – kb, b). 

(998, 996) = (998 - 996, 996) = (2, 996) = 2.

 

Autre exemple:

(204, 153) = (204 – 153, 153) = (51, 153) = (51, 3x51) = 51

 

Exemple algébrique:

(3n + 4, n + 1) = (3n + 4 – 3(n + 1), n + 1) = (1, n + 1) = 1

 

 

PGCD avec un nombre certainement composé

 

Si (b,c) = 1,

(a, bc) = (a, b) (a, c)

 

Nécessité que b et c soient premiers entre eux pour que cette formule soit vraie, même si elle peut être vraie dans d'autres cas.

 

Formule complète

 

Si ((a,b), (a,c)) = 1, alors (a, bc) = (a, b)(a, c)

 

ou

 

Si PGCD ( PGCD(a,b), PGCD(a,c) ) = 1,

alors PGCD (a, bc) = PGCD (a, b) x PGCD (a, c)

 

 

 

 

PGCD de plusieurs nombres

 

Propriété

 

PGCD (a, b, c) = PGCD (PGCD (a, b), c)

 

Pour trouver le PGCD de plusieurs nombres, on peut remplacer deux nombres par leur PGCD.

 

Exemple

PGCD (240, 252, 792)              = PGCD (PGCD (240, 252), 792)   

                                                     = PGCD (12), 792)

                                                     = 12

PGCD (322, 546, 611)              = PGCD (PGCD (322, 546), 611)   

                                                     = PGCD (14), 611)                           

                                                     = 1                                                      

 

*    Si le PGCD est égal à 1, les nombres sont tous premiers entre eux dans leur ensemble.
Attention! Ils peuvent ne pas être premiers deux à deux
Exemple: 6, 10 et 15.

 

 

 

PGCD de 3 NOMBRES

 

           Quelques exemples   &      Premières valeurs pour G croissant

           

 

 

 

PGCD et PPCM

 

*    Si a ne divise pas b mais s'ils ont en commun un nombre g qui les divise tous les deux, alors a et b sont tous deux composés.

 

 

Dans ce cas, il existe un nombre g tel que:

b = g . d1

a = g . d2


a, b, d1 , d2 et g sont des nombres entiers.

 

Exemple

 

 

*    Pour caractériser le degré de divisibilité, on a inventé deux nombres spéciaux:

 

PGCD : plus grand commun diviseur.

PPCM: plus petit commun multiple.

 

 

Exemple

 

14 et 15 sont premiers entre eux.

14 = 2             x 7

15 =       3 x 5

PGCD = 1

PPCM = 210

 

 

Deux exemples de calcul

 

 

 

 

 

Suite

*         PPCM

*         PGCD en théorie des nombres

*         PGCD er recherche de nombres premiers

Autour

*         La division en pratique c'est quoi?Débutant

*         La division en résumé c'est quoi?Glossaire

*         Divisibilité par un nombre donné

*         Diviseurs: calculs et facteurs premiers

*         PGCD d'une suite de nombres consécutifs

Voir

*         Des jeux sur les partages

*         Diviseurs: nombres parfaits

*         Fraction continue

*         Jeux et puzzlesIndex

*         L'arithmétique de l'horloger

*         Le calcul mental

*         Nombres Premiers

*         Pseudo Premiers

*         Pseudo Premiers Absolus

*         Théorie des nombresIndex

Cette page

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