Solutions - Exercices sur les nombres premiers - 02

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

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 $\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}}$

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

Remarque

Laisser un commentaire Annuler la réponse