Conjecture "2^n"

Olympiades mathématiques, énigmes et défis
nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 06 Oct 2015, 20:49

S(2) mod n = 0 ça se prouve assez facilement.
Attention aux nombres composés de Carmichael, qui donneront le même résultat. C'est à dire que ton test de primalité ne sera pas vrai à 100%.



Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 06 Oct 2015, 21:16

nodjim a écrit:S(2) mod n = 0 ça se prouve assez facilement.
Attention aux nombres composés de Carmichael, qui donneront le même résultat. C'est à dire que ton test de primalité ne sera pas vrai à 100%.

Eh oui! on retrouve notre test de Fermat en fin de compte.
Comment trouver S(2) connaissant n?
Pas facile!

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 06 Oct 2015, 21:17

Cette suite est interessante a etudier de tres pres, je pense.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 06 Oct 2015, 23:50

As-tu teste n=561?
Tu obtiens quoi?
En cours de route de S(561) a S(0) tu as pas mal S(k)= 0 mod 561.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 07 Oct 2015, 09:36

Pour la preuve de S(2)=0 mod p si p premier > 3.
S(0)=2^p-2^(p-1)+.....+2-1. en partant de S(p)
S(0)=Si-Sp (comme somme des puissances impaires et paires)
Si=2^p+2^(p-2)+...2^1
Sp=2^(p-1)+2^(p-3)+....2^0
On vérifie que Si=2Sp
Par ailleurs Si+Sp=2^(p+1)-1 car = 2^p+2^(p-1)+....1
Or si p premier, 2^p=2 et 2^(p+1)=4 mod p, si p>3.
Si+Sp=3Sp= 4-1= 3
Sp= 1 et Si=2
S(0)=Si-Sp=2-1=1
Si on ôte les 2 derniers termes
S(0)-(-2^0)-(2^1)=1-(-1)-2=0 mod p.
Donc S(2)= 0 mod p.

Corollaire: les nombres px pseudo premiers (2^px=2 mod px) donneront forcément le même résultat.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 07 Oct 2015, 18:08

Bizarrement le calcul me donne autre chose.
j`ai lu et relu ta preuve quelque chose a du m`echapper.

S(2) mod 561=187 et non zero

Est-ce quelqu`un peut confirmer ou infirmer?
Merci

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 07 Oct 2015, 18:41

561 est un nombre de Carmichael qui echappe au test de Fermat.
En esperant que mon calcul ne soit pas faux et que S(2) mod 561 different de zero, ce serait une avancee.
On aurait (je parle au conditionnel) un test plus precis de primalite. Plus besoin de tester les bases 3,5 et 7.
2 ecueils :
- il faut qu`il n`y ait pas d`autres exceptions
- il faut trouver un moyen de calculer rapidement S(2) a partir de n (faisable a mon avis). C`est une difference entre 2 progressions geometriques de raison 4.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 07 Oct 2015, 20:02

Je confirme pour 561: 187 au lieu de zéro. C'est très curieux car la démo est indépendante de la primalité du nombre testé, sauf que 2^n=2.
Donc je regarde pourquoi ça cloche. A noter tout de même que 187 est le 1/3 de 561, donc ces 2 nombres sont ressemblants. Dans ma démo, j'avais exclu 3 comme p premier, mais seulement lorsqu'il était seul, pas dans une décomposition. Quelque chose m'échappe mais je ne vois pas quoi pour l'instant.

En revanche, pour 341=11*31, qui est un composé non Carmichael, mais dont 2^341=2 mod 341, on a bien S(2)=0.
Le test de primalité n'est donc pas sûr à 100%

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 07 Oct 2015, 20:08

nodjim a écrit:Je confirme pour 561: 187 au lieu de zéro. C'est très curieux car la démo est indépendante de la primalité du nombre testé, sauf que 2^n=2.
Donc je regarde pourquoi ça cloche. A noter tout de même que 187 est le 1/3 de 561, donc ces 2 nombres sont ressemblants. Dans ma démo, j'avais exclu 3 comme p premier, mais seulement lorsqu'il était seul, pas dans une décomposition. Quelque chose m'échappe mais je ne vois pas quoi pour l'instant.

En revanche, pour 341=11*31, qui est un composé non Carmichael, mais dont 2^341=2 mod 341, on a bien S(2)=0.
Le test de primalité n'est donc pas sûr à 100%

Merci pour ces precisions on aura bientot les nombres de Mario (ha ha ha).
J`ai bien precise qu`il pouvait y avoir un ecueil.
A part 341 il devrait y en avoir d`autres peut-etre.
Dommage que je ne sache pas programmer.
Si la liste n`est pas longue et s`il y a une explication a ces nombres, je pense detenir alors un test de primalite a combiner avec Fermat.

Un grand merci.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 07 Oct 2015, 20:42

L'explication pour 341:
En fait, c'est 2^phi(n)=1 modulo n, phi étant la fonction indicatrice d'Euler (cardinal des nombres premiers avec n).
phi(341)=300 car (31-1)(11-1).
Or le 1 n'arrive pas forcément à 2^300, il peut arriver avant, en fait il arrive sur un diviseur de 300. Ici, pour 341, le hasard a voulu que le cycle soit 10. Or 10, s'il est bien diviseur de 300, est aussi diviseur de 340. C'est la raison pour laquelle 2^340=1 mod 341.
Malheureusement, on ne connait pas les cycles des nombres, il faut tester. Aussi, le test risque bien de ne pas fonctionner pour une infinité de valeurs, même si elles sont peu fréquentes.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 07 Oct 2015, 20:52

