← Cours de mathématiques

Chapitre 10 — Nombres premiers

Maths Expertes · Math@mine · Exercices

Ch9 📖 Cours ✏️ Exercices Ch11

I. Primalité et décomposition

Exercice 1

Tests de primalité

  1. Montrer que 101 est premier.
  2. Décomposer \(2\,310\) en facteurs premiers.
  3. Trouver tous les diviseurs de \(360 = 2^3 \times 3^2 \times 5\). Combien y en a-t-il ?
  4. Montrer que si \(2^n - 1\) est premier, alors \(n\) est premier.
Correction

a. \(\sqrt{101} < 11\). On teste 2, 3, 5, 7 : \(101/2=50.5\), \(101/3=33.7\), \(101/5=20.2\), \(101/7=14.4\). Aucun ne divise, donc 101 est premier.

b. \(2310 = 2\times1155 = 2\times3\times385 = 2\times3\times5\times77 = 2\times3\times5\times7\times11\).

c. Les diviseurs sont \(2^a\times3^b\times5^c\) avec \(0\le a\le3\), \(0\le b\le2\), \(0\le c\le1\). Nombre de diviseurs : \((3+1)(2+1)(1+1)=24\).

d. Si \(n=ab\) avec \(1\lt a,b\), alors \(2^n-1=(2^a)^b-1\). Or \(x^b-1=(x-1)(x^{b-1}+\cdots+1)\), donc \(2^a-1\mid 2^n-1\). Et \(2^a-1\gt 1\), donc \(2^n-1\) est composé. Contraposée : si \(2^n-1\) est premier, alors \(n\) est premier.

Exercice 2

PGCD et PPCM par factorisation

Donner la décomposition en facteurs premiers, puis calculer \(\pgcd\) et \(\ppcm\) :

  1. \(a = 2^4 \times 3^2 \times 7\) et \(b = 2^2 \times 3^3 \times 5\).
  2. \(a = 1\,260\) et \(b = 3\,024\).
  3. Vérifier que \(\pgcd(a,b)\times\ppcm(a,b) = ab\) dans les deux cas.
Correction

a. \(\pgcd = 2^{\min(4,2)}\times3^{\min(2,3)}\times5^0\times7^0 = 2^2\times3^2=36\). \(\ppcm=2^4\times3^3\times5\times7=15120\). Vérif : \(36\times15120=544320\) et \(ab=2^6\times3^5\times5\times7=544320\). ✓

b. \(1260=2^2\times3^2\times5\times7\) et \(3024=2^4\times3^3\times7\). \(\pgcd=2^2\times3^2\times7=252\). \(\ppcm=2^4\times3^3\times5\times7=15120\). \(252\times15120=3810240=1260\times3024\). ✓

II. Infinité des premiers et résultats classiques

Exercice 3

Variantes de la preuve d’Euclide

  1. Montrer qu’il existe une infinité de premiers de la forme \(4k+3\) (i.e. congrus à 3 mod 4).
  2. Soit \((p, p+2)\) une paire de premiers jumeaux avec \(p > 3\). Montrer que \(p\equiv 5\pmod 6\) (et donc \(p+2\equiv 1\pmod 6\)).
  3. Montrer que pour tout \(n\), il existe \(n\) entiers consécutifs tous composés. (Indication : considérer \((n+1)!+2, (n+1)!+3, \ldots\))
Correction

a. Supposons qu’il n’y en ait qu’un nombre fini : \(p_1=3, p_2, \ldots, p_k\) (tous \(\equiv3\pmod4\)). Posons \(N = 4p_2\cdots p_k - 1\). Alors \(N\equiv -1\equiv 3\pmod4\). Aucun des \(p_i\) ne divise \(N\) : pour \(i\ge 2\), \(N\equiv -1\pmod{p_i}\) ; et \(N\equiv -1\equiv 2\pmod 3\). Donc tous les facteurs premiers de \(N\) sont impairs et différents de \(p_2,\ldots,p_k\). S’ils étaient tous \(\equiv 1\pmod 4\), leur produit le serait aussi (un produit d’entiers \(\equiv 1\pmod 4\) reste \(\equiv 1\pmod 4\)), contredisant \(N\equiv 3\pmod 4\). Donc \(N\) admet un facteur premier \(\equiv 3\pmod 4\), nouveau premier non dans la liste : contradiction. ∎

b. Comme \(p > 3\) est premier, \(p\) n’est divisible ni par 2 ni par 3, donc \(p\equiv 1\) ou \(p\equiv 5\pmod 6\). Si \(p\equiv 1\pmod 6\), alors \(p+2\equiv 3\pmod 6\), donc \(3\mid p+2\). Or \(p+2 > 5\) est premier, contradiction. Donc \(p\equiv 5\pmod 6\), et \(p+2\equiv 7\equiv 1\pmod 6\). ∎

c. Pour \(2 \le k \le n+1\), l’entier \((n+1)! + k\) est divisible par \(k\) (car \(k\mid(n+1)!\) et \(k\mid k\)), et \((n+1)!+k > k\), donc il est composé. On a bien \(n\) entiers consécutifs composés.

Exercice 4

Propriétés liées aux premiers

  1. Montrer que si \(p\) est premier impair, alors \(p^2 \equiv 1 \pmod{8}\).
  2. Montrer que tout entier \(n \ge 2\) peut s’écrire \(n = 2^k m\) avec \(m\) impair et \(k \ge 0\).
  3. Soit \(p\) un premier et \(0 < k < p\). Montrer que \(p \mid \binom{p}{k}\).
  4. En déduire que \((a+b)^p \equiv a^p + b^p \pmod{p}\) pour tous entiers \(a, b\) (freshman’s dream).
Correction

a. \(p\) impair premier, donc \(p=2m+1\) avec \(m\ge1\). \(p^2=(2m+1)^2=4m^2+4m+1=4m(m+1)+1\). Comme \(m(m+1)\) est produit de deux consécutifs, il est pair : \(m(m+1)=2t\). Donc \(p^2=8t+1\equiv1\pmod8\). ✓

b. Par récurrence ou par décomposition : dans la factorisation de \(n\), la puissance de 2 est \(k=v_2(n)\ge0\), et \(m=n/2^k\) est impair par construction.

c. On a \(k!\,(p-k)!\,\binom{p}{k} = p!\). Comme \(p\) est premier et que \(p\mid p!\), on en déduit que \(p\) divise le membre de gauche. Or \(k! = 1\cdot 2\cdots k\) est un produit de facteurs tous strictement inférieurs à \(p\) : aucun n’est divisible par \(p\), donc \(\pgcd(k!, p)=1\). De même \(\pgcd((p-k)!,p)=1\), donc \(\pgcd(k!\,(p-k)!,\,p)=1\). Par le lemme de Gauss appliqué à \(p \mid k!(p-k)!\,\binom{p}{k}\), on conclut \(p\mid\binom{p}{k}\). ∎

d. Par la formule du binôme : \((a+b)^p = \sum_{k=0}^{p}\binom{p}{k}a^k b^{p-k}\). Pour \(0\lt k\lt p\), on a \(p\mid\binom{p}{k}\) d’après (c), donc chaque terme intermédiaire est nul modulo \(p\). Il ne reste que les termes \(k=0\) et \(k=p\) :

\((a+b)^p \equiv \binom{p}{0}\,a^0 b^p + \binom{p}{p}\,a^p b^0 = b^p + a^p \pmod p.\)

Ainsi \((a+b)^p \equiv a^p + b^p \pmod p\). C’est le « rêve du débutant » (freshman’s dream) : il est faux dans \(\mathbb{Z}\) mais vrai modulo un nombre premier. ∎

Exercice 5

Indicatrice d’Euler

L’indicatrice d’Euler \(\varphi(n)\) est le nombre d’entiers dans \(\{1,\ldots,n\}\) premiers avec \(n\).

  1. Calculer \(\varphi(p)\) pour \(p\) premier.
  2. Calculer \(\varphi(p^k)\) pour \(p\) premier et \(k\ge1\).
  3. Admettre la formule multiplicative \(\varphi(mn)=\varphi(m)\varphi(n)\) si \(\pgcd(m,n)=1\). Calculer \(\varphi(30)\) et \(\varphi(100)\).
  4. Retrouver le petit théorème de Fermat comme cas particulier du théorème d’Euler : \(a^{\varphi(n)}\equiv1\pmod n\) si \(\pgcd(a,n)=1\).
