CHP 4. PGCD

             CHP  4.              PGCD   de deux entiers naturels  non tous les deux nuls.   BTS1                2014

         1. PROPRIETE:

                 Soient a , b ,c des entiers naturels avec c non nul.

                 Si c divise a et b alors c divise  toute combinaison linéaire u a + v b

                 où u et v sont de entiers relatifs.

                 En particulier  u a + v b peut être  a + b   ou   a - b .   

                 Par exemple:    7 × 6 + 5 × 9 est divisible par 3 car 3 divis 6 et 9    

         2. PGCD de deux entiers naturels  non tous les deux nuls..

                    Soit N et N ' deux entiers naturels  non tous les deux nuls.

                    • Si N = 0 et N ' ≠ 0   alors  N ' est  le PGCD  de N et N '.

                    • Si  N ≠ 0 et N ' ≠ 0   alors leur PGCD est le plus grand entier naturel

                       non nul qui divise chacun d'eux.   

                    Par exemple:   PGCD( 0 ; 42 ) = 42

                                                PGCD( 4 ; 26 )  = 2                

         3. DECOMPOSITION en facteurs premiers d'un entier naturel non nul.

                 Soit N un entier naturel tel que N ≥ 2.

                Il est décomposable en un produit d'un nombre fini de nombres premiers.

                c-à-d

                il existe des nombres premier p1 ,  p2 ,  .....   , pk 

                et des entiers naturels non nuls n1 , n2 , ...  , nk   tels que

                    Dec

               Par exemple:

                48 = 2 × 24 =  2 × 2 ×12 =  2 × 2 × 2 × 6 =  2 × 2 × 2 × 2 × 3 = 24  ×  31

        4. Obtention du PGCD de deux entiers naturels non nuls.

                      Soit  N  et  N ' deux entiers naturels non nuls.

                    • Dans le cas où tels que N ≥ 2  et  N '  ≥ 2.

                         On décompose chacun d'eux en facteurs premiers.

                          •• S'il n'y en a aucun facteur premier commun, leur PGCD est 1.

                         ••Sinon on considère le produit des nombres premiers communs aux deux décompositions

                        affectés du plus petit exposant.   

                   • Dans le cas où N = 1 ou N ' = 1 alors leur PGCD est 1             

         5. EXEMPLE.

                    Soit        N =   22  ×  33 × 54

                    Soit        N '  =   23  ×  53 × 7

                   Les nombres premiers communs sont 2 et 5.

                   Pour l'exposant de 2 on considère 2   et pour celui de  5 on considère 3.

                    PGCD( N , N ' ) =  22   × 53   = 500

                   c-à-d

                                 PGCD( N , N ' ) = 500

        6. ALGORITHME D'EUCLIDE pour obtenir le PGCD de deux entiers naturels non nuls. 

              Soit N et N ' deux entiers naturels non nuls.

                • Soit  N = N '   alors     PGCD( N , N ' ) =  N = N'

               • Soit   N  > N ' .

                      On divise N pa N ' et on note r le reste de cette division.  

                                                  N = N ' × q + r     0 ≤ r < N ' 

                                               Div

                         •• Si r = 0  alors    PGCD( N , N ' ) = N '

                         •• Si r ≠ 0   alors on divise   N ' par r   .

                                                         N ' = r  × q ' + r '     0 ≤ r' < r

                                                    Div3

                                 Même discussion on continue ainsi jusqu'à ce que le reste soit nul.

                          Le dernier reste non nul est le PGCD( N , N ' ).

           7. Exemple:

                    Soit    N = 14    et  N ' =   12

                    N > N '

     14 = 12 × 1  +  2    avec   0 ≤  2 < 12                      12 = 2  × 6  + 0

      Div12            Div2

        Le dernier reste non nul est 2.

                              Conclusion :   PGCD( 14 , 12 ) = 2

          8. NOMBRES  PREMIERS ENTRE EUX .  

            Les entiers naturels N et N ' sont premiers entre eux ssi  PGCD( N , N ' ) = 1              

          9. Exemple:       PGCD( 15 , 26 ) = 1    

                          15 = 3 × 5                  26 = 2 × 13 

                 Aucun nombre premier commun dans les deux décomposition en facteurs premiers.

          10. PROPRIETE.

                 Tout diviseur commun des entiers naturels non nuls N et N ' est un diviseur de PGCD( N , N ' ).

          11. Propriété.

               Soit N et N ' deux entiers naturels non nuls .

                 Il existe  n et n ' deux entiers naturels premiers entre eux  tels que  

                    N = n   ×   PGCD( N , N ' )

                    N ' = n '   ×  PGCD( N , N ' )

        12. Exemple :

                 On a vu que :         PGCD( 14 , 12 ) = 2

                              On a :    14 =   7 ×   PGCD( 14 , 12 )

                                     et     12 =   6  ×  PGCD( 14 , 12 )

                         avec     PGCD( 7 , 6 ) = 1

-----------------------------------------------------------------------------------