Un número impar compuesto, que no sea una potencia de $3$, es un Fermat-pseudoprimo para alguna base

Question

Quiero demostrar la siguiente afirmación :

Si $n$ es un número compuesto impar, que no es una potencia de $3$ (o, equivalentemente, tiene un factor primo $p>3$), entonces $n$ es un pseudo-primo de Fermat para la misma base $a$, en otras palabras, existe un número $a$ con $$1 y $$a^{n-1}\equiv 1\ (\ mod\ n\ )$$

Pude demostrar el recíproco:

Si $$a^{n-1}\equiv 1\ (\ mod\ n\ )$$ para algún número $a$ con $1, entonces el número $o\ :=\ ord_a(n)$ divide tanto a $n-1$ como a $\phi(n)$. Dado que $o=1$ es imposible porque $a\equiv 1\ (\ mod\ n\ )$ contradice $1 y $\phi(3^k)=2\times 3^{k-1}$, se deduce que $o=2$. Pero $a^2\equiv 1\ (\ mod\ 3^k\ )$ implica $a\equiv \pm1\ (\ mod\ 3^k\ )$ debido a que $gcd(a-1,a+1)\le 2$. Pero esto contradice $1, por lo que el número no puede ser una potencia de $3$

¿Es correcta mi demostración del recíproco ?

¿Cómo puedo mostrar la afirmación original ?

Answer 1

Sí, tu demostración de la afirmación contraria es correcta.

Para probar la afirmación original:

Si $n = p^k$ para un primo $p > 3$, entonces el grupo de unidades módulo $n$ es cíclico, y por lo tanto contiene un elemento $a$ de orden $p-1 \geqslant 4$. Este es una base para la cual $n$ es un pseudo primo de Fermat, y $a \not\equiv \pm 1 \pmod{n}$.

Si $n$ tiene al menos dos factores primos distintos $p,q$, digamos $n = p^kq^m\cdot r$ con $\gcd(r,pq) = 1$, entonces sea

$$a \equiv 1 \pmod{p^kr},\quad a \equiv -1 \pmod{q^m}.$$

Entonces $a^2 \equiv 1 \pmod{n}$, y $n$ es un pseudoprimo de Fermat para la base $a".