Aller au contenu

Feuille d'exercices sur les nombres premiers

Définition et critère d'arrêt

Exercice 1

Sans calculatrice, à l'aide de divisions successives et du critère d'arrêt, déterminer si les entiers suivants sont premiers ou non.

\(97\) ; \(109\) ; \(117\) ; \(271\) ; \(317\) ; \(323\) ; \(401\) ; \(419\) ; \(437\) ; \(527\) ; \(719\)

Exercice 2 : Vrai-Faux

  1. Proposition 1 : Il existe une valeur de \(n \in \mathbb{N}\) tel que \(2n^2+n-10\) est premier.

  2. Proposition 2 : Il existe une valeur de \(n \in \mathbb{N}\) tel que \(2n^2 + 7n + 6\) est premier.

  3. Proposition 3 : Pour \(n \in \mathbb{N}\) et \(n > 5\), \(n^2-3n-10\) n'est jamais premier.

On cherchera à factoriser les quantités.

Exercice 3

Dans les Inédits de Marcel Pagnol, l'écrivain indique que, pour tout \(n\) entier impair \(n > 1\), le nombre \(N = n + (n + 2) + n(n + 2)\) est premier.

Qu'en pensez-vous ?

Exercice 4

Soit \(p\) un nombre premier et deux entiers \(n_1\) et \(n_2\) tels que \(n_1 = p + 1 000\) et \(n_2 = p + 2 000\).

  1. En raisonnant modulo \(3\), montrer que la seule valeur possible de \(p\) pour que \(n_1\) et \(n_2\) soient des nombres premiers est \(3\).

  2. Peut-on avoir \(n_1\) et \(n_2\) premiers ?

Théorème de Gauss et nombres premiers

Exercice 5

\(p\) est premier et \(p \geqslant 5\).

  1. DĂ©montrer que \((p^2-1)\) est divisible par \(3\) et par \(8\).

  2. En déduire que \((p^2-1)\) est divisible par \(24\).

Exercice 6

\(p\) est premier et \(p \geqslant 7\).

  1. DĂ©montrer que \((p^4-1)\) est divisible par \(3\) et par \(5\).

  2. DĂ©montrer que \((p^4-1)\) est divisible par \(16\).

  3. En déduire que \((p^4-1)\) est divisible par \(240\).

Exercice 7

\(p > 3\) est un nombre premier.

  1. Quels sont les restes possibles dans la division de \(p\) par \(12\) ?

  2. Prouver que \(p^2 + 11\) est divisible par \(12\).

Exercice 8

Soit \(n \geqslant 1\).

DĂ©montrer que \((30n + 7)\) n'est pas la somme de deux nombres premiers.

Exercice 9

Soit \(p\) un nombre premier et \(a\), \(b\) \(\in \mathbb{N}\).

Montrer que si \(p\) divise \(a\) et \(a^2 + b^2\) alors \(p\) divise \(b\).

Exercice 10

  1. DĂ©composer en produit de facteurs premiers : \(6468\) et \(16380\).

  2. En déduire \(pgcd(6468,16380)\).

Exercice 11

À l'aide de décompositions en facteurs premiers, déterminer \((a, b) \in \mathbb{N}^2\) tel que :

\(\dfrac{a}{b}=\dfrac{5292}{5544}\) et \(a + b = 903\)

Exercice 12

  1. a. Quelle est la condition sur les puissances des facteurs premiers d'un carré ?

    b. Trouver un nombre de trois chiffres qui soit un carré parfait divisible par \(56\).

  2. Trouver les diviseurs de \(84\), puis résoudre dans \(\mathbb{N}\) : \(x(x+1)(2x+1)=84\)

Exercice 13

Cet exercice a pour but de déterminer par combien de zéros se termine \(1~000!\).

On rappelle que : \(1~000!=1 \times 2 \times 3 \times...\times 1~000\).

  1. Montrer qu'il existe \(p, q \in \mathbb{N}^*\) et un entier \(N\) premier avec \(10\) tels que :

    \[1~000! = 2^p \times 5^q \times N\]

  2. a. Combien y a-t-il de nombres inférieurs ou égaux à \(1~000\) divisible par \(5\) ? divisible par \(5^2\) ? divisible par \(5^3\)? divisible par \(5^4\) ?

    b. En déduire alors que \(q = 249\).

  3. Montrer que \(p > q\) et que \(q\) est le nombre cherché.

