OliForum Matematico

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)

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!
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!

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