$n^{n-1}-1$ es un múltiplo de$k$

Question

Encuentre la cantidad de enteros$k$ con$2 \leq k \leq 1000$ que satisfaga la siguiente propiedad:

• Para cada entero positivo$n$ relativamente primo a$k$,$n^{n-1}-1$ es un múltiplo de$k$.

Deje$k = 2^{\alpha_1}3^{\alpha_2} \cdots p_n^{\alpha_n}$ ser la descomposición principal de$k$. Luego, según el Teorema del resto chino$n^{n-1} \equiv 1 \pmod{k}$ para todos$n$ de manera que$\gcd(n,k) = 1$ si y solo si \begin{align*}n^{n-1} &\equiv 1 \pmod{2^{\alpha_1}}\\n^{n-1} &\equiv 1 \pmod{3^{\alpha_2}}\\&\vdots\\n^{n-1} &\equiv 1 \pmod{p_n^{\alpha_n}}\end {alinee *} para todos$n$ tal que$\gcd(n,k) = 1$. ¿Cómo podemos continuar?

Answer 1

Si $\gcd(n,k)=1$$\gcd(n+k,k)=1$. Así:

$$1\equiv (n+k)^{n+k-1}\equiv n^{n+k-1}=n^{n-1}n^k\pmod{k}$$

y, por tanto, $n^k\equiv 1\pmod{k}$ todos los $n$ relativamente primer a $k$.

Ahora si $0<n<k$$\gcd(n,k)=1$, entonces:

$$1\equiv (k-n)^{k-n-1} \equiv (-1)^{k-n-1} n^kn^{-(n-1)}n^{-2}\pmod{k}$$

Pero $n^k\equiv n^{-(n-1)}\equiv 1\pmod{k}$, por lo que usted ha $$n^2\equiv (-1)^{k-n-1}\pmod{k}$$

Esto debería reducir el problema en gran medida para el caso-por-caso de análisis. El único primer poderes, donde cada relativamente primer cuadrado es$\pm 1$$2,4,8,3,5$. Y $k$ tiene que ser un producto de estos.

Sabemos $k$ debe ser, incluso, ya que de lo contrario $(2,k)=1$ $k$ debe dividir $2^{2-1}-1=1$, somos la mayoría de la forma.

Al $k$ es incluso, conseguimos que los $n$ es impar, y por lo tanto,$(-1)^{k-n-1}=1$, por lo que necesitamos $n^2\equiv 1\pmod{k}$ todos los $n$. Pero eso significa que $5$ no puede ser un factor.

Esto nos deja con $k=2,4,8,6,12,24$. Podemos comprobar rápidamente cada caso.

---

Bueno, más muestra un, usted necesita para probar este lema:

Si $p^{a}\mid k$ y hay algunos $n_0$ tal que $\gcd(n_0,p^a)=1$$n_0^2\not\equiv 1\pmod{p^a}$, entonces no es un $n$ $\gcd(n,k)\neq 1$ tal que $n^{2}\not\equiv 1\pmod{k}$.

Esencialmente, esto es porque usted puede escribir $k=p^bk'$ $\gcd(k',p)=1$ y luego resolver el resto Chino pregunta:

$$n\equiv n_0\pmod{p^b}\\ n\equiv 1\pmod{k}$$

Esto le da un $n$$n^2\not\equiv -1\pmod{p^b}$$n^2\not\equiv -1\pmod{k}$.