Solutions détaillées de neuf exercices sur la notion de nombre premier (fiche 02).
Cliquer ici pour accéder aux énoncés.

icone-math-OS-Exos
exercice 1 facile

Pour commencer :

    \begin{eqnarray*} 2^{18}+1 & = & \left(2^{6}\right)^{3}+1\\ & = & \left(2^{6}+1\right)\left(2^{12}-2^{6}+1\right) \end{eqnarray*}


et de même :

    \begin{eqnarray*} 2^{6}+1 & = & \left(2^{2}\right)^{3}+1\\ & = & \left(2^{2}+1\right)\left(2^{4}-2^{2}+1\right)\\ & = & 5\times13 \end{eqnarray*}

Pour finir :

    \[2^{12}-2^{6}+1=4033=37\times109\]

et donc :

    \[\boxed{2^{18}+1=5\times13\times37\times109}\]

Soit n\geqslant2 et soit A=\left\lfloor \sqrt[3]{n}\right\rfloor sa racine cubique entière.

Supposons que n ne possède aucun diviseur d tel que 1<d\leqslant A.

Montrons que n est premier ou produit de deux nombres premiers, en écartant les autres possibilités :

  • Déjà, n ne peut pas posséder trois facteurs premiers distincts. En effet, si p<q<r sont premiers et divisent n, alors p^{3}<pqr<n donc p est un diviseur non trivial de n, strictement inférieur à A.
  • Supposons maintenant que n=p^{\alpha}q^{\beta} avec p,q\in\mathbb{P}, p<q et \alpha,\beta\geqslant1 tels que \alpha+\beta\geqslant3. Si par exemple \alpha\geqslant2 alors p^{3}<p^{2}q\leqslant n d’où p<A : contradiction. Même chose en supposant \beta\geqslant2. Donc \alpha=\beta=1.
  • On voit de même que n=p^{\alpha} avec p\in\mathbb{P} et \alpha\geqslant3 ne tient pas.

Les seules possibilités sont donc :

n=p^{\alpha} avec p\in\mathbb{P} et \alpha\in\left\{1,2\right\}

n=pq avec p,q\in\mathbb{P} distincts.

En conclusion, n est un nombre premier ou bien le produit de deux nombres premiers.

L’algorithme standard de primalité consiste à chercher d’éventuels diviseurs jusqu’à la racine carrée entière incluse. Il est expliqué en détail dans cet article ainsi que dans cette vidéo.

Sa transcription en Python est alors assez directe :

def ppfp(n):
    if n < 2:
        return None
    elif n % 2 == 0:
        return 2
    d = 3
    isprime = True
    while (d * d <= n and isprime):
        if n % d == 0:
            isprime = False
        else:
            d += 2
    if isprime:
        return n
    else:
        return d

A partir de là, il est facile de dresser la liste des facteurs premiers d’un entier n\geqslant2. Il suffit d’initialiser une variable à n, de le diviser par son PPFP et de recommencer … jusqu’à ce qu’on atteigne 1.

C’est ce que fait la fonction dfp (pour Décomposition en Facteurs Premiers) ci-dessous. La liste renvoyée contient la liste des facteurs premiers de n (avec d’éventuelles répétitions bien entendu).

def dfp(n):
    L = []
    x = n
    while x > 1:
        p = ppfp(x)
        L.append(p)
        x = x // p
    return L

Exemple :

>>> dfp (1571427)
[3, 3, 3, 11, 11, 13, 37]

Ce n’était pas demandé, mais on peut obtenir à partir de là une décomposition en facteurs premiers « compacte », c’est-à-dire une liste de couples (facteur premier, exposant). L’implémentation ci-dessous repose sur l’utilisation d’un dictionnaire :

dfpc(n):
     L = dfp(n)
     L.reverse()
     couples = {}
     while L != []:
         q = L.pop()
         if q in couples:
             couples[q] = couples[q] + 1
         else:
             couples[q] = 1
     return couples

Exemple :

>>> dfpc (1571427)
{3: 3, 11: 2, 13: 1, 37: 1}

Posons, pour tout n\in\mathbb{N} :

    \[u_{n}=2^{2^{n}}+5\]

Clairement u_{0}=7\in\mathbb{P}. Supposons maintenant que n\geqslant1. Comme 2^{2}\equiv1\pmod{3} :

    \[2^{2^{n}}=\left(2^{2}\right)^{2^{n-1}}\equiv1\pmod{3}\]

et donc :

    \[u_{n}\equiv0\pmod{3}\]

Comme u_{n}\geqslant9, alors en particulier u_{n}\neq3 et donc u_{n}\notin\mathbb{P}.

Conclusion : 0 est le seul entier n pour lequel u_{n} est premier.

On rappelle (voir l’exercice n° 8 de la fiche n° 1 consacrée aux nombres premiers) que si p\in\mathbb{P} et 1\leqslant k\leqslant p-1, alors :

(\star)   \[\binom{p}{k}\equiv0\pmod{p}\]

Montrons par récurrence (finie) que :

    \[\boxed{\forall k\in\llbracket0,p-1\rrbracket,\,\binom{p-1}{k}\equiv\left(-1\right)^{k}\pmod{p}}\]

  • Pour k=0, ok.
  • Supposons que \binom{p-1}{k}\equiv\left(-1\right)^{k}\pmod{p} pour un certain k tel que 0\leqslant k\leqslant p-2. Alors, d’après la formule de Pascal :

        \begin{eqnarray*}\binom{p-1}{k+1} & = & \binom{p}{k+1}-\binom{p-1}{k}\\ & \underset{\star}{\equiv} & -\binom{p-1}{k}\\ & \underset{\text{HR}}{\equiv} & -\left(-1\right)^{k}\\ & = & \left(-1\right)^{k+1}\pmod{p} \end{eqnarray*}


    Noter qu’on a pu utiliser \left(\star\right) puisque 1\leqslant k+1\leqslant p-1.

Posons :

    \[A=\left(\prod_{i=1}^{n}p_{i}\right)-1\]

Comme n\geqslant2, alors :

    \[A\geqslant2\times3-1=5\geqslant2\]

Soit q un facteur premier de A. Il existe r\in\mathbb{N}^{\star} tel que q=p_{r}. Comme aucun des p_{i} pour 1\leqslant i\leqslant n ne divise A, alors r\geqslant n+1 et donc :

    \[p_{n+1}\leqslant p_{r}\leqslant N\]

d’où finalement :

    \[\boxed{p_{n+1}<\prod_{i=1}^{n}p_{i}}\]

Si p\in\left\{ 2,3\right\} , alors n=2 convient, puisque :

    \[2^{2}+3^{2}+6^{2}-1=48\]

Si p\geqslant5, alors p est premier avec chacun des entiers 2, 3 et 6.

Donc, d’après le petit théorème de Fermat :

    \[2^{p-1}\equiv1\pmod{p}\]

    \[3^{p-1}\equiv1\pmod{p}\]

    \[6^{p-1}\equiv1\pmod{p}\]

donc :

    \[6\left(2^{p-2}+3^{p-2}+6^{p-2}-1\right)\equiv3+2+1-6=0\pmod{p}\]

et finalement (comme p est premier avec 6), on voit que n=p-2 convient.

D’après la formule de Legendre :

    \[v_{p}\left(n!\right)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor\]

En fait, on peut se limiter aux termes d’indices k\leqslant n_{p} avec :

    \[n_{p}=\left\lfloor \frac{\ln\left(n\right)}{\ln\left(p\right)}\right\rfloor\]

puisque si k>n_{p} alors p^{k}>n et donc \left\lfloor \frac{n}{p^{k}}\right\rfloor =0.

Comme t-1<\left\lfloor t\right\rfloor \leqslant t pour tout t\in\mathbb{R} :

    \[n\left(\sum_{k=1}^{n_{p}}\frac{1}{p^{k}}\right)-n_{p}<v_{p}\left(n!\right)\leqslant n\left(\sum_{k=1}^{n_{p}}\frac{1}{p^{k}}\right)\]

Or {\displaystyle \lim_{n\rightarrow\infty}n_{p}=+\infty} et donc :

    \[\lim_{n\rightarrow\infty}\sum_{k=1}^{n_{p}}\frac{1}{p^{k}}=\frac{1}{p-1}\]

et aussi n_{p}=o\left(n\right) lorsque n\rightarrow\infty; donc :

    \[\boxed{v_{p}\left(n!\right)\sim\frac{n}{p-1}}\]

exercice 9 difficile

Soit n un nombre parfait pair, distinct de 6. On sait qu’il existe p\in\mathbb{P} tel que :

    \[n=2^{p-1}\left(2^{p}-1\right)\qquad\text{et}\qquad2^{p}-1\in\mathbb{P}\]

  • le cas p=2 est exclu, puisque n\neq6.
  • si p=3, alors n=28\equiv1\pmod{9}

Et si p\in\mathbb{P}-\left\{ 2,3\right\} , alors p\equiv1\pmod{6} ou bien p\equiv5\pmod{6}, ce qui conduit aux deux cas supplémentaires ci-dessous. On va utiliser le fait que :

(\heartsuit)   \[\forall k\in\mathbb{N},\thinspace2^{k}\equiv2^{k\,\text{mod}\,6}\pmod{9}\]

ce qui résulte simplement du fait que :

    \[2^{6}=64\equiv1\pmod{9}\]

  • si p\equiv1\mod6, alors n\equiv1\pmod{9} d’après \left(\heartsuit\right)
  • si p\equiv5\pmod{6}, alors n\equiv2^{4}\left(2^{5}-1\right)=16\times31\equiv7\times4=28\equiv1\pmod{9} toujours d’après \left(\heartsuit\right)

On a bien établi que n\equiv1\pmod{9}.

Remarque

Comme tout entier naturel est congru modulo 9 à la somme de ses chiffres, ceci explique l’observation faite par Tartaglia (1506 – 1559) qu’en itérant le calcul de la somme des chiffres décimaux d’un nombre parfait pair, autre que 6, on aboutisse toujours à 1 :

    \[28\rightarrow10\rightarrow1\]

    \[496\rightarrow19\rightarrow10\rightarrow1\]

    \[8\thinspace128\rightarrow19\rightarrow10\rightarrow1\]

    \[33\thinspace550\thinspace336\rightarrow28\rightarrow10\rightarrow1\]

    \[8\thinspace589\thinspace869\thinspace056\rightarrow64\rightarrow10\rightarrow1\]


Si un point n’est pas clair ou vous paraît insuffisamment détaillé, n’hésitez pas à poster un commentaire ou à me joindre via le formulaire de contact.

Partager cet article

Laisser un commentaire