Exercice 14

  1. À l'aide d'une décomposition en facteurs premiers, déterminer le nombre de diviseurs de : \(2025\) et \(1575\).

  2. En déduire la liste des diviseurs de \(2025\) et \(1575\).

Exercice 15

\(\alpha\) et \(\beta\) sont deux entiers naturels et \(n=2^{\alpha}3^{\beta}\)

Le nombre de diviseurs de \(n^2\) est le triple du nombre de diviseurs de \(n\).

  1. Prouver que \((\alpha-1)(\beta-1)=3\)

  2. En déduire \(n\)

Exercice 16

Un entier \(n\) a \(5\) diviseurs et \(n-16\) est le produit de deux nombres premiers.

  1. Prouver que \(n = p^4\), avec \(p\) premier.

  2. Écrire \(n-16\) sous forme d'un produit de trois facteurs dépendant de \(p\).

  3. En déduire la valeur de \(n\).

Petit théorème de Fermat

Exercice 17

  1. Montrer que pour tout \(n \in \mathbb{N}\), \(3^{6n}-1\) est divisible par \(7\).

  2. Soit \(p\) un nombre premier différent de \(3\).

    DĂ©montrer que pour tout \(n \in \mathbb{N}\), \(3^{n+p}-3^{n+1}\) est divisible par \(p\).

Exercice 18

Soit \(n \in \mathbb{N}\) et \(a = n^5 - n\).

  1. Montrer que \(a\) est divisible par \(5\).

  2. Montrer que \(a = n(n^2 - 1)(n^2 + 1)\) puis que a est divisible par \(2\) et \(3\).

    Pourquoi \(a\) est-il divisible par \(30\) ?

Exercice 19

  1. Montrer que \(4^{28} - 1\) est divisible par \(29\).

  2. Montrer que pour tout \(n\), \(4^n-1\) est divisible par \(3\).

  3. Montrer que pour tout \(k\), \(4^{4k}-1\) est divisible par \(5\) et par \(17\).

  4. En déduire quatre diviseurs premiers de \(4^{28}-1\).

Exercice 20

Soit \(n \in \mathbb{N}^*\). On note \(a = n^{13}-n\).

  1. Montrer que \(a\) est divisible par \(13\) et \(7\).

  2. En déduire que \(a\) est divisible par \(182\).

Exercice 21

  1. Montrer que, pour tout \(a \in \mathbb{N}\) : \(a^{31}-a \equiv 0 [62]\).

  2. Montrer que, pour tout \(a, n \in \mathbb{N}\) : \(a^{30+n}-a^n \equiv 0 [62]\).

Exercice 22

  1. Soit \(p\) un nombre premier supérieur à 2.

    Montrer que \(p\) divise \(1+2+2^2+...+2^{p-2}\).

  2. Est-ce que \(97\) divise la somme \(S\) telle que \(S =\sum\limits_{n=1}^{98}n^{96}\) ?

Exercice 23

Soit \(p\) un nombre premier.

  1. Montrer que si \(p\) divise \(3^p + 1\) alors \(p\) divise \(4\).

  2. Trouver \(p\) tel que \(p\) divise \(3^p + 1\).

Exercice 24

  1. VĂ©rifier que \(761\) est un nombre premier.

  2. L'entier n est un naturel composé de 760 chiffres tous égaux a 9

    a. Calculer \(n + 1\).

    b. Montrer que \(n\) est divisible par \(761\).

Exercice 25

Soit \(p\) un nombre premier et \(a\), \(b\), \(n\) des entiers relatifs.

  1. Montrer que si \(na \equiv nb [p]\) avec \(n \not\equiv 0 [p]\) alors : \(a \equiv b [p]\).

  2. Montrer que si \(a\) est premier avec \(p\) et \(n\) un multiple de \(p-1\) alors : \(a^n \equiv 1 [p]\).

  3. Montrer que si \(a\) est premier avec \(p\) alors il existe \(b\) tel que : \(ab \equiv 1 [p]\).

    En déduire que tout entier non nul \(a < p\) possède un inverse inférieur à \(p\) modulo p.

