Pseudoprimi

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
luca88
Messaggi: 161
Iscritto il: 01 gen 1970, 01:00
Località: ciomp ciomp

Pseudoprimi

Messaggio da luca88 » 22 mag 2008, 13:26

Chiamiamo $ a $ uno pseudoprimo rispetto a 2 se $ a $ è composto e $ 2^{a-1} \equiv 1 \mod{a} $. Dimostrare che esistono infiniti pseudoprimi rispetto a 2.

PS: per chi è interessato: dimostrare che esistono infiniti pseudoprimi forti rispetto a 2 (vedi http://en.wikipedia.org/wiki/Strong_pseudoprime)

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 27 lug 2008, 14:23

Di questo fattarello esiste una dimostrazione elementare che ho letto e che non linko così magari qualcuno prova a farla;però volevo riportare la strada che provai io, che ha l'unico inconveniente di trasformare il problema in uno più difficile di quello di partenza! :D
Allora io ho trovato che se fosse vero questo lemma allora sarebbe vero il fatto degli pseudoprimi rispetto a 2 : esistono infiniti primi p per cui $ 2^p-1 $ è composto e con almeno due fattori primi.Vero questo si hanno facilmente gli pseudoprimi:poichè stiamo parlando di 2 alla base si ricava immediatamente che p è ordine moltiplicativo tra 2 e i due fantomatici fattori che chiamiamo l e m.Così $ l \equiv 1 \pmod p $ e $ m\equiv 1 \pmod p\ $ dunque $ lm\equiv 1 \pmod p $ ed il gioco è fatto $ 2^{lm-1}\equiv 1\pmod {lm} $.Dunque è per caso vero il lemma da cui io sono partito?: di quello io nn ne ho trovata una dimostrazione, però sarei curioso di vederne una. Scusate se invece dovesse essere una banalità o un problema di scarso interesse
Ciao!
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 27 lug 2008, 18:41

Usiamo tutti i cannoni possibili e immaginabili, e il bello è che alla fine non ti rispondo nemmeno (ma se non ricordo male sono in pochi a saperti rispondere) ...

I numeri di Mersenne sono quei numeri che si possono esprimere come $ \displaystyle 2^n-1 $ E' evidente che se $ \displaystyle n $ è composto lo è anche $ \displaystyle 2^n-1 $.
Ma a noi interessa il caso in cui $ \displaystyle n $ è primo. Credo che ancora non si sappia se esistono infiniti numeri di Mersenne composti con esponente primo. Quindi non preoccuparti, non hai chiesto una banalità.

Ciao

Rispondi