Terminale maths expertes

Arithmétique : nombres premiers et cryptographie — 20 exercices

Rechercher et démontrer des propriétés de nombres premiers et appliquer l'arithmétique à de petits problèmes de chiffrement.

L'essentiel à retenir

  • Un nombre premier p≥2p\ge2 n'a pour diviseurs positifs que 11 et pp.
  • Pour tester la primalité de nn, il suffit d'examiner les diviseurs premiers ≤n\le\sqrt n.
  • La décomposition unique en facteurs premiers permet de dénombrer les diviseurs.
  • Les congruences fournissent un cadre simple pour étudier le chiffrement par décalage ou l'idée de RSA.

Exercice 1 — Décomposition en facteurs premiers de 60

Étudier l'entier 60.
  1. Le décomposer en produit de puissances de nombres premiers.
  2. Déterminer son nombre de diviseurs positifs.
  3. Expliquer comment on construit tous ses diviseurs.
Corrigé détaillé
1. En divisant successivement par les nombres premiers, on obtient 60=22×31×51\boxed{60=2^{2}\times3^{1}\times5^{1}}. 2. Un diviseur positif choisit indépendamment un exposant entre 0 et kk pour chaque facteur premier. Le nombre de possibilités est le produit des (k+1)(k+1), soit 12\boxed{12}. 3. Les diviseurs se construisent par tous les produits des puissances admissibles de ces premiers.

Exercice 2 — Décomposition en facteurs premiers de 84

Étudier l'entier 84.
  1. Le décomposer en produit de puissances de nombres premiers.
  2. Déterminer son nombre de diviseurs positifs.
  3. Expliquer comment on construit tous ses diviseurs.
Corrigé détaillé
1. En divisant successivement par les nombres premiers, on obtient 84=22×31×71\boxed{84=2^{2}\times3^{1}\times7^{1}}. 2. Un diviseur positif choisit indépendamment un exposant entre 0 et kk pour chaque facteur premier. Le nombre de possibilités est le produit des (k+1)(k+1), soit 12\boxed{12}. 3. Les diviseurs se construisent par tous les produits des puissances admissibles de ces premiers.

Exercice 3 — Décomposition en facteurs premiers de 90

Étudier l'entier 90.
  1. Le décomposer en produit de puissances de nombres premiers.
  2. Déterminer son nombre de diviseurs positifs.
  3. Expliquer comment on construit tous ses diviseurs.
Corrigé détaillé
1. En divisant successivement par les nombres premiers, on obtient 90=21×32×51\boxed{90=2^{1}\times3^{2}\times5^{1}}. 2. Un diviseur positif choisit indépendamment un exposant entre 0 et kk pour chaque facteur premier. Le nombre de possibilités est le produit des (k+1)(k+1), soit 12\boxed{12}. 3. Les diviseurs se construisent par tous les produits des puissances admissibles de ces premiers.

Exercice 4 — Décomposition en facteurs premiers de 126

Étudier l'entier 126.
  1. Le décomposer en produit de puissances de nombres premiers.
  2. Déterminer son nombre de diviseurs positifs.
  3. Expliquer comment on construit tous ses diviseurs.
Corrigé détaillé
1. En divisant successivement par les nombres premiers, on obtient 126=21×32×71\boxed{126=2^{1}\times3^{2}\times7^{1}}. 2. Un diviseur positif choisit indépendamment un exposant entre 0 et kk pour chaque facteur premier. Le nombre de possibilités est le produit des (k+1)(k+1), soit 12\boxed{12}. 3. Les diviseurs se construisent par tous les produits des puissances admissibles de ces premiers.

Exercice 5 — Test de primalité de 97

L'entier 97 est-il premier ?
  1. Énoncer la borne jusqu'à laquelle tester les diviseurs.
  2. Effectuer les divisions nécessaires.
  3. Conclure avec une justification.
Corrigé détaillé
1. Si un entier composé 97 a deux facteurs non triviaux, l'un est ≤97\le\sqrt{97}, donc il suffit de tester les nombres premiers jusqu'à cette racine. 2. Les nombres premiers à tester sont 2,3,5,7 ; aucun ne divise 97. 3. Ainsi 97 est premier\boxed{97\ \text{est}\ premier}.

Exercice 6 — Test de primalité de 91

