Composti del piccolo Fermat

Messaggioda dan95 » 20/02/2019, 13:23

Dimostrare che esistono infiniti numeri composti $m$ tali che

$a^(m-1) \equiv 1 \mod m$

Con $(a,m)=1$.
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Advanced Member
Advanced Member
 
Messaggio: 2472 di 2478
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Composti del piccolo Fermat

Messaggioda giammaria » 08/03/2019, 10:47

Intendi che deve essere vera per ogni $a$ soddisfacente alla condizione data? In particolare, dovrebbe esserlo per $a=2$ ed $m$ dispari e composto; ho provato al computer e non ci sono soluzioni fino a $m=49$ (dopo questo valore i numeri diventano troppo alti).
Forse le soluzioni si hanno con $m$ pari (e quindi $a$ dispari): confermi?
- Indicando i metri con m e i centimetri con cm, si ha m=100 cm. Quindi 5 centimetri equivalgono a metri m=100*5=500.
- E' disonesto che un disonesto si comporti in modo onesto (R. Powell)
giammaria
Cannot live without
Cannot live without
 
Messaggio: 5035 di 5045
Iscritto il: 29/12/2008, 22:19
Località: provincia di Asti

Re: Composti del piccolo Fermat

Messaggioda axpgn » 08/03/2019, 11:36

@giammaria
Testo nascosto, fai click qui per vederlo
Penso che intenda una via di mezzo tra gli pseudoprimi e gli pseudoprimi assoluti e cioè che per ogni $a$ esistano infiniti $m$ che soddisfino le condizioni date ma non è detto che lo stesso $m$ "vada bene" per ogni $a$ (quindi non è uno pseudoprimo assoluto).
Conosco una dimostrazione ma preferisco che sia lui, eventualmente, a postarla …


Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13106 di 13183
Iscritto il: 20/11/2013, 22:03

Re: Composti del piccolo Fermat

Messaggioda dan95 » 08/03/2019, 11:51

Rileggendo il testo mi sono accorto che non è molto chiaro. Lo riscrivo:

Per ogni fissato $a$ bisogna dimostrare che esistono infiniti numeri composti $m$ tali che:

$a^(m-1) \equiv 1 \mod m$

La dimostrazione è "costruttiva"

Hint:

Testo nascosto, fai click qui per vederlo
Fissiamo $a$, prendiamo $p$ primo tale che $p$ non divide $a(a^2-1)$ (esiste?), e definiamo $m=\frac{a^(2p)-1}{a^2-1}$
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Advanced Member
Advanced Member
 
Messaggio: 2475 di 2478
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Composti del piccolo Fermat

Messaggioda giammaria » 08/03/2019, 20:51

Grazie mille; senza hint non ce l'avrei mai fatta ed anche avendolo dovrò scervellarmi per sfruttarlo. Capisco perché il computer non aiutava: il più piccolo valore corrisponde ad $a=2$ ed è $m=341$.
- Indicando i metri con m e i centimetri con cm, si ha m=100 cm. Quindi 5 centimetri equivalgono a metri m=100*5=500.
- E' disonesto che un disonesto si comporti in modo onesto (R. Powell)
giammaria
Cannot live without
Cannot live without
 
Messaggio: 5036 di 5045
Iscritto il: 29/12/2008, 22:19
Località: provincia di Asti

Re: Composti del piccolo Fermat

Messaggioda axpgn » 08/03/2019, 21:33

@giammaria
Testo nascosto, perchè contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.
È il più piccolo pseudoprimo e il primo scoperto nel 1919 da Sarrus. Questa scoperta purtroppo "smentiva" la conversa del piccolo teorema di Fermat.
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13116 di 13183
Iscritto il: 20/11/2013, 22:03

Re: Composti del piccolo Fermat

Messaggioda dan95 » 08/03/2019, 21:42

Alex
:smt023
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Advanced Member
Advanced Member
 
Messaggio: 2476 di 2478
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Composti del piccolo Fermat

Messaggioda axpgn » 15/03/2019, 00:27

In attesa della dimostrazione, un paio di esercizi di allenamento … :-D

Dimostrare che $2047$ è uno pseudoprimo e che $2821$ è uno pseudoprimo assoluto,

Cioè $2047|(2^2047-2)$ e $2821|(a^2821-a)$ con $a in ZZ$

Cordialmente, Alex

P.S.: chiedo scusa a dan95 se ho approfittato del suo thread ma mi pareva inutile aprirne un altro … :D :wink:
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13148 di 13183
Iscritto il: 20/11/2013, 22:03


Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite