Composti del piccolo Fermat

[dan952]

Dimostrare che esistono infiniti numeri composti $m$ tali che

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

Con $(a,m)=1$.

[giammaria2]

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?

[axpgn]

@giammaria

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

[dan952]

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:

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}$

[giammaria2]

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$.

[axpgn]

@giammaria
[ot]È il più piccolo pseudoprimo e il primo scoperto nel 1919 da Sarrus. Questa scoperta purtroppo "smentiva" la conversa del piccolo teorema di Fermat.[/ot]

[dan952]

Alex

[axpgn]

In attesa della dimostrazione, un paio di esercizi di allenamento …

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 …

[axpgn]

Visto che dan95 latita …

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