Des nombres particuliers
dans Arithmétique
Bonjour
Je me demandais si pour un entier naturel n supérieur ou égal à 2, on a:
n(n-1) | 2^n - 2 implique n premier ?
J'ai déjà vérifié la véracité de cette proposition pour tout n entre 2 et 1000000 mais je ne pense pas qu'elle soit vraie (ce serait trop beau pas vrai ?).
Si quelqu'un a un contre-exemple ou mieux : une démonstration de la fausseté de la proposition ce serait sympa.
Merci d'avance pour votre aide.
Je me demandais si pour un entier naturel n supérieur ou égal à 2, on a:
n(n-1) | 2^n - 2 implique n premier ?
J'ai déjà vérifié la véracité de cette proposition pour tout n entre 2 et 1000000 mais je ne pense pas qu'elle soit vraie (ce serait trop beau pas vrai ?).
Si quelqu'un a un contre-exemple ou mieux : une démonstration de la fausseté de la proposition ce serait sympa.
Merci d'avance pour votre aide.
Réponses
-
Bonjour
Pas compris.2 2 2 1 3 6 6 2 4 12 14 4 5 20 30 8 6 30 62 16
Pour la première colonne (n), la deuxième colonne (n(n-1)) ne divise pas forcément la troisième (2^n-2), ni la quatrième (2^(n-2)).
Que vouais-tu dire ?Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé. -
Bonjour,
il n'est pas écrit que n(n-1) divise 2^n - 2; il est dit que si n(n-1) divise 2^n -2 alors n est un nombre premier.
Bien cordialement.
kolotoko -
Bonjour.
Donc le contre exemple est tout trouvé, celui de la ligne 4, 20 ne divise ni 30, ni 8, pourtant il est formé à partir du nombre premier 5.
À bientôt.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Bonjour,
je ne vois pas pourquoi cela serait un contre exemple.
Bien cordialement.
kolotoko -
Tout dépend ce que l'on entend par "diviser".
De mon point de vue, cela comprend "exactement", ce qui n'est pas le cas pour ce contre exemple.
Il y a un nombre premier pour lequel l'assertion qui est sensée le discriminer ne le fait pas.
Je ne vois pas comment le comprendre autrement.
Après, on peut aussi chercher un nombre non premier qui rend l'assertion vraie aussi, mais ce n'est pas le but de l'assertion.
Cordialement.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Bonjour,
5*4 = 20 ; 2^5 -2 = 32 - 2 = 30 ; 20 ne divise pas 30 (exactement) donc 5 n'est pas concerné par l'assertion de Mounir.
Pour contredire celle-ci , il faut trouver un nombre composé n tel que n(n-1) divise exactement 2^n - 2.
Bien cordialement.
kolotoko -
Dreamer, on t'a connu plus pertinent !
-
Oui kolotoko a raison sur la méthode de contradiction ; et nul besoin de dire : divise "exactement", l'énoncé est parfaitement clair.
. -
Bonjour,
D'accord avec kolotoko (à cela près que, pour contredire la conjecture de Mounir, il suffit de (et non: il faut) trouver un nombre composé $n$ tel que $n(n-1)$ divise $2^n-2$
Cordialement
Paul -
Peut-être ne suis-je pas aussi pertinent que d'habitude, mais de là à me ressortir trois fois l'argument que je donne aussi en fin de mon message comme non représentatif...
Partons alors sur le fait que n ne divise pas 2^n-2 pour tout n supérieur ou égal à 3.
Je vous dis vraiment à bientôt.
Edit : excès de précipitation, ne quid nimis.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
A ce stade, le monde doit se diviser en deux groupes :
- ceux qui pensent que l'assertion est vraie, et doivent donc démontrer que si un entier n>1 vérifie : n(n-1) | (2^n - 2), alors n est premier.
- ceux qui pensent qu'elle est fausse, et partent à la recherche d'un entier c composé qui vérifie : c(c-1) | (2^c - 2). -
Après, ce qui serait frustrant, c'est qu'elle soit vraie, mais sans aucune occurrence, i.e. que pour aucun entier on n'ait n(n-1) | (2^n - 2). Mais bon, c'est une tout autre histoire qui n'a rien à voir avec sa véracité
. -
Ce n'est pas le cas.
sage: def T(N): ....: def b(k): ....: K = k*(k-1) ....: return power_mod(2,k,K)==2 and is_prime(k) ....: return [k for k in range(2,N+1) if b(k)] ....: sage: T(1000) [3, 7, 19, 43, 127, 163, 379, 487, 883]
Par exemple, \[2^3-2=3\times2, \quad2^7-2=3\times7\times6, \quad2^{19}-2=1533\times19\times18,\ \text{etc.}\] -
Bonjour,
serait-ce A069051 ?
Bien cordialement.
kolotoko -
On en déduit donc qu'il faut aller chercher dans les nombres de Carmichael. Car le petit théorème de Fermat en tant que test de primalité ne fonctionne pas même s'il est très probable. Bonne chance.Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
-
Bonjour, sur le net il y en a:
$\bullet $ Si $2^n-1$ est premier, $n$ est premier.
$\bullet $Si $2^n-1$ est premier, $n$ divise $2^n-2$.
[Je voulais dire si $n$ divise $2^{n}-2$ alors $n$ est premier. C'est faux pour $n=561$ (Carmichael)]
$\bullet $ $n$ ne divise pas $2^n-1$,
le facteur $n-1$ divise $2(2^{n-1}-1)$ et donc $n$ est impair.
Cordialement. -
Bonjour à tous et merci pour vos réponses.
Le suite A069051 nous donne effectivement les nombres qui sont premiers et qui vérifient p(p-1) divise 2^p - 2.
Mais la question reste entière!
Le but est bien de trouver un nombre n composé tel que n(n-1) divise 2^n-2.
Cependant, nul besoin de vous creusez plus la tête plus longtemps, j'ai bien cherché et j'en ai trouvé un:N = 2^524287 - 1.
Il est bien composé (comme on peut le voir sur la page wikipédia des Nombres de Mersenne)
Je vous laisse la démonstration en exercice pour les motivés B-)-
(Indice: étudiez la suite U(n+1) = 2^U(n) - 1 avec U(0) = 19) -
Bonjour à tous,
@Mounir, pour voir si je suis bien ( de l'infinitif "suivre" ;-) ):
Sur la page wikipédia des nombres de Mersenne que tu nous proposes, il est écrit que $M_{19:}=2^{19}-1=524287$ est premier.
En revanche, il n'est pas écrit (en tout cas pas noir sur blanc) que $M_{M_{19}}$ est composé. Donc je trouve que tu exagères dans ta formulation:"il est bien composé comme on peut le voir sur cette page wikipédia". N'aurais-tu pas dû écrire :"comme on peut le déduire des informations données sur cette page"?
L'étude de ta suite $U$ permet-elle de déduire tout ou seulement partie des trois preuves attendues:
1)$N:=M_{M_{19}}$ est composé
2)$N$ divise $2^{N-1}-1$ (bien que $N$ soit composé)
3)$\dfrac{N-1}{2}$ divise $2^{N-1}-1$ ?
Edit: au temps pour moi: voir mon message suivant
Cordialement
Paul -
Bonjour,
Un peu plus d'attention m'aurait permis de voir que $M_{M_{19}}$ était composé: les $31^{ième}$ et $32^{ième}$ nombres premiers de Mersenne sont $M_{216091}$ et $M_{756839}$; or $216091<524287=M_{19}<756839.$
Excuses
Paul -
Bonjour Paul
Oui, tu as raison, j'ai simplement déduit des informations contenues sur la page wikipédia que $M_{M_{19}}$ n'est pas premier.
Cependant, la première colonne du tableau indique le rang des nombres de Mersenne, ainsi, $M_2$ est le premier, $M_3$ est le deuxième, $M_5$ est le troisième... donc comme ce rang est clairement indiqué, il n'y a pas d’ambiguïté quant au fait qu'un nombre de Mersenne non découvert ne peut se glisser entre deux rangs consécutifs. Or, $M_{M_{19}} = M_{524287}$ n'apparait par dans ce tableau et devrait se trouver au rang $32$, entre $M_{216091}$ et $M_{756839}$.
Alors bien sûr, on peut toujours se demander si ce qui est affirmé dans la page wikipédia est juste mais ça, c'est une autre histoire
Ensuite, une étude de la suite $U$ permet d'obtenir les points 2 et 3 que tu as énoncés, en procédant par récurrence pour chaque point:
DEMO du point 2: $\forall n \in \mathbb{N},\quad U_n | 2^{U_n} - 2$.
Initialisation: Comme $19$ est premier, d'après le petit théorème de Fermat, on a bien $19 | 2^{19} - 2$.
Hérédité: Soit $n\in\mathbb{N}$ tel que $U_n | 2^{U_n} - 2$.
Alors $2^{U_n} - 1 | 2^{2^{U_n}-2} - 1$
i.e $U_{n+1} | 2^{U_{n+1} - 1} - 1$
donc $U_{n+1} | 2^{U_{n+1} } - 2$.
DEMO du point 3: $\forall n \in \mathbb{N},\quad U_n - 1| 2^{U_n} - 2$.
Initialisation: On a bien $18 | 2^{19} - 2$.
Hérédité: Soit $n\in\mathbb{N}$ tel que $U_n - 1 | 2^{U_n} - 2$.
Alors $2^{U_n - 1} - 1 | 2^{2^{U_n}-2} - 1$
donc $2^{U_n } - 2 | 2^{2^{U_n}-1} - 2$
i.e $U_{n+1} - 1| 2^{U_{n+1} } - 2$
Conclusion: Comme pour tout $n\in\mathbb{n}$, $U_n$ et $U_n -1$ sont premiers entre eux, on a bien:
$$\forall n\in\mathbb{N},\quad U_n(U_n - 1) | 2^{U_n} - 2$$ -
Oups nos messages ont du se croiser ^^ Mes excuses.
-
Bravo mounir!
J'y étais presque, mais seulement presque! Petite frustration. Mais tu fais plaisir à ma compagne qui s'agaçait que je fasse des maths tandis qu'il fait si beau dans notre jardin. Je l'y rejoins.
Cordialement
Paul -
En réponse à ce message, tous les nombres qui figurent dans la liste sont premiers.
sage: L = [] ....: with open('Mounir.txt','r') as h: ....: for l in h.readlines(): ....: t = l.split(' ') ....: L.append(ZZ(t[1])) ....: if not is_prime(int(t[1])): ....: print t[1] ....: sage: all(is_prime(l) for l in L) TrueJe trouve la question très intéressante parce qu'elle est simple à comprendre et que même si la réponse est négative, le premier contre-exemple est inaccessible par des moyens de calculs naïfs. Merci pour cela.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K 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
Qui est en ligne 3
+2 Invités