EXERCICE 1 : restes et congruences.

                         Utilisation des congruences.                 TS   Spé maths      janvier 2016  

 

            EXERCICE 1 

           Déterminer le reste de la division euclidienne de 14123  par 3.

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

           REPONSE:

               Si vous prenez votre calculatrice il y aura "ERR:OVERFLOW",

               c'est-à-dire un dépassement de capacité.

                Nous allons procéder en plusieurs étapes.

           1. Nous allons nous occuper d'abord du 14.

              Regardons, d'abord , s'il est  possible de trouver un plus petit entier naturel

                 non nul  k tel que 14 ≡ 1 [ 3 ]

               Testons pour cela les premiers entiers naturels non nuls:

         •      141 ≡ 2  [ 3 ]              car  14 = 2 + 3 x 4

         •    Ainsi :  14 ≡  22    [ 3 ]           c-à-d    14  ≡  4  [ 3 ]    Mais 14 = 1 + 3

              Donc   14 2  ≡  1  [ 3 ]  

              L'entier naturel non nul le plus petit qui convient est  k = 2.

           2 . Ecrivons à présent  la division euclidienne de 123  par k = 2.

                  On a :     123 = 2 x 61 + 1      avec      0 ≤ 1 < 2

                  Le reste de la division euclidienne de 123 par 2 est 1.

          3. Synthétisons nos deux observations.

                  On a vu d'abord que:          14 2  ≡  1  [ 3 ]  

                 On va essayer de faire apparaître en exposant de 14 le 123

                 Ainsi                      ( 14 2 ) 61  ≡  161  [ 3 ]  

                  c-à-d                         14 2 x 61  ≡  1  [ 3 ]    

                    Donc :                    14 2 x 61 x 14  ≡  1 14  [ 3 ]  

                   c-à-d                         14 2 x 61+1  ≡ 14    [ 3 ]

                    c-à-d                        14 2 x 61+1  ≡  2  [ 3 ]    avec      0 ≤  2 < 3  

                    c-à-d                       14123    ≡  2    [ 3 ]    avec      0 ≤  2 < 3

                   Nous pouvons conclure:       

            Conclusion :  Le reste de la division de 14123 par 3 est 2.

                On a pu obtenir ce reste sans même calculer  14 123  .

             grace aux propriétés des congruences et à la division euclidienne.

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