L'entier 91 est-il premier ?
  1. Énoncer la borne jusqu'à laquelle tester les diviseurs.
  2. Effectuer les divisions nécessaires.
  3. Conclure avec une justification.
Corrigé détaillé
1. Si un entier composé 91 a deux facteurs non triviaux, l'un est ≤91\le\sqrt{91}, donc il suffit de tester les nombres premiers jusqu'à cette racine. 2. On trouve 91=7\times13, avec deux facteurs entiers supérieurs à 1. 3. Ainsi 91 est composeˊ\boxed{91\ \text{est}\ composé}.

Exercice 7 — Test de primalité de 101

L'entier 101 est-il premier ?
  1. Énoncer la borne jusqu'à laquelle tester les diviseurs.
  2. Effectuer les divisions nécessaires.
  3. Conclure avec une justification.
Corrigé détaillé
1. Si un entier composé 101 a deux facteurs non triviaux, l'un est ≤101\le\sqrt{101}, donc il suffit de tester les nombres premiers jusqu'à cette racine. 2. Les nombres premiers à tester sont 2,3,5,7 ; aucun ne divise 101. 3. Ainsi 101 est premier\boxed{101\ \text{est}\ premier}.

Exercice 8 — Test de primalité de 121

L'entier 121 est-il premier ?
  1. Énoncer la borne jusqu'à laquelle tester les diviseurs.
  2. Effectuer les divisions nécessaires.
  3. Conclure avec une justification.
Corrigé détaillé
1. Si un entier composé 121 a deux facteurs non triviaux, l'un est ≤121\le\sqrt{121}, donc il suffit de tester les nombres premiers jusqu'à cette racine. 2. On trouve 121=11\times11, avec deux facteurs entiers supérieurs à 1. 3. Ainsi 121 est composeˊ\boxed{121\ \text{est}\ composé}.

Exercice 9 — Factorielle et nombres premiers — pour n=3

Posons N=3!+1N=3!+1.
  1. Calculer NN.
  2. Montrer qu'aucun entier kk, avec 2≤k≤32\le k\le3, ne divise NN.
  3. Expliquer la conséquence sur ses facteurs premiers.
Corrigé détaillé
1. 3!=6, donc N=6+1=7N=6+1=\boxed{7}. 2. Tout entier kk entre 2 et 3 divise 3!, donc N≡1(modk)N\equiv1\pmod k : aucun ne divise NN. 3. Tout diviseur premier de NN est strictement supérieur à 3. Attention : NN n'est pas forcément premier ; c'est ce raisonnement qui fonde la preuve d'Euclide de l'infinitude des nombres premiers.

Exercice 10 — Factorielle et nombres premiers — pour n=4

Posons N=4!+1N=4!+1.
  1. Calculer NN.
  2. Montrer qu'aucun entier kk, avec 2≤k≤42\le k\le4, ne divise NN.
  3. Expliquer la conséquence sur ses facteurs premiers.
Corrigé détaillé
1. 4!=24, donc N=24+1=25N=24+1=\boxed{25}. 2. Tout entier kk entre 2 et 4 divise 4!, donc N≡1(modk)N\equiv1\pmod k : aucun ne divise NN. 3. Tout diviseur premier de NN est strictement supérieur à 4. Attention : NN n'est pas forcément premier ; c'est ce raisonnement qui fonde la preuve d'Euclide de l'infinitude des nombres premiers.

Exercice 11 — Factorielle et nombres premiers — pour n=5

Posons N=5!+1N=5!+1.
  1. Calculer NN.
  2. Montrer qu'aucun entier kk, avec 2≤k≤52\le k\le5, ne divise NN.
  3. Expliquer la conséquence sur ses facteurs premiers.
Corrigé détaillé
1. 5!=120, donc N=120+1=121N=120+1=\boxed{121}. 2. Tout entier kk entre 2 et 5 divise 5!, donc N≡1(modk)N\equiv1\pmod k : aucun ne divise NN. 3. Tout diviseur premier de NN est strictement supérieur à 5. Attention : NN n'est pas forcément premier ; c'est ce raisonnement qui fonde la preuve d'Euclide de l'infinitude des nombres premiers.

Exercice 12 — Factorielle et nombres premiers — pour n=6

