Composti del piccolo Fermat

Messaggioda dan95 » 20/02/2019, 14: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 2492
Iscritto il: 10/06/2013, 17:37
Località: Roma Caput Mundi

Re: Composti del piccolo Fermat

Messaggioda giammaria » 08/03/2019, 11: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 5080
Iscritto il: 29/12/2008, 23:19
Località: provincia di Asti

Re: Composti del piccolo Fermat

Messaggioda axpgn » 08/03/2019, 12: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 13544
Iscritto il: 20/11/2013, 23:03

Re: Composti del piccolo Fermat

Messaggioda dan95 » 08/03/2019, 12: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 2492
Iscritto il: 10/06/2013, 17:37
Località: Roma Caput Mundi

Re: Composti del piccolo Fermat

Messaggioda giammaria » 08/03/2019, 21: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 5080
Iscritto il: 29/12/2008, 23:19
Località: provincia di Asti

Re: Composti del piccolo Fermat

Messaggioda axpgn » 08/03/2019, 22: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 13544
Iscritto il: 20/11/2013, 23:03

Re: Composti del piccolo Fermat

Messaggioda dan95 » 08/03/2019, 22: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 2492
Iscritto il: 10/06/2013, 17:37
Località: Roma Caput Mundi

Re: Composti del piccolo Fermat

Messaggioda axpgn » 15/03/2019, 01: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 13544
Iscritto il: 20/11/2013, 23:03

Re: Composti del piccolo Fermat

Messaggioda axpgn » 02/05/2019, 14:41

Visto che dan95 latita … :D

Testo nascosto, fai click qui per vederlo
Sia $p$ un primo dispari che NON divida $a(a^2-1)$ dove $a$ è un intero maggiore di uno.
Allora $p$ non divide né $a$ né $a^2-1$.
Si prenda $n$ tale che $n=(a^(2p)-1)/(a^2-1)=(a^p-1)/(a-1)*(a^p+1)/(a+1)$ e quindi $n$ è composito.
Per il "Piccolo teorema di Fermat" abbiamo $a^(p-1)-=1$per cui $p$ divide $a^(p-1)-1$.
Ora $n-1=(a^(2p)-a^2)/(a^2-1)\ =>\ (n-1)(a^2-1)=a(a^(p-1)-1)(a^p+a)$ che è divisibile per $p$.
Siccome $p$ NON divide $a^2-1$ allora $p$ divide $n-1$.
Inoltre $n=a^(2(p-1))+a^(2(p-2))+...+a^2+1$ è dispari quindi anche $2$ divide $n-1$.
Ne consegue che $2p$ divide $n-1$ per cui $n=2kp+1$ per qualche $k in NN$ ed anche $a^(2p)=1+(a^2-1)n-=1\ MOD\ n$ che implica $(a^(2p))^k-=1\ MOD\ n$ ovvero $a^(n-1)-=1\ MOD\ n$ (perché $n=1+2kp$).
In conclusione $n$ è uno pseudoprimo rispetto alla base $a$. E siccome $n$ ha valori differenti per differenti valori di $p$ (quando $p$ NON divide $a(a^2-1)$) abbiamo infiniti pseudoprimi per ogni base $a$.


Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13404 di 13544
Iscritto il: 20/11/2013, 23:03


Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite