INFO TEST du 29 mars 2016

                                       INFO  TEST  du  mardi 29 mars 2016                   TS   spé maths

    EXERCICE  de bac   2016 en Nouvelle Calédonie

                                   Candidats ayant suivi l’enseignement de spécialité 5 points
                   Les parties A et B peuvent être traitées de manière indépendante
      Partie A
            Afin de crypter un message, on utilise un chiffrement affine.
            Chaque lettre de l’alphabet est associée à un nombre entier comme indiqué dans le tableau ci-dessous :
           comme indiqué dans le tableau ci-dessous :   

A     B    C    D    E    F    G    H   I   J    K    L    M     N    O    P   Q    R    S    T    U    V     W    X   Y    Z
0     1      2    3     4     5     6    7   8   9  10  11   12   13   14  15  16  17   18   19  20  21   22  23  24  25
            Soit x le nombre associé à la lettre à coder. 

            On détermine le reste y de la division euclidienne de 7x + 5 par 26,
            puis on en déduit la lettre associée à y (c’est elle qui code la lettre d’origine).

     1.Codons la lettre L. 
           La lettre L correspond à :    x = 11     
           On a :         7 × 11 + 5 = 82  = 26 × 3  + 4     avec 0 ≤ 4  ≤ 26 
           Donc  82  a pour reste 4 dans la division par 26.  

           y = 4 

            Le nombre 4 correspond à E.   

           Conclusion:     la lettre L est codée E.      

     2. a. Montrons que  k ≡ 7x [26] ⇒ 15k ≡ x [26]  pour tout entier relatif k           
         Soit k un entier relatif. 

         On a    k ≡ 7x [26] ⇒   15 k ≡ 15 × 7   x [26]    en  multipliant par 15

                                         Or     15 × 7 = 105 =  4 × 26   +  1  

           Ainsi       k ≡ 7 x [26] ⇒     15 k ≡  4 × 26 x + x  [26]  

          c-à-d        k ≡ 7x  [26]    ⇒   15 k ≡ x [26]     

           Conclusion :    k ≡ 7x   [26] ⇒ 15k ≡ x [26]     pour tout entier relatif k

    b. Montrons la réciproque  :  pour tout  k entier relatif

                              15 k ≡ x [26]    ⇒    k ≡ 7 x [26]

              Soit un  k entier relatif  quelconque

           On a :   15 k ≡ x [26] ⇒    7  × 15 k ≡ 7 x [26]            en multipliant par 7
                         Mais on a vu que      7 × 15  =  4 × 26 + 1                                     

           Ainsi :   15k ≡ x [26] ⇒   4 × 26 k + 1k  ≡ 7 x   [26]

            c-à-d              15k ≡ x [26]    ⇒  k  ≡ 7 x    [26]
            Ainsi    on a l'implication réciproque.   
                      Conclusion:   15 k ≡ x [26]
