Se$n$è pseudoprimo e$[n,a]=[n,a+1]=1$, poi$(a+1)^n\equiv a^n +1 \pmod n$?

Aug 23 2020

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

1 JohnOmielan Aug 23 2020 at 11:46

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