nodjim a écrit:L'explication pour 341:
En fait, c'est 2^phi(n)=1 modulo n, phi étant la fonction indicatrice d'Euler (cardinal des nombres premiers avec n).
phi(341)=300 car (31-1)(11-1).
Or le 1 n'arrive pas forcément à 2^300, il peut arriver avant, en fait il arrive sur un diviseur de 300. Ici, pour 341, le hasard a voulu que le cycle soit 10. Or 10, s'il est bien diviseur de 300, est aussi diviseur de 340. C'est la raison pour laquelle 2^340=1 mod 341.
Malheureusement, on ne connait pas les cycles des nombres, il faut tester. Aussi, le test risque bien de ne pas fonctionner pour une infinité de valeurs, même si elles sont peu fréquentes.

Y a moyen de remedier a cela.
Je viens d`avoir une idee lumineuse!
Encore du boulot!
A suivre donc!

Robot

par Robot » 08 Oct 2015, 00:35

Il y a une infinité de nombres de Carmichael de la forme 3k+1. Pour tous ceux-là S(2)=0.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 08 Oct 2015, 02:09

Les nombres pour lesquels S(2)=0 sont-ils listes sur OEIS?

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 08 Oct 2015, 10:05

Une précision sur les multiples de 3: En fait, le cycle S(3) est de 3, contrairement aux autres nombres premiers p dont le cycle est de longueur p-1 (ou un des diviseurs).
Pour 561=3*11*17, le cycle est de longueur 3*10*16=480 (ou un de ses diviseurs).
Pour S(561), le 0 arrive pour le rang S=561-480+1=82.
S(82)=0 en partant de S(561).

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 08 Oct 2015, 13:41

L`algorithme deviendrait pour un n impair quelconque :
- Calculer S(2)
- Calculer pgcd(n,S(2)) si >1 et <n donc n est compose sinon calculer S(2) mod n
- Si S(2) mod n = 0 n est un nombre premier.

Je ne sais pas si cela filtrerait tous les faux premiers.
A verifier.

Edit (C`est corrige!)

Robot

par Robot » 08 Oct 2015, 14:58

Mario2015 a écrit:- Calculer pgcd(n,S(2)) si >1 donc n compose ...

Si n=5, S(2)=2^5-2^4+2^3-2^2=32-16+8-4=20, donc pgcd(n,S(2))=5>1, donc 5 est composé ...

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 08 Oct 2015, 15:12

Robot a écrit:Si n=5, S(2)=2^5-2^4+2^3-2^2=32-16+8-4=20, donc pgcd(n,S(2))=5>1, donc 5 est composé ...

Remarque triviale.
On cherche la petite bete on dirait.
Ce qui m`interesserait serait de savoir si certains faux nombres premiers passent le filtre.
Je propose un test de primalite different du test de Fermat.
On me fait des remarques triviales.
Tres serieusement, est-ce que vous pensez que les physiciens qui ont concu ces formidables machines qui sont les accelerateurs de particles savent reparer ces machines?
bref, je viens de corriger mon erreur.
Il faut bien plus que cela. Il faut construire des preuves pour solidifier le test.
Je ne suis pas un mathematicien professionnel.
D`ailleurs, je viens de faire une decouverte importante en m`amusant.
Celle-la risque de faire peter la communaute des mathematiciens.
A suivre donc.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 08 Oct 2015, 15:37

J`ai besoin de remarques constructives sur le fond.
Je viens de me reveiller, je n`ai pas encore atteint ma dose de nicotine qui me permet de voir clair et je fais une erreur.
Desole, il fallait juste pointer l`erreur sans user de la derision.
J`arrete encore une fois avant de peter les plombs.
Certains sont la juste pour jouer les instits. Ils ne produisent rien!
Allez jeter un coup a leurs posts. Ils n`initient jamais de posts, jamais.
Mais des que quelqu`un commet une erreur ils s`en donnent a coeur joie. Allez! Vazon vazy rions d`eux rions d`eux rions cela soulage l`ego.
Adios!
Sylviel, rebannissez-moi et de maniere definitive.
Votre forum ne se portera pas mieux.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 08 Oct 2015, 15:41

Discussion ouverte par le pseudo Robot : une seule sur un probleme de bug?
Une sur 476!!!!!!!!!!!!!!!!!!!!!
Quelle est ta contribution bordel de merde!!!!!!!!!!!!!!!!!!
A part jouer les instits!!!!!!!!!!!!!!!?????????????????

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 08 Oct 2015, 15:43

Qu`est-ce que Robot apporte au forum?????????????????????
RIEN!!!!!!!!!!!!!!!!!!!!!!!!!
RIEN!!!!!!!!!!!!!!!!!!!!!!!!!

DE LA GROSSE CROTTE GOOGLISEE ...........
REVEILLEZ-VOUS MODERATEURS!!!!
CE SONT DES GENS COMME ROBOT QUI COULENT LE FORUM.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite