Nombres premiers et théorème de Fermat Terminale : 10 exercices corrigés

Le cours de Nombres premiers et théorème de Fermat fournit les critères nécessaires pour mener un test de primalité, décomposer en facteurs premiers et calculer le nombre de diviseurs.

La seconde partie utilise le petit théorème de Fermat pour réduire une puissance modulo p, puis examine ses limites avant un chiffrement affine et une miniature de RSA.

Primalité et factorisation

Justifier les bornes de recherche.

Exercice 1 : Tester un entier

Facile

Étudier la primalité de 221.

  1. Jusqu'où faut-il tester les diviseurs premiers ?
  2. Conclure.
Voir le corrigé
  1. Jusqu'à 221<15\sqrt{221}\lt 15, donc 2, 3, 5, 7, 11 et 13.
  2. 221=13×17221=13\times17, donc 221 n'est pas premier.

Exercice 2 : Décomposition et diviseurs

Moyen

Soit N=23×32×5N=2^3\times3^2\times5.

  1. Calculer N.
  2. Compter ses diviseurs positifs.
Voir le corrigé
  1. N=8×9×5=360N=8\times9\times5=360.
  2. Il y en a (3+1)(2+1)(1+1)=24(3+1)(2+1)(1+1)=24.

Exercice 3 : PGCD par facteurs premiers

Facile

Décomposer 756 et 540.

  1. Donner les décompositions.
  2. Calculer PGCD et PPCM.
Voir le corrigé
  1. 756=22×33×7756=2^2\times3^3\times7 et 540=22×33×5540=2^2\times3^3\times5.
  2. Le PGCD vaut 22×33=1082^2\times3^3=108, et le PPCM vaut 22×33×5×7=37802^2\times3^3\times5\times7=3780.

Exercice 4 : Preuve de l’infinité

Moyen

Supposons qu'il existe seulement p1,…,pnp_1,\ldots,p_n nombres premiers.

  1. Construire un entier contradictoire.
  2. Expliquer la contradiction.
Voir le corrigé
  1. On pose N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1.
  2. Aucun pip_i ne divise N, mais N possède un facteur premier ; ce facteur manque à la liste.

Fermat et codage

Vérifier la primalité et la coprimalité.

Exercice 5 : Réduire un exposant

Moyen

Calculer 21002^{100} modulo 13.

  1. Appliquer Fermat.
  2. Conclure.
Voir le corrigé
  1. 212≡1(mod13)2^{12}\equiv1\pmod{13}.
  2. 100≡4(mod12)100\equiv4\pmod{12}, donc 2100≡16≡3(mod13)2^{100}\equiv16\equiv3\pmod{13}.

Exercice 6 : Cas divisible par p

Moyen

Calculer 26202726^{2027} modulo 13.

  1. Peut-on inverser 26 modulo 13 ?
  2. Calculer directement.
Voir le corrigé
  1. Non, car 13 divise 26.
  2. 26≡0(mod13)26\equiv0\pmod{13}, donc la puissance est congrue à 0.

Exercice 7 : Chiffrement affine

Difficile

On code x∈{0,…,25}x\in\{0,\ldots,25\} par y≡5x+8(mod26)y\equiv5x+8\pmod{26}.

  1. Vérifier que le codage est inversible.
  2. Coder x = 3.
  3. Décoder y = 23.
Indication
Chercher l'inverse de 5 modulo 26.
Voir le corrigé
  1. gcd⁡(5,26)=1\gcd(5,26)=1, et 5−1≡21(mod26)5^{-1}\equiv21\pmod{26}.
  2. y≡5×3+8=23(mod26)y\equiv5\times3+8=23\pmod{26}.
  3. x≡21(23−8)=315≡3(mod26)x\equiv21(23-8)=315\equiv3\pmod{26}.

Exercice 8 : Faux test de primalité

Difficile

On sait que 2340≡1(mod341)2^{340}\equiv1\pmod{341}.

  1. Cette congruence prouve-t-elle que 341 est premier ?
  2. Factoriser 341.
  3. Conclure sur ce type de test.
Indication
Chercher un petit facteur avant de conclure.
Voir le corrigé
  1. Non : la réciproque du petit théorème de Fermat est fausse.
  2. 341=11×31341=11\times31.
  3. Une base qui satisfait la congruence peut produire un pseudo-premier ; un test exact exige d'autres vérifications.

Primalité et chiffrement raisonné

Contrôler les hypothèses avant d'utiliser un théorème ou un code.

Exercice 9 : Certifier un nombre premier

Moyen

Déterminer si 997 est premier.

  1. Justifier la borne des essais.
  2. Effectuer les tests nécessaires.
  3. Conclure.
Voir le corrigé
  1. Il suffit de tester les nombres premiers inférieurs ou égaux à 997<32\sqrt{997}\lt 32.
  2. 997 n'est divisible par aucun des nombres premiers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 et 31.
  3. 997 est donc premier.

Exercice 10 : Miniature de RSA

Difficile

On choisit p=5p=5, q=11q=11, n=55n=55 et l'exposant public e=3e=3.

  1. Calculer φ(n)\varphi(n) et vérifier le choix de e.
  2. Trouver d tel que 3d≡1(mod40)3d\equiv1\pmod{40}.
  3. Chiffrer le message m = 4.
  4. Vérifier le déchiffrement.
Indication
Séparer la construction des clés, le chiffrement et le contrôle du déchiffrement.
Voir le corrigé
  1. φ(55)=(5−1)(11−1)=40\varphi(55)=(5-1)(11-1)=40, et gcd⁡(3,40)=1\gcd(3,40)=1.
  2. On peut prendre d=27d=27, car 3×27=81≡1(mod40)3\times27=81\equiv1\pmod{40}.
  3. c≡43≡64≡9(mod55)c\equiv4^3\equiv64\equiv9\pmod{55}.
  4. Le calcul modulaire donne 927≡4(mod55)9^{27}\equiv4\pmod{55}, donc on retrouve le message.
Partager