Correction

a. Parmi \(1,\ldots,p\), tous sauf \(p\) sont premiers avec \(p\). Donc \(\varphi(p)=p-1\).

b. Les entiers de \(\{1,\ldots,p^k\}\) non premiers avec \(p^k\) sont exactement les multiples de \(p\) : \(p, 2p, \ldots, p^{k-1}\cdot p\), soit \(p^{k-1}\) multiples. Donc \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\).

c. \(30=2\times3\times5\) : \(\varphi(30)=\varphi(2)\varphi(3)\varphi(5)=1\times2\times4=8\). \(100=2^2\times5^2\) : \(\varphi(100)=\varphi(4)\varphi(25)=2\times20=40\).

d. Pour \(p\) premier et \(p\nmid a\) : \(\pgcd(a,p)=1\) et \(\varphi(p)=p-1\). Le théorème d’Euler donne \(a^{p-1}\equiv1\pmod p\), qui est exactement le petit théorème de Fermat.

Exercice 6

Irrationalité par les premiers

  1. Montrer que \(\sqrt{p}\) est irrationnel pour tout premier \(p\).
  2. Montrer que \(\log_2 3\) est irrationnel.
  3. Montrer que si \(n\) n’est pas un carré parfait, alors \(\sqrt{n}\) est irrationnel.
Correction

a. Supposons \(\sqrt{p}=a/b\) avec \(\pgcd(a,b)=1\). Alors \(a^2=pb^2\), donc \(p\mid a^2\), donc \(p\mid a\) (lemme de Gauss), soit \(a=pk\). Alors \(p^2k^2=pb^2\), \(pk^2=b^2\), donc \(p\mid b^2\), \(p\mid b\). Contradiction avec \(\pgcd(a,b)=1\).

b. Supposons \(\log_2 3=p/q\) (rationnel). Alors \(2^{p/q}=3\), soit \(2^p=3^q\). Mais \(2^p\) est pair et \(3^q\) est impair : impossible.

c. ⚠ Outil hors programme On utilise la valuation \(p\)-adique (au-delà du BO Expertes, mais accessible) : pour un premier \(p\) et un entier \(m\geq 1\), on note \(v_p(m)\) l’exposant de \(p\) dans la décomposition de \(m\). Cette valuation vérifie \(v_p(mn)=v_p(m)+v_p(n)\), donc en particulier \(v_p(a^2)=2\,v_p(a)\) est toujours paire.

Supposons \(\sqrt n\) rationnel, \(\sqrt n = a/b\) avec \(a,b\in\mathbb{N}^*\). Alors \(a^2 = n\,b^2\). Soit \(p\) un premier dont l’exposant \(\alpha = v_p(n)\) est impair (un tel \(p\) existe car \(n\) n’est pas un carré parfait). En appliquant \(v_p\) à l’égalité \(a^2 = n\,b^2\) :

\(2\,v_p(a) = v_p(n) + 2\,v_p(b) = \alpha + 2\,v_p(b).\)

Le membre de gauche est pair, mais le membre de droite est impair (somme d’un impair \(\alpha\) et d’un pair \(2v_p(b)\)). Contradiction. Donc \(\sqrt n\) est irrationnel. ∎

Exercice 7

Problème de synthèse — Infinité de premiers de la forme 6k+1 ⚠ Hors programme BO — Niveau CPGE / concours

Cet exercice utilise des outils au-delà du programme BO 2020 Maths Expertes : polynôme cyclotomique \(\Phi_6\), ordre multiplicatif (§10.6 hors programme), petit théorème de Fermat (au programme). À considérer comme une ouverture culturelle vers les classes préparatoires.