Exercice 26

Soit \(a\) un entier naturel pair non nul. Soit \(p\) un nombre premier divisant \(a^2 + 1\).

  1. Montrer que \(p\) est de la forme \(4n + 1\) ou \(4n + 3\).

  2. On suppose que \(p\) est de la forme \(4n + 3\).

    a. Montrer que \(p\) ne divise pas \(a\).

    b. Montrer que \((a^4)^n \times a^2 \equiv 1 [p]\).

    c. En déduire une contradiction.

  3. Conclure.

Exercice 27

Le nom du système de cryptage RSA provient des initiales des noms de ses inventeurs américains en 1977 : Ronald Rivest (informaticien), Adi Shamir (informaticien) et Leaonard Adleman (mathématicien).

Partie A : Arithmétique du système RSA

Soit \(p\) et \(q\) deux nombres premiers impairs distincts. On pose : \(n = pq\) et \(m = (p - 1)(q - 1)\) et \(e\) tel que : \(1 < e < m\) avec \(e\) premier avec \(m\).

  1. Montrer qu'il existe un entier \(d\) unique tel que : \(1 \leqslant d < m\) et \(ed \equiv 1 [m]\).

  2. Prouver que pour tout \(a \in \mathbb{N}\), \(a^{ed} \equiv a [n]\).

  3. On choisit \(p = 3\), \(q = 11\) et \(e = 7\). Calculer d

Partie B Envoi d'un message

Alice veut transmettre un message à Bob. Pour cela Bob diffuse à tout le monde (donc à Alice) les nombres \(n\) et \(e\) (clé publique). Il garde pour lui les nombres \(p\) et \(q\) (clé privé) qui lui permettent de calculer \(d\) et déchiffrer un message.

Bob rend publique : \(n = 33\) et \(e = 7\).

Alice veut envoyer Ă  Bob le mot : SALUT. Elle transforme les \(5\) lettres en nombres :

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

Alice code ces nombres avec la fonction « trappe » de Bob : \(b = f_B(a) \equiv a^e[n]\).

Ainsi pour la lettre S : \(a_1 = 18 \to 18^7 \equiv 6 [33]\), on obtient alors \(b_1 = 6\).

  1. Rentrer cette fonction en Python puis vérifier qu'Alice envoie à Bob les nombres suivants : \(06\) - \(00\) - \(11\) - \(26\) - \(13\)

  2. Bob décode avec sa fonction « trappe inverse » : \(a = f_B^{-1}(b) \equiv b^d [n]\)

    Expliquer pourquoi cette fonction \(f_B^{-1}\) permet de déchiffrer le message d'Alice.

  3. La clé privée de Bob est \(p = 3\) et \(q = 11\).

    Il reçoit un deuxième message d'Alice avec les nombres :

    \(14\) - \(20\) - \(08\) - \(12\) - \(02\) - \(09\) - \(00\) - \(01\) - \(11\) - \(16\).

    Rentrer la fonction inverse en Python puis décoder le message d'Alice.

Partie C Authentification

Le but est de montrer comment Bob peut être sûr de recevoir un message d'Alice.

Alice dispose également d'une clé publique (fonction trappe \(f_A\)) et d'une clé privée (fonction trappe inverse \(f_A^{-1}\)).

Alice envoie Ă  Bob un message contenant :

  • ce qu'elle a Ă  lui dire,
  • une double signature : \(A, f_A^{-1}(A)\).

Comment Bob peut-il s'assurer que le message vient bien d'Alice ?

Remarque : La clé publique \((n,e)\) permet à "tout public" de transmettre un message à Bob. La clé personnelle \((p, q)\) n'est connue que de Bob et lui permet d'être le seul à pouvoir déchiffrer le message en calculant \(d\).

La sécurité du système réside dans la construction de nombre premier \(p\) et \(q\) très grands (300 chiffres) et la difficulté de décomposer le nombre \(n\) en produit de 2 nombres premiers.