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](https://math-os.com/wp-content/uploads/2017/08/icone-Math-OS-Exos-205x205.png)
![exercice 1 facile](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv1-1-small.png)
Pour commencer :
et de même :
![](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv2-2-small.png)
Soit et soit
sa racine cubique entière.
Supposons que ne possède aucun diviseur
tel que
Montrons que est premier ou produit de deux nombres premiers, en écartant les autres possibilités :
- Déjà,
ne peut pas posséder trois facteurs premiers distincts. En effet, si
sont premiers et divisent
alors
donc
est un diviseur non trivial de
strictement inférieur à
- Supposons maintenant que
avec
et
tels que
Si par exemple
alors
d’où
: contradiction. Même chose en supposant
Donc
- On voit de même que
avec
et
ne tient pas.
Les seules possibilités sont donc :
➣ avec
et
➣ avec
distincts.
En conclusion, est un nombre premier ou bien le produit de deux nombres premiers.
![](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv2-3-small.png)
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 Il suffit d’initialiser une variable à
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 (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}
![](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv2-4-small.png)
Posons, pour tout :
![Rendered by QuickLaTeX.com u_{0}=7\in\mathbb{P}.](https://math-os.com/wp-content/ql-cache/quicklatex.com-0efb50989603efe45693278d2626c620_l3.png)
![Rendered by QuickLaTeX.com n\geqslant1.](https://math-os.com/wp-content/ql-cache/quicklatex.com-09a63f0a250afc8eb6c1afc362624557_l3.png)
![Rendered by QuickLaTeX.com 2^{2}\equiv1\pmod{3}](https://math-os.com/wp-content/ql-cache/quicklatex.com-79f61927447bb699892602f99c25baa7_l3.png)
![Rendered by QuickLaTeX.com u_{n}\geqslant9,](https://math-os.com/wp-content/ql-cache/quicklatex.com-3be31b1a1ec45e1767b51f91b45a3575_l3.png)
![Rendered by QuickLaTeX.com u_{n}\neq3](https://math-os.com/wp-content/ql-cache/quicklatex.com-3f7ea5d58c4fbef4947b312a7873c934_l3.png)
![Rendered by QuickLaTeX.com u_{n}\notin\mathbb{P}.](https://math-os.com/wp-content/ql-cache/quicklatex.com-2051798f393368fc97c85e9bb5b3f7fb_l3.png)
Conclusion : 0 est le seul entier pour lequel
est premier.
![](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv2-5-small.png)
On rappelle (voir l’exercice n° 8 de la fiche n° 1 consacrée aux nombres premiers) que si et
alors :
()
- Pour
ok.
- Supposons que
pour un certain
tel que
Alors, d’après la formule de Pascal :
Noter qu’on a pu utiliserpuisque
![](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv2-6-small.png)
Posons :
![Rendered by QuickLaTeX.com n\geqslant2,](https://math-os.com/wp-content/ql-cache/quicklatex.com-296029041208b868e66a8f6cc2c33dc7_l3.png)
![Rendered by QuickLaTeX.com q](https://math-os.com/wp-content/ql-cache/quicklatex.com-540dac59494482653923dffbd7469e20_l3.png)
![Rendered by QuickLaTeX.com A.](https://math-os.com/wp-content/ql-cache/quicklatex.com-c2c00cacd6762188f63a6b0087f13a39_l3.png)
![Rendered by QuickLaTeX.com r\in\mathbb{N}^{\star}](https://math-os.com/wp-content/ql-cache/quicklatex.com-5e321cfabebc84a1ce1dbcbd7913c293_l3.png)
![Rendered by QuickLaTeX.com q=p_{r}.](https://math-os.com/wp-content/ql-cache/quicklatex.com-1efb9e346602e7d629c2ca24fda21bda_l3.png)
![Rendered by QuickLaTeX.com p_{i}](https://math-os.com/wp-content/ql-cache/quicklatex.com-fdae6cc18477a309ddbd671fc0a92069_l3.png)
![Rendered by QuickLaTeX.com 1\leqslant i\leqslant n](https://math-os.com/wp-content/ql-cache/quicklatex.com-9768e74f7ee2d802339562b1f3b7b6b5_l3.png)
![Rendered by QuickLaTeX.com A,](https://math-os.com/wp-content/ql-cache/quicklatex.com-4c8759187a5ad636c8a504f9b6683a9c_l3.png)
![Rendered by QuickLaTeX.com r\geqslant n+1](https://math-os.com/wp-content/ql-cache/quicklatex.com-d02e3a9eeec59824150afd598514149a_l3.png)
![](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv3-7-small.png)
Si alors
convient, puisque :
![Rendered by QuickLaTeX.com p\geqslant5,](https://math-os.com/wp-content/ql-cache/quicklatex.com-cfd060a298449fd76dc3a46e33d7d056_l3.png)
![Rendered by QuickLaTeX.com p](https://math-os.com/wp-content/ql-cache/quicklatex.com-37f6a1a9a39aa263d588cacc9c82b405_l3.png)
![Rendered by QuickLaTeX.com 2,](https://math-os.com/wp-content/ql-cache/quicklatex.com-cd180f8cff43ce605e826c500a820e7b_l3.png)
![Rendered by QuickLaTeX.com 3](https://math-os.com/wp-content/ql-cache/quicklatex.com-834b2c0db64ba2b43066a4d4b1655736_l3.png)
![Rendered by QuickLaTeX.com 6.](https://math-os.com/wp-content/ql-cache/quicklatex.com-e46ad4ba202c37fdacdcc23a26796b9c_l3.png)
Donc, d’après le petit théorème de Fermat :
![Rendered by QuickLaTeX.com p](https://math-os.com/wp-content/ql-cache/quicklatex.com-37f6a1a9a39aa263d588cacc9c82b405_l3.png)
![Rendered by QuickLaTeX.com 6)](https://math-os.com/wp-content/ql-cache/quicklatex.com-80b2964e330e9c40233244d6d1133375_l3.png)
![Rendered by QuickLaTeX.com n=p-2](https://math-os.com/wp-content/ql-cache/quicklatex.com-7c0a51dc0576544bac50fb9d7fc75228_l3.png)
![](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv3-8-small.png)
D’après la formule de Legendre :
![Rendered by QuickLaTeX.com k\leqslant n_{p}](https://math-os.com/wp-content/ql-cache/quicklatex.com-0620b69ce5e4a5956b68c1f8b9eaa970_l3.png)
![Rendered by QuickLaTeX.com k>n_{p}](https://math-os.com/wp-content/ql-cache/quicklatex.com-82276478468b076f8715f602a493745e_l3.png)
![Rendered by QuickLaTeX.com p^{k}>n](https://math-os.com/wp-content/ql-cache/quicklatex.com-f763e7940c5ac53ed7684ae179d8fa5d_l3.png)
![Rendered by QuickLaTeX.com \left\lfloor \frac{n}{p^{k}}\right\rfloor =0.](https://math-os.com/wp-content/ql-cache/quicklatex.com-bba9d7ad6763ca36ad0236238bb2b794_l3.png)
Comme pour tout
:
![Rendered by QuickLaTeX.com {\displaystyle \lim_{n\rightarrow\infty}n_{p}=+\infty}](https://math-os.com/wp-content/ql-cache/quicklatex.com-ef6b9ad2d847af56c8095d3165f6d181_l3.png)
![Rendered by QuickLaTeX.com n_{p}=o\left(n\right)](https://math-os.com/wp-content/ql-cache/quicklatex.com-7c25ff60a09d83db05e8ff8179a97469_l3.png)
![Rendered by QuickLaTeX.com n\rightarrow\infty;](https://math-os.com/wp-content/ql-cache/quicklatex.com-cd9cd7691250255366491c90a83619e0_l3.png)
![exercice 9 difficile](https://math-os.com/wp-content/uploads/2017/08/TitreExo-Niv3-9-small.png)
Soit un nombre parfait pair, distinct de 6. On sait qu’il existe
tel que :
- le cas
est exclu, puisque
- si
alors
Et si alors
ou bien
ce qui conduit aux deux cas supplémentaires ci-dessous. On va utiliser le fait que :
()
- si
alors
d’après
- si
alors
toujours d’après
On a bien établi que
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 :
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.