Se$n$è pseudoprimo e$[n,a]=[n,a+1]=1$, poi$(a+1)^n\equiv a^n +1 \pmod n$?
Ho riscontrato un problema ($[a,b]$è il MCD di$a,b$.)
Se$n$è pseudoprimo, e$a$un numero intero tale che$[n,a]=[n,a+1]=1$, mostralo
$$(a+1)^n\equiv a^n +1 \pmod n$$
Suggerimento:$a^n\equiv a\pmod n, \; (a+1)^n\equiv a+1\pmod n$.
Riconosco i suggerimenti come il piccolo teorema di Fermat, ma questo è vero quando$n$è primo. Ho provato a fare delle tabelle su Mathematica ma le identità non sembrano tenere. E' vero o sto commettendo qualche errore?
Risposte
Come afferma Pseudoprimo ,
Gli pseudoprimi sono classificati in base alla proprietà dei numeri primi che soddisfano.
Il problema della tua domanda non indica esplicitamente per quale particolare proprietà viene utilizzata$n$, ma la proprietà sembra (ad esempio, sulla base del loro suggerimento) essere Fermat pseudoprime . In tal caso, la frase "Se$n$è pseudoprimo, ..." dovrebbe significare "Se$n$è uno pseudoprimo di Fermat in base$a$e base$a + 1$, ...".
Il loro suggerimento sarebbe quindi vero da allora$a^{n-1} \equiv 1 \pmod{n} \implies a^n \equiv a \pmod{n}$e$(a + 1)^{n-1} \equiv 1 \pmod{n} \implies (a + 1)^n \equiv a + 1 \pmod{n}$. Da questo, sostituendo$a^n$per$a$sul lato destro nella seconda congruenza dà quanto richiesto, cioè,$(a + 1)^n \equiv a^n + 1 \pmod{n}$.