Nombres a-fortement-probablement-premier
Bonjour,
J'ignore si ce résultat est connu depuis bien longtemps ou si je fais fausse route mais il me semble que :
Tout entier naturel $n$ de la forme $n=(2p)^{2^{a+1}p^b}+1$ est $2p$-fortement-probablement-premier pour tout entier naturel $a$ et $b$ et pour tout entier impair $p$.
Une petite tentative de démo pour justifier ce résultat :
Etape 1 : Montrons que $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-probablement-premier
Un nombre entier naturel $n$ est $r$-probablement-premier ssi
$r^{n-1} \equiv 1 [n]$
$r$ est premier avec $n$
1-1/ Mq $r^{n-1} \equiv 1 [n]$
Posons $r=(2p)$ et $n=(2p)^{2^{a+1}.p^b}+1=(2p)^m+1$ avec $a$ et $b$ des entiers naturels et $p$ un entier impair.
Notons $m={2^{a+1}.p^b}$, il vient :
$r^{n-1} =(2p)^{(2p)^m}=(2p)^{\frac{(2p)^m}{m}m}=((2p)^m)^{\frac{(2p)^m}{m}}=((2p)^m)^{\frac{2^m.p^m}{m}}=((2p)^m)^{\frac{2^m.p^m}{{2^{a+1}p^b}}}=((2p)^m)^{2^{m-a-1}.p^{m-b}}=((2p)^m)^{2.(2^{m-a-2}.p^{m-b})}=((2p)^m)^{2.K}\equiv (-1)^{2.K}[(2p)^m+1]\equiv 1 [(2p)^m+1]$ avec $K$ un entier naturel qui existe pour toutes valeurs de $a$ et $b$.
1-2/ Mq $r$ est premier avec $n$
Si $r=2*p$ divise $n$ alors $n$ est divisible par $2$ ou par $p$ or
$n=(2p)^m+1=2^m.p^m+1=2(2^{m-1}.p^m)+1$ est un entier impair donc non divisible par $2$.
D'autre part, $n=(2p)^m+1=2^m.p^m+1=p(p^{m-1}.2^m)+1$ n'est pas divisible par $p$.
1-3/ Conclusion
$(2p)^{n-1} \equiv 1 [n]$ et $n$ est premier avec $(2p)$ donc $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-probablement-premier pour tout entier naurel $a$ et $b$
Etape 2 : Montrons que $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-fortement-probablement-premier
Un nombre entier naturel $n$ est $f$-fortement-probablement-premier ssi
(1) En écrivant $n-1=2^d.q$ avec $q$ impair et $d$ entier, on a $f^q \equiv 1 [n]$
ou (2) s'il existe un entier $i$ tel que $0<=i<d$ et $f^{q.2^i}\equiv -1 [n]$
2-1/ Mq $f^q \not\equiv 1 [n]$ (1) n'est jamais vraie
Posons $f=(2p)$ et rappelons que $n=(2p)^m+1$
$n-1=(2p)^m=2^m.p^m=2^m.q$ avec $q=p^m$ impair, il vient $f^q=(2p)^{p^m}=(2p)^{\frac{p^m}{m}.m} = ((2p)^m)^{\frac{p^m}{2^{a+1}.p^b}}=((2p)^m)^{\frac{p^{m-b}}{2^{a+1}}}=((2p)^m)^{K'}\equiv (-1)^{K'} [n]$ mais $K'$ n'est pas un entier donc $(2p)^q \not\equiv 1 [n]$
2-2/ Mq il existe toujours un entier $i$ compris entre $0$ et $d$ tel que $f^{q.2^i}\equiv -1 [n]$ (2) est toujours vraie
$f^{q.2^i}=(2p)^{2^i.p^m}=(2p)^{\frac{2^i.p^m}{m}.m}=((2p)^m)^{\frac{2^i.p^m}{2^{a+1}.p^b}}=((2p)^m)^{2^{i-a-1}.p^{m-b}}\equiv (-1)^{K"}[n]\equiv -1 [n]$ si $K"$ est impair or $K"=2^{i-a-1}.p^{m-b}$ n'est pas divisible par $2$ si $i-a-1=0$. Cette condition est assurée lorsque $i=a+1$
$i=a+1$ est positif pour tout entier naturel $a$
De plus, $i=a+1<m$ et rappelons que $n-1=(2p)^m=2^m.p^m=2^d.q$ avec $q$ impair
Par identification, $d=m$ et nous venons de voir que $0<i=a+1<m$ donc $0<i<d$
2-3/ Conclusion
Tout entier naturel de la forme $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-probablement-premier et $(2p)$-fortement-probablement-premier[/quote]
J'ignore si ce résultat est connu depuis bien longtemps ou si je fais fausse route mais il me semble que :
Tout entier naturel $n$ de la forme $n=(2p)^{2^{a+1}p^b}+1$ est $2p$-fortement-probablement-premier pour tout entier naturel $a$ et $b$ et pour tout entier impair $p$.
Une petite tentative de démo pour justifier ce résultat :
Etape 1 : Montrons que $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-probablement-premier
Un nombre entier naturel $n$ est $r$-probablement-premier ssi
$r^{n-1} \equiv 1 [n]$
$r$ est premier avec $n$
1-1/ Mq $r^{n-1} \equiv 1 [n]$
Posons $r=(2p)$ et $n=(2p)^{2^{a+1}.p^b}+1=(2p)^m+1$ avec $a$ et $b$ des entiers naturels et $p$ un entier impair.
Notons $m={2^{a+1}.p^b}$, il vient :
$r^{n-1} =(2p)^{(2p)^m}=(2p)^{\frac{(2p)^m}{m}m}=((2p)^m)^{\frac{(2p)^m}{m}}=((2p)^m)^{\frac{2^m.p^m}{m}}=((2p)^m)^{\frac{2^m.p^m}{{2^{a+1}p^b}}}=((2p)^m)^{2^{m-a-1}.p^{m-b}}=((2p)^m)^{2.(2^{m-a-2}.p^{m-b})}=((2p)^m)^{2.K}\equiv (-1)^{2.K}[(2p)^m+1]\equiv 1 [(2p)^m+1]$ avec $K$ un entier naturel qui existe pour toutes valeurs de $a$ et $b$.
1-2/ Mq $r$ est premier avec $n$
Si $r=2*p$ divise $n$ alors $n$ est divisible par $2$ ou par $p$ or
$n=(2p)^m+1=2^m.p^m+1=2(2^{m-1}.p^m)+1$ est un entier impair donc non divisible par $2$.
D'autre part, $n=(2p)^m+1=2^m.p^m+1=p(p^{m-1}.2^m)+1$ n'est pas divisible par $p$.
1-3/ Conclusion
$(2p)^{n-1} \equiv 1 [n]$ et $n$ est premier avec $(2p)$ donc $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-probablement-premier pour tout entier naurel $a$ et $b$
Etape 2 : Montrons que $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-fortement-probablement-premier
Un nombre entier naturel $n$ est $f$-fortement-probablement-premier ssi
(1) En écrivant $n-1=2^d.q$ avec $q$ impair et $d$ entier, on a $f^q \equiv 1 [n]$
ou (2) s'il existe un entier $i$ tel que $0<=i<d$ et $f^{q.2^i}\equiv -1 [n]$
2-1/ Mq $f^q \not\equiv 1 [n]$ (1) n'est jamais vraie
Posons $f=(2p)$ et rappelons que $n=(2p)^m+1$
$n-1=(2p)^m=2^m.p^m=2^m.q$ avec $q=p^m$ impair, il vient $f^q=(2p)^{p^m}=(2p)^{\frac{p^m}{m}.m} = ((2p)^m)^{\frac{p^m}{2^{a+1}.p^b}}=((2p)^m)^{\frac{p^{m-b}}{2^{a+1}}}=((2p)^m)^{K'}\equiv (-1)^{K'} [n]$ mais $K'$ n'est pas un entier donc $(2p)^q \not\equiv 1 [n]$
2-2/ Mq il existe toujours un entier $i$ compris entre $0$ et $d$ tel que $f^{q.2^i}\equiv -1 [n]$ (2) est toujours vraie
$f^{q.2^i}=(2p)^{2^i.p^m}=(2p)^{\frac{2^i.p^m}{m}.m}=((2p)^m)^{\frac{2^i.p^m}{2^{a+1}.p^b}}=((2p)^m)^{2^{i-a-1}.p^{m-b}}\equiv (-1)^{K"}[n]\equiv -1 [n]$ si $K"$ est impair or $K"=2^{i-a-1}.p^{m-b}$ n'est pas divisible par $2$ si $i-a-1=0$. Cette condition est assurée lorsque $i=a+1$
$i=a+1$ est positif pour tout entier naturel $a$
De plus, $i=a+1<m$ et rappelons que $n-1=(2p)^m=2^m.p^m=2^d.q$ avec $q$ impair
Par identification, $d=m$ et nous venons de voir que $0<i=a+1<m$ donc $0<i<d$
2-3/ Conclusion
Tout entier naturel de la forme $n=(2p)^{2^{a+1}.p^b}+1$ est $(2p)$-probablement-premier et $(2p)$-fortement-probablement-premier[/quote]
Réponses
-
Bon évidemment, si je ne suis pas apte à décrypter les calculs, je peux en tout cas te féliciter de CHERCHER (à tout le moins) des nombres sur la base de l'algorithme probabiliste polynomial d'attestation de primalité. C'est une idée plaisante: construire des formes d'entiers dont on sait à l'avance qu'ils seront déclarés "probablement premier" quand passés au test.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Attention, pour que $n$ soit "probablement premier", on a besoin de montrer que $n$ est $a$-fortement probablement premier pour plusieurs valeurs aléatoires de $a$ (plus on teste de valeurs de $a$, plus $n$ a des chances d'être premier).
Or ici on a le résultat seulement pour une valeur très particulière de $a$, ce qui limite l'intérêt de la chose.
N.B. Le résultat a l'air juste, mais il faudrait vérifier les calculs pour être sûr, ce que je n'ai pas fait. -
Effectivement, ce type d'entier n'est pas probablement premier et il génère même quasiment que des nombres pseudos premiers.
-
Remarque: il y a une espièglerie dans ce que je t'ai répondu, et j'espère que tu la verras. (Que personne ne souffle smiley tchin tchin)Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Bon bin, tu n'as pas vu la blague. Merci à JLT de n'avoir rien dit :-D
Avant de continuer, essaie de la trouver. Indice: ça donne un slogan qui publié dans les journaux ferait scandale.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Bon, je vois que tu n'es pas revenu, je te donne la réponse: ;-)dans ton contexte tout nombre probablement premier est premier. Evidemment, dit comme ça, ça pourrait choquer... :-DAide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Salut Christophe,
Désolé je n'ai rien compris. J'imagine que tu plaisantes.
Tu sembles poster pas mal dans maths à l'envers et du coup je me demande ce que tu recherches vraiment ? -
Mouahahaha elle est trop bonne celle là (:P)
Christophe victime de son succès sur Shtam...
@quimavendu@laposte.net je te rassure Christophe n'a rien à voir avec la rubrique Shtam, c'est tout à fait exceptionnel qu'il publie ici. Si tu ne comprends pas ce qu'il dit c'est pour une autre raison... -
Non, je ne plaisantais pas du tout, tout nombre probablement premier est premier. Il ne faut pas se faire avoir par le dénominations mathématiques. Tu devrais demander à Gérard0, pro en probas-stats la "probable" :-D démangeaison que ça a dû lui faire de voir que les pros de la complexité algorithmique nomment comme ça les nombres premiers quand ils ont découvert l'algorithme proba polynomial de primalité.
Mais attention, je n'ai pas lu tes calculs (j'ai vu que JLT lui l'a fait), ça ne veut pas dire que tu as tort. Juste que tu aurais dû annoncer les choses comme suit:
"Bonjour, je vous présente des nombres dont je peux prouver qu'ils sont premiers. En effet, je peux prouver qu'ils sont probablement premiers au sens de la définition Truc-Bidule de Shamir**".
** je ne suis pas sûr que c'est lui le découvreur, j'ai mis "le nom célèbre".Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Je précise pour les lecteurs débutants qui passeraient par là, afin qu'ils économisent du stress neuronal.
Il a été découvert il y a quelques décennies qu'il existe $A$ un ensemble $\subset \N^2$ ayant les propriétés suivantes, pour tout entier $n$:
1/ Si $n$ est premier alors $\forall p\leq n: (p,n)\notin A$
2/ Si $n$ n'est pas premier alors plus de la moitié des $p\leq n$ sont tels que $(p,n)\in A$
3/ $A$ se calcule très rapidement.
Ce qui permet de faire la chose suivante quand vous êtes confrontés à un grand entier $n$:
1/ vous tirez au sort $p\leq n$.
2/ Vous regardez si $(p,n)\in A$. Si oui, c'est réglé, $n$ n'est pas premier. Sinon, pas de bol, peut-être que $n$ n'est pas premier, mais que vous n'avez pas tiré le bon. Vous vous dites "j'avais moins de 0.5 de proba de me foirer".
Vous recommencez. A nouveau situation pas concluante. Vous vous dites "j'avais moins de 0.25 de proba de me foirer".
Vous recommencez. A nouveau situation pas concluante. Vous vous dites "j'avais moins de 0.125 de proba de me foirer"......
Vous recommencez. A nouveau situation pas concluante. Vous vous dites "j'avais moins de $\frac{1}{2^{50}}$ de proba de me foirer".
3/ Vous en avez marre, ça fait 0.034 secondes que votre PC taffe et vous vous dites: "bon franchement, si $n$ n'est pas premier, je n'ai vraiment pas eu de chances de tomber 50 fois de suite sur un $p$ tel que $(p,n)\notin A$ alors que plus de $50\%$ d'entre eux vérifient $(p,n)\in A$
Les entiers probablement premiers sont les entiers premiers, bien évidemment, ce sont les $n$ tels que $\forall p\leq n: (p,n)\notin A$.
Cette méthode achoppe sur un problème philosophico-physiqco-mathématique important. Aujourd'hui, les ordinateurs qui implémentent une simulation du hasard, implémentent en général "le vrai hasard quantique" en allant par exemple, mesurer la pression de l'air sur un périphérique. Donc "tout va bien".
Les anciennes machines par contre implémentaient une simulation du hasard en prenant un algorithme rapide qui en gros, par exemple, calculait le modulo $r(i)$ de la division de $36543643610461043658071367436 +2036827543 i $ par $5$, en espérant secrètement que ça simulait bien le hasard au nom d'une sorte d'imbitabilité issue des théorèmes chinois/Bezout.
Il y avait donc de grosses craintes que la seule chose que ça donne c'est une corrélation encore méconnue entre les nombres premiers et les modulo des chinoiseries implémentées. Et de manière générale, aucun algorithme rapide de simulation déterministe du hasard n'est fiable pour cette raison.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Je dois préciser que
* je n'ai pas compris non plus la blague de cc. A la rigueur je croyais que sa phrase "construire des formes d'entiers dont on sait à l'avance qu'ils seront déclarés 'probablement premier' quand passés au test" pouvait passer pour une blague sur le CDAL mais ça n'a pas l'air d'être ça.
* je n'ai pas non plus vérifié les calculs du message initial, je disais juste que l'énoncé m'a l'air plausible, la forme de la démonstration ressemble à une démonstration raisonnable de l'énoncé.
* quimavendu n'a pas prétendu que son $n$ est probablement premier, mais qu'il existe $a$ (dépendant de $n$) tel que $n$ est $a$-fortement probablement premier, ce qui est une assertion beaucoup plus faible. -
quimavendu n'a pas prétendu que son n est probablement premier, mais qu'il existe a (dépendant de n) tel que n est a-fortement probablement premier, ce qui est une assertion beaucoup plus faible.
En fait, j'avais vu que tu lui répondais ça, c'est clair que c'est beaucoup plus faible a priori. Je connais très mal les idées de l'algorithme bien que je les ai relues*** il y a peu sur wikipedia. Je trouve dommage que Gérard ne soit pas venu râler contre l'expression, lui qui s'est bien souvent évertué à différencier risque et probabilité, mais .. il ne fréquente peut-être pas trop shtam ....
*** si le confinement dure, et vu que j'ai Python qui gère les grands entiers (mais est très lent comparé aux autres langages),j'essaierai même peut-être de me forcer à l'implémenter pour me forcer à l'apprendre.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Terminologie.
Il n'y a pas l'adverbe ``probablement''. On dit que $n$ est pseudo-premier de base $a$ si bla-bla. On dit que $n$ est fortement pseudo-premier de base $a$ si patati-patata (ce n'est pas la même chose). Et on dit que $n$ est pseudo-premier de bases $A$ (pour un ensemble $A$ d'entiers $\ge 2$) si $n$ est pseudo-premier de base $a$ pour tout $a \in A$. Idem pour fortement pseudo-premier. Point. -
Merci Claude. Je confondais avec Wims qui utilise l'adverbe "probablement premier" pour les grands entiers dont il ne détermine sauf sur demande s'ils sont premiers. Gérard peut rester tranquille ;-)Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 26
+18 Invités