k ≡ 7x [26]    pour  tout  k entier relatif

     c.   Montrons que :   y ≡ 7x + 5 [26] ⇔   x ≡ 15 y + 3  [26] 

         c-à-d     montrons      y − 5 ≡ 7 x  [26]       x  ≡ 15 ( y − 5 ) + 15 × 5 + 3  [26]

         Ce qui revient à établir      y − 5 ≡ 7 x  [26]       x  ≡ 15 ( y − 5 )   [26]   notée  ( 1 )

                                                                                   sachant     15 × 5 + 3 = 78 = 26 × 3

         Or   on a  montré déjà  que :       k ≡ 7x [26]   ⇔   15 k ≡ x [26]     pour tout entier relatif k                
          Donc aussi en particulier pour      k = y − 5   on obtient l'équivalence souhaitée ( 1 )

                    Conclusion : L'équivalence est prouvée.
      3. Décodons F. 
         Pour décoder une lettre:
         On cherche à quel entier  y  entre 0 et 25 elle correspond
         puis on détermine l'entier  x entre 0 et 25  tel que :      y ≡ 7x + 5  [26]  

                                                                   c-à-d  tel que      x ≡ 15 y + 3 [26]. 

         La lettre F correspond à y = 5 .

          On a :   15 y + 3 =15 × 5 + 3 =   78          

           78 = 26 ×  3  +  0   et    0 ≤ 0 < 26

           78   a pour reste 0 dans la division par 26. 

          Donc x = 0

         L'entier  0 correspond à la lettre A .
         Le décodage de la lettre F donne la lettre A.  

              Conclusion : Le décodage de la lettre F donne la lettre A. 

         Partie B
               On considère les suites (an) et (bn) telles que a0 et b0 sont des entiers compris entre 0 et 25 inclus 
                 et pour tout entier naturel n,
                an+1 = 7an + 5                et    bn+1 = 15 bn + 3                         

                  Montrons que   pour tout entier naturel n :     an =  (   a0 + 5 / 6 ) × 7n  −  5 / 6

              On admet pour la suite du problème que pour tout entier naturel n

               b n =  ( b 0 + 3 / 14 ) × 15n − 3 / 14

               Récurrence sur IN
      • Pour n = 0
                     (  a0 +  5 / 6 ) × 70 − 5 / 6 = a0 + 5 / 6 − 5 / 6 = a0

                   L'égalité est vérifiée pour n = 0

       • Soit n dans IN quelconque.

           Montrons que si l'égalité est vraie pour n alors elle est vraie pour  n + 1.

            Considérons :  a n+ 1  =  7 an + 5  

            On a :          a n =  ( a 0 + 5 / 6 ) × 7n − 5 / 6

           Donc    a n+ 1  = 7 (  ( a 0 + 5 / 6 ) × 7n − 5 / 6  ) + 5

          c-à-d   a n+ 1  =  ( a 0 + 5 / 6 ) × 7n + 1 − 7 × 5 / 6   + 5

                         mais      − 7 × 5 / 6   + 5  = − 35 / 6 + 30 / 6 = − 5 / 6 

            Ainsi :            a n + 1 =  ( a 0 + 5 / 6 ) × 7n + 1  − 5 / 6 

                     C'est l'égalité à l'ordre n + 1.

       Conclusion : L'égalité est prouvée sur IN

    Partie C

             Déchiffrer un message codé avec un chiffrement affine ne pose pas de difficulté (on peut tester les 312
             couples de coefficients possibles). Afin d’augmenter cette difficulté de décryptage, on propose d’utiliser
             une clé qui indiquera pour chaque lettre le nombre de fois où on lui applique le chiffrement affine de la
            partie A. Par exemple pour coder le mot MATH avec la clé 2-2-5-6, on applique « 2 » fois le chiffrement
            affine à la lettre M (cela donne E), « 2 » fois le chiffrement à la lettre A, « 5 » fois le chiffrement à la lettre T
             et enfin « 6 » fois le chiffrement à la lettre H. Dans cette partie, on utilisera la clé 2-2-5-6.
 

          On veut décoder la lettre Q dans le mot IYYQ.
           • Première méthode:   On décode  six fois de suite en remontant à la lettre de départ.
            En effet  lettre cherchée a été codée 6 fois de suite pour donner la lettre Q.           

           On repart chaque fois du x trouvé qui devient un y  pour obtenir  le nouvel x.


       Lettre           Entier   y               15 y + 3            Reste x  dans la division par 26                  Lettre pour x
           Q                   16                243 = 26 × 9 +                   0 ≤  9  < 26                                                 J
           J                     9                 138 = 26 × 5 + 8                    0 ≤   8   < 26                                                I
            I                     8                 123 = 26 × 4 + 19                 0  ≤  19 < 26                                               T
           T                   19                 288 = 26  × 11 +  2              0  ≤   2    <  26                                               C
            C                   2                    33 = 26  × 1 +  7                  0  ≤   7   <  26                                             H
            H                   7                  108 = 26 × 4  +  4                0  ≤     4    < 26                                             E
                     

                x = 4        Conclusion:   la lettre Q se décode en E.
 

      • Deuxième méthode: On utilise la partie B.
          Pour  y on considère   x ≡ 15 y + 3  [26]    avec      0  ≤ x < 26   

          Donc  on applique à y la fonction   y →  15 y + 3

           Puis à  15 y + 3   on applique cette même fonction six fois de suite 

             comme  15( 15 ( 15 ( 15 ( 15 ( 15 y + 3 ) + 3) + 3) + 3 ) + 3) + 3  avec y =16

           Ensuite on doit prendre le reste dans la division par 26.

           Or la suite ( b n ) déjà rencontrée est telle que:

                    b n+ 1 = 15 b n + 3  avec b0  entre 0 et 25

               On décide de  prendre :     b 0 = 16

                     Alors                              b1  = 15 b 0 + 3            

                                                             b2  = 15 b 1 + 3

                                                             ..................

                                                            b6 = 15 b5 + 3  

                    On considère alors le reste de la division de b6 par 26  

                     pour avoir un entier entre 0 et 25. cet entier indiquera la lettre qui décode Q

                      Pour trouver b6   on utilise ce que l'on a admis:

                                             b n =  ( b 0 + 3 / 14 ) × 15n − 3 / 14     pour tout n dans IN

                                                           Ici on a pris b0 = 16

               Pour n = 6      on a             b6 =   ( 16 + 3 / 14 ) × 156 − 3 / 14   

                           c-à-d                        b6 = 184690848 = 26× 7103494  + 4    avec    0 ≤ 4 < 26
           Le reste de la division de 184 690 848 par 26 est 4

                                     4  correspond  à E.
                         Conclusion : Q se décode  en E.

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