Posons N=6!+1N=6!+1.
  1. Calculer NN.
  2. Montrer qu'aucun entier kk, avec 2≤k≤62\le k\le6, ne divise NN.
  3. Expliquer la conséquence sur ses facteurs premiers.
Corrigé détaillé
1. 6!=720, donc N=720+1=721N=720+1=\boxed{721}. 2. Tout entier kk entre 2 et 6 divise 6!, donc N≡1(modk)N\equiv1\pmod k : aucun ne divise NN. 3. Tout diviseur premier de NN est strictement supérieur à 6. Attention : NN n'est pas forcément premier ; c'est ce raisonnement qui fonde la preuve d'Euclide de l'infinitude des nombres premiers.

Exercice 13 — Chiffrement de César — décalage 3

On code les lettres par A=0,…,Z=25A=0,\ldots,Z=25 et on chiffre xx en x+3(mod26)x+3\pmod{26}.
  1. Chiffrer le mot MATH.
  2. Donner la fonction de déchiffrement.
  3. Vérifier le mot obtenu.
Corrigé détaillé
1. Les codes de MATH sont (12,0,19,7)(12,0,19,7). Ajouter 3 modulo 26 donne (15,3,22,10), soit PDWK\boxed{\text{PDWK}}. 2. Pour déchiffrer, on soustrait 3 modulo 26 : x↦x−3(mod26)x\mapsto x-3\pmod{26}. 3. En appliquant cette soustraction au mot chiffré, on retrouve MATH.

Exercice 14 — Chiffrement de César — décalage 5

On code les lettres par A=0,…,Z=25A=0,\ldots,Z=25 et on chiffre xx en x+5(mod26)x+5\pmod{26}.
  1. Chiffrer le mot MATH.
  2. Donner la fonction de déchiffrement.
  3. Vérifier le mot obtenu.
Corrigé détaillé
1. Les codes de MATH sont (12,0,19,7)(12,0,19,7). Ajouter 5 modulo 26 donne (17,5,24,12), soit RFYM\boxed{\text{RFYM}}. 2. Pour déchiffrer, on soustrait 5 modulo 26 : x↦x−5(mod26)x\mapsto x-5\pmod{26}. 3. En appliquant cette soustraction au mot chiffré, on retrouve MATH.

Exercice 15 — Chiffrement de César — décalage 7

On code les lettres par A=0,…,Z=25A=0,\ldots,Z=25 et on chiffre xx en x+7(mod26)x+7\pmod{26}.
  1. Chiffrer le mot MATH.
  2. Donner la fonction de déchiffrement.
  3. Vérifier le mot obtenu.
Corrigé détaillé
1. Les codes de MATH sont (12,0,19,7)(12,0,19,7). Ajouter 7 modulo 26 donne (19,7,0,14), soit THAO\boxed{\text{THAO}}. 2. Pour déchiffrer, on soustrait 7 modulo 26 : x↦x−7(mod26)x\mapsto x-7\pmod{26}. 3. En appliquant cette soustraction au mot chiffré, on retrouve MATH.

Exercice 16 — Chiffrement de César — décalage 11

On code les lettres par A=0,…,Z=25A=0,\ldots,Z=25 et on chiffre xx en x+11(mod26)x+11\pmod{26}.
  1. Chiffrer le mot MATH.
  2. Donner la fonction de déchiffrement.
  3. Vérifier le mot obtenu.
Corrigé détaillé
1. Les codes de MATH sont (12,0,19,7)(12,0,19,7). Ajouter 11 modulo 26 donne (23,11,4,18), soit XLES\boxed{\text{XLES}}. 2. Pour déchiffrer, on soustrait 11 modulo 26 : x↦x−11(mod26)x\mapsto x-11\pmod{26}. 3. En appliquant cette soustraction au mot chiffré, on retrouve MATH.

Exercice 17 — Initiation au chiffrement RSA — exemple 1

On choisit deux premiers p=3p=3 et q=11q=11, puis un exposant public e=3e=3.
  1. Calculer N=pqN=pq et φ(N)=(p−1)(q−1)\varphi(N)=(p-1)(q-1).
  2. Chercher dd tel que ed≡1(modφ(N))ed\equiv1\pmod{\varphi(N)}.
  3. Chiffrer le message entier m=4m=4 via c≡me(modN)c\equiv m^e\pmod N, puis vérifier le déchiffrement.
