Demostrar que $n^k+1$ tiene un divisor primo $>2k$

Question

Sea $n\ge3$ & $k\ge2$ . Demuestre que $n^k +1$ tiene un divisor primo $>2k$ .

Answer 1

Puede utilizar directamente Teorema de Zsigmondy, escrito en este pdf . Por el teorema se obtiene que existe un divisor primo $p$ de $n^k+1$ que no divide $n^r+1$ para todos $1\le r\le k-1$ . Ese divisor primo $p$ debe ser impar, porque si $n^k+1$ es impar, entonces es obvio, y si $n^k+1$ es par, entonces el divisor primo no divide a $n+1$ que es par. Se obtiene que $n^k\equiv -1\pmod{p}$ y $n^r\not\equiv -1\pmod{p}$ para todos $1\le r\le k-1$ . Entonces $n^{2k}\equiv 1\pmod{p}$ . Sea $\text{ord}_p(n)$ sea el orden multiplicativo de $p$ mod $n$ . Entonces $\text{ord}_p(n)\mid 2k$ lo cual es fácil de demostrar (para demostrarlo, por contradicción escribe $2k=\text{ord}_p(n)t+r_1$ , $1\le r_1<\text{ord}_p(n)$ y conseguir que $n^{r_1}\equiv 1\pmod{p}$ contradicción). Entonces demostraré que $\text{ord}_p(n)=2k$ . En efecto, si $\text{ord}_p(n)<2k$ , entonces voy a comprobar dos casos:

$1)\ \ $ si $\text{ord}_p(n)$ es par, entonces $n^{\frac{\text{ord}_p(n)}{2}}\equiv -1\pmod{p}$ y $1\le \frac{\text{ord}_p(n)}{2}\le k-1$ contradicción porque se nos da que $n^r\not\equiv -1\pmod{p}$ para todos $1\le r\le k-1$ .

$2)\ \ $ si $\text{ord}_p(n)$ es impar, entonces de $\text{ord}_p(n)\mid 2k$ te las arreglas Lema de Euclides que $\text{ord}_p(n)\mid k$ pero esto significa que $n^k\equiv 1\pmod{p}$ y nos dan que $n^k\equiv -1\pmod{p}$ Así que $1\equiv -1\pmod{p}$ Así que $p\mid 1-(-1)=2$ contradicción porque $p$ es impar.

Ahora que sabe que $\text{ord}_p(n)=2k$ te las arreglas Pequeño teorema de Fermat que $2k\mid p-1$ Así que $p-1=2kh$ para algunos $h\ge 1$ , $p=2kh+1\ge 2k+1>2k$ .

Answer 2

Por el teorema de Zsigmondy (véase aquí ), $n^{2k} - 1$ tiene un divisor primo $p$ tal que $p$ no es divisor de $n^j-1$ para cualquier $j < 2k$ . En particular, $p$ no divide $n^k-1$ pero divide $n^{2k} - 1 = (n^k - 1)(n^k + 1)$ Así que $p$ divide $n^k + 1$ . También disponemos de $n^{j} \neq 1 \pmod{p}$ para $j < 2k$ Así que $\varphi(p) = p-1 \ge 2k$ .