BURHAN.

Arithmétique dans ℤ : Exercices corrigés 2BAC Sciences Mathématiques, niveau perfectionnement

Arithmétique dans ℤ : 3 exercices corrigés de maths 2BAC SM, niveau perfectionnement, chacun avec un indice et une correction détaillée. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).

  1. Un chiffrement affine modulo 26

    Perfectionnement

    On numérote les lettres de l'alphabet de 00 à 2525 :

    A B C D E F G H I J K L M
    00 11 22 33 44 55 66 77 88 99 1010 1111 1212
    N O P Q R S T U V W X Y Z
    1313 1414 1515 1616 1717 1818 1919 2020 2121 2222 2323 2424 2525

    Une clé est un couple (a,b)(a, b) d'entiers tels que 1≤a≤251 \leq a \leq 25 et 0≤b≤250 \leq b \leq 25. Pour chiffrer la lettre de numéro xx, on calcule le reste yy de ax+bax + b dans la division par 2626. La lettre chiffrée est celle de numéro yy.

    1. 1.

      Chiffre le mot RESTE avec la clé (15,7)(15, 7).

    2. 2.

      Montre que 15‾\overline{15} est inversible dans Z/26Z\mathbb{Z}/26\mathbb{Z} et détermine son inverse. Déduis-en une formule de déchiffrement : des entiers a′a' et b′b', entre 00 et 2525, tels que, pour tous entiers xx et yy, y≡15x+7 [26]y \equiv 15x + 7 \ [26] équivaille à x≡a′y+b′ [26]x \equiv a'y + b' \ [26].

    3. 3.

      On a reçu le message UJFWCP, chiffré avec la clé (15,7)(15, 7). Déchiffre-le.

    4. 4.

      Avec la clé (13,5)(13, 5), montre que A et C sont chiffrées par la même lettre. Plus généralement, montre qu'avec une clé (a,b)(a, b), deux lettres distinctes ont toujours des chiffrés distincts si et seulement si a∧26=1a \wedge 26 = 1. Combien y a-t-il de telles clés ?

    Notions du cours : Nombres premiers entre eux et théorème de Bézout, Ensemble ℤ/nℤ

  2. Un entier lu en base 7 et en base 9

    Perfectionnement

    On dit qu'un entier naturel nn « se termine par cc en base bb » lorsque cc est le dernier chiffre de son écriture en base bb. On cherche les entiers naturels nn qui se terminent par 44 en base 77 et par 22 en base 99.

    1. 1.

      Montre que le dernier chiffre de l'écriture de nn en base bb est le reste de la division euclidienne de nn par bb. Traduis le problème par un système (S)(S) de deux congruences.

    2. 2.

      Montre que nn vérifie (S)(S) si et seulement si n≡11 [63]n \equiv 11 \ [63].

    3. 3.

      Détermine les entiers nn qui vérifient (S)(S) et qui s'écrivent avec exactement trois chiffres en base 77. Écris chacun d'eux en base 77.

    4. 4.

      Parmi ces entiers, un seul a une écriture en base 77 qui se lit de la même façon dans les deux sens. Lequel ? Écris-le aussi en base 99.

    5. 5.

      Sans liste, montre directement qu'un entier qui s'écrit 4c4‾(7)\overline{4c4}^{(7)}, avec un chiffre cc, vérifie n≡2 [9]n \equiv 2 \ [9] si et seulement si c=0c = 0.

    6. 6.

      Existe-t-il un entier naturel qui se termine par 44 en base 77, par 22 en base 99 et par 11 en base 33 ?

    Notions du cours : Congruences modulo n, Équation diophantienne ax + by = c, Numération en base b

  3. Une infinité de premiers de la forme 4k + 3

    Perfectionnement

    Le but est de prouver qu'il existe une infinité de nombres premiers de la forme 4k+34k + 3, avec kk entier naturel. Les questions sont peu guidées : à toi d'organiser chaque preuve, en nommant les résultats du cours que tu utilises.

    1. 1.

      Montre qu'un nombre premier impair est congru à 11 ou à 33 modulo 44. Montre aussi qu'un produit d'entiers tous congrus à 11 modulo 44 est congru à 11 modulo 44.

    2. 2.

      Soit nn un entier naturel tel que n≥2n \geq 2 et n≡3 [4]n \equiv 3 \ [4]. Montre que nn admet au moins un diviseur premier congru à 33 modulo 44.

    3. 3.

      Suppose par l'absurde qu'il n'existe qu'un nombre fini de premiers de la forme 4k+34k + 3, avec kk entier naturel ; note-les p1,p2,…,psp_1, p_2, \dots, p_s. En étudiant l'entier M=4p1p2⋯ps−1M = 4p_1 p_2 \cdots p_s - 1, aboutis à une contradiction.

    4. 4.

      Illustration. On part de la liste 33, 77, 1111. Calcule l'entier MM correspondant, décompose-le, et repère le premier de la forme 4k+34k + 3 qu'il fournit.

    5. 5.

      La même démarche permet-elle de prouver qu'il existe une infinité de premiers de la forme 4k+14k + 1 ? Examine l'entier 2121, puis dis quelle étape tombe en défaut.

    6. 6.

      Adapte la preuve pour montrer qu'il existe une infinité de nombres premiers de la forme 6k+56k + 5, avec kk entier naturel.

    Notions du cours : Nombres premiers, Congruences modulo n

Réviser le chapitre avec le résumé