Corrigé détaillé
1. N=3×11=33N=3\times11=33, φ(N)=(3−1)(11−1)=20\varphi(N)=(3-1)(11-1)=20. 2. On vérifie 3\times7\equiv1\pmod{20}, donc l'exposant privé peut être d=7d=7. 3. c≡43≡31(mod33)c\equiv4^{3}\equiv\boxed{31}\pmod{33}. Le calcul inverse donne 31^{7}\equiv4\pmod{33} : le message initial 4 est retrouvé. Il s'agit d'un exemple pédagogique, pas d'un chiffrement sûr avec de si petits paramètres.

Exercice 18 — Initiation au chiffrement RSA — exemple 2

On choisit deux premiers p=5p=5 et q=11q=11, puis un exposant public e=3e=3.
  1. Calculer N=pqN=pq et φ(N)=(p−1)(q−1)\varphi(N)=(p-1)(q-1).
  2. Chercher dd tel que ed≡1(modφ(N))ed\equiv1\pmod{\varphi(N)}.
  3. Chiffrer le message entier m=7m=7 via c≡me(modN)c\equiv m^e\pmod N, puis vérifier le déchiffrement.
Corrigé détaillé
1. N=5×11=55N=5\times11=55, φ(N)=(5−1)(11−1)=40\varphi(N)=(5-1)(11-1)=40. 2. On vérifie 3\times27\equiv1\pmod{40}, donc l'exposant privé peut être d=27d=27. 3. c≡73≡13(mod55)c\equiv7^{3}\equiv\boxed{13}\pmod{55}. Le calcul inverse donne 13^{27}\equiv7\pmod{55} : le message initial 7 est retrouvé. Il s'agit d'un exemple pédagogique, pas d'un chiffrement sûr avec de si petits paramètres.

Exercice 19 — Initiation au chiffrement RSA — exemple 3

On choisit deux premiers p=7p=7 et q=11q=11, puis un exposant public e=7e=7.
  1. Calculer N=pqN=pq et φ(N)=(p−1)(q−1)\varphi(N)=(p-1)(q-1).
  2. Chercher dd tel que ed≡1(modφ(N))ed\equiv1\pmod{\varphi(N)}.
  3. Chiffrer le message entier m=5m=5 via c≡me(modN)c\equiv m^e\pmod N, puis vérifier le déchiffrement.
Corrigé détaillé
1. N=7×11=77N=7\times11=77, φ(N)=(7−1)(11−1)=60\varphi(N)=(7-1)(11-1)=60. 2. On vérifie 7\times43\equiv1\pmod{60}, donc l'exposant privé peut être d=43d=43. 3. c≡57≡47(mod77)c\equiv5^{7}\equiv\boxed{47}\pmod{77}. Le calcul inverse donne 47^{43}\equiv5\pmod{77} : le message initial 5 est retrouvé. Il s'agit d'un exemple pédagogique, pas d'un chiffrement sûr avec de si petits paramètres.

Exercice 20 — Initiation au chiffrement RSA — exemple 4

On choisit deux premiers p=5p=5 et q=13q=13, puis un exposant public e=5e=5.
  1. Calculer N=pqN=pq et φ(N)=(p−1)(q−1)\varphi(N)=(p-1)(q-1).
  2. Chercher dd tel que ed≡1(modφ(N))ed\equiv1\pmod{\varphi(N)}.
  3. Chiffrer le message entier m=9m=9 via c≡me(modN)c\equiv m^e\pmod N, puis vérifier le déchiffrement.
Corrigé détaillé
1. N=5×13=65N=5\times13=65, φ(N)=(5−1)(13−1)=48\varphi(N)=(5-1)(13-1)=48. 2. On vérifie 5\times29\equiv1\pmod{48}, donc l'exposant privé peut être d=29d=29. 3. c≡95≡29(mod65)c\equiv9^{5}\equiv\boxed{29}\pmod{65}. Le calcul inverse donne 29^{29}\equiv9\pmod{65} : le message initial 9 est retrouvé. Il s'agit d'un exemple pédagogique, pas d'un chiffrement sûr avec de si petits paramètres.

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 minSoutien Maths expertes