On veut montrer qu’il existe une infinité de premiers \(\equiv 1 \pmod{6}\). C’est un cas particulier du théorème de Dirichlet sur la progression arithmétique (1837), admis dans le cours.

  1. Montrer que si \(p\) est premier \(\ge 5\), alors \(p\equiv1\) ou \(p\equiv5\pmod6\).
  2. Montrer que si \(n\equiv1\pmod6\) et \(m\equiv1\pmod6\), alors \(nm\equiv1\pmod6\).
  3. (Étape clé, technique) Supposons qu’il n’existe qu’un nombre fini de premiers \(p_1,\ldots,p_k\equiv1\pmod6\). Posons \(P = p_1\cdots p_k\) et \(N = P^2 - P + 1\). On vérifiera l’identité utile \((P+1)\,N = P^3 + 1\) (par développement direct, c’est aussi le « polynôme cyclotomique \(\Phi_6\) » évalué en \(P\), notion vue en classes préparatoires). Montrer : (i) \(N\) n’est divisible ni par 2, ni par 3, ni par aucun \(p_i\) ; (ii) tout facteur premier \(q\) de \(N\) vérifie \(P^6 \equiv 1\pmod q\) (utiliser l’identité \((P+1)\,N = P^3+1\), donc \(P^3\equiv -1\pmod q\)) ; (iii) montrer que l’ordre de \(P\) modulo \(q\) est exactement \(6\) ; (iv) par le petit théorème de Fermat (section 10.5), \(6\) divise \(q-1\), soit \(q\equiv 1\pmod 6\). Contradiction.
Correction

a. \(p\ge5\) premier, donc \(p\) n’est divisible ni par 2 ni par 3. Les restes mod 6 possibles pour un entier non divisible par 2 ou 3 sont 1 et 5.

b. \((6a+1)(6b+1)=36ab+6a+6b+1=6(6ab+a+b)+1\equiv1\pmod6\). ✓

c. Posons \(P=p_1\cdots p_k\) et \(N=P^2-P+1\). On observe l’identité \((P+1)\,N = P^3+1\), donc tout facteur premier \(q\) de \(N\) vérifie \(q\mid P^3+1\), soit \(P^3 \equiv -1\pmod q\), et donc \(P^6\equiv 1\pmod q\).

(i) \(N\) n’est divisible ni par 2, ni par 3, ni par aucun \(p_i\).

  • Modulo 2 : \(P\) est impair (produit de premiers tous \(\geq 7\)), donc \(P^2\) impair, \(P^2 - P\) pair (impair − impair), donc \(N = P^2 - P + 1\) est impair. Ainsi \(2\nmid N\).
  • Modulo 3 : \(P\equiv 1\pmod 3\), donc \(N\equiv 1-1+1=1\pmod 3\). Donc \(3\nmid N\).
  • Modulo \(p_i\) : \(P\equiv 0\pmod{p_i}\), donc \(N\equiv 0-0+1=1\pmod{p_i}\). Donc \(p_i\nmid N\).

(ii) Soit \(q\) un facteur premier de \(N\). On vient de voir que \(q\notin\{2,3,p_1,\ldots,p_k\}\). De plus \(P^6\equiv 1\pmod q\), donc l’ordre multiplicatif \(d=\text{ord}_q(P)\) divise 6, soit \(d\in\{1,2,3,6\}\).

(iii) Élimination des cas \(d\in\{1,2,3\}\).

  • Si \(d=1\) : \(P\equiv 1\pmod q\), donc \(N\equiv \Phi_6(1)=1\pmod q\), donc \(q\mid 1\) — impossible.
  • Si \(d=2\) : \(P\equiv -1\pmod q\), donc \(N\equiv \Phi_6(-1)=1+1+1=3\pmod q\), donc \(q\mid 3\), donc \(q=3\) — exclu.
  • Si \(d=3\) : par définition de l’ordre, \(P^3\equiv 1\pmod q\). Mais l’hypothèse \(q\mid N\) combinée à l’identité \((P+1)\,N = P^3+1\) donne \(P^3 \equiv -1\pmod q\). On a donc simultanément \(P^3\equiv 1\) et \(P^3\equiv -1 \pmod q\), soit \(2\equiv 0\pmod q\), donc \(q\mid 2\), donc \(q=2\) — exclu (puisque \(N\) est impair par (i)).

(iv) Conclusion. Donc \(d=6\). Par le petit théorème de Fermat, \(P^{q-1}\equiv 1\pmod q\), donc \(6=d\) divise \(q-1\), soit \(q\equiv 1\pmod 6\). Comme \(q\notin\{p_1,\ldots,p_k\}\), \(q\) est un nouveau premier \(\equiv 1\pmod 6\) : contradiction. ∎

Remarque : cette preuve utilise le polynôme cyclotomique \(\Phi_6(X)=X^2-X+1\), la notion d’ordre multiplicatif (complément section 10.6) et le petit théorème de Fermat (section 10.5). Exercice de synthèse exigeant.

Exercice 8

📜 La démarche historique d’Ibn al-Haytham — Critère de primalité ⭐ Approfondissement

Vers l’an 1000, Ibn al-Haytham (Bassora, puis Le Caire) étudie les congruences et formule des observations précurseures reliant la primalité à la factorielle. Le résultat sera redécouvert et démontré par Leibniz (1682), puis énoncé par John Wilson et publié par Waring en 1770. Dans cet exercice, on reproduit la démarche expérimentale d’Ibn al-Haytham.
📜 Lire l’article complet → Ibn al-Haytham et Al-Farisi  ·  📄 Rashed 1980 (source historique)

Partie A — Observer (démarche d’Ibn al-Haytham).

  1. Compléter le tableau suivant pour \(n \in \{1, 2, 3, 4, 5, 6\}\) :
    \(n\) \(n!\) \(n! + 1\) \(n+1\) divise-t-il \(n!+1\) ? \(n+1\) est-il premier ?
    1à compléter
    ……
  2. Quelle conjecture pouvez-vous faire sur le lien entre « \(n+1\) divise \(n!+1\) » et « \(n+1\) premier » ?

Partie B — Formuler (théorème de Wilson).

  1. En posant \(p = n+1\), reformuler la conjecture sous la forme : « \(p\) est premier \(\iff (p-1)! \equiv \underline{\phantom{xx}} \pmod{p}\) ». Quelle est la valeur à compléter ?
  2. Tester sur \(p = 11\) : calculer \(10!\), puis déterminer son reste modulo 11. L’énoncé est-il vérifié ?

Partie C — Appliquer.

  1. Sans calculer \(12!\) entièrement, déterminer le reste de \(12!\) modulo 13. (Indication : \(13\) est premier.)
  2. Al-Farisi (XIIIe siècle) notait que le critère est « théoriquement parfait mais pratiquement inutilisable ». Pourquoi ? Combien de chiffres environ compte \(100!\,\) ?
Correction

a. Tableau :

\(n\)\(n!\)\(n!+1\)\(n+1 \mid n!+1\) ?\(n+1\) premier ?
112oui (2∣2)oui (2)
223oui (3∣3)oui (3)
367non (4∤7)non (4 = 2×2)
42425oui (5∣25)oui (5)
5120121non (6∤121, 121=11²)non (6 = 2×3)
6720721oui (7∣721, 721=7×103)oui (7)

b. Conjecture : « \(n+1\) divise \(n!+1\) si et seulement si \(n+1\) est premier. » La colonne « divisible » et la colonne « premier » coïncident parfaitement.

c. Avec \(p = n+1\) : \(p\) est premier \(\iff p \mid (p-1)! + 1 \iff (p-1)! \equiv \boxed{-1} \pmod{p}\). C’est le théorème de Wilson.

d. \(10! = 3\,628\,800\). On peut calculer directement : \(3\,628\,800 = 11 \times 329\,890 + 10 = 11 \times 329\,891 - 1\), donc \(10! \equiv -1 \equiv 10 \pmod{11}\). ✓ (conforme à Wilson puisque 11 est premier)

e. \(13\) est premier, donc par Wilson : \(12! \equiv -1 \equiv \mathbf{12} \pmod{13}\). (Inutile de calculer \(12! = 479\,001\,600\).)

f. Le critère est parfait théoriquement (équivalence exacte : primalité ⇔ congruence) mais inutilisable pratiquement : \(100! \approx 9{,}33 \cdot 10^{157}\) — soit environ 158 chiffres. Pour un \(p\) à 20 chiffres, \((p-1)!\) dépasse largement les capacités de calcul. Les tests de primalité modernes (Miller–Rabin, AKS) sont bien plus efficaces.

Maths Expertes — Math@mine