Para cualquier número entero positivo $a$ demuestre que existen infinitos compuestos $n$ tal que $a^{n-1}\equiv 1\mod n$ .

Question

Estudiando para un examen exhaustivo nos encontramos con el siguiente problema:

Demostrar que para cada entero positivo $a$ existen infinitos números enteros compuestos $n$ tal que $a^{n-1}\equiv 1 \mod n$ . (Sugerencia: Elija $n=\frac{a^{2p}-1}{a^2-1}$ para un primo adecuado $p$ .)

Hemos intentado muchas cosas sin éxito. El enfoque más prometedor consistía en elegir $p$ tal que $a$ es un residuo cuadrático módulo $p$ . Entonces $n-1=\frac{a^2(a^{2(p-1)}-1)}{a^2-1}$ tiene un factor de $p$ (el segundo factor en el numerador es una diferencia de cuadrados que factoriza a otra diferencia de cuadrados y finalmente a una $a^{(p-1)/2}-1$ sale que por nuestra elección de $p$ debe ser divisible por $p$ . No hemos podido llegar a ninguna conclusión. Agradeceríamos cualquier ayuda.

Answer 1

Primero: Si $p$ es un primo y $$n=\frac{a^{2p}-1}{a^2-1} =1+a^2+a^4+...+a^{2p-2}$$

Entonces $$ 1+a^2+a^4+...+a^{2p-2}=0 \pmod{n} \\ a^2( 1+a^2+a^4+...+a^{2p-2})=0 \pmod{n} \\ a^2+a^4+...+a^{2p-2}+a^{2p}=0 \pmod{n} \\ $$

Restando la primera y la última relación se obtiene $$1=a^{2p} \pmod{n}$$

Ahora, si ahora eliges $p,n$ para que $2p |n-1$ obtienes $$a^{n-1} \equiv 1 \pmod{n}$$

Tenga en cuenta que $2p |n-1$ significa $$2p|a^2(1+a^2+...+a^{2p-4})$$

Es fácil hacer que el RHS incluso y si lo desea $$p|1+a^2+...+a^{2p-4}$$ la forma más fácil es elegir $p >a^2-1$ (para asegurarse de que $a^2-1$ no puede ser divisible por $p$ ) y utilice $$a^{2p-2} \equiv (a^{p-2})^2\equiv 1 \pmod{p}$$