¿Existen infinitos pares de primos $(p,q)$ tal que $pq$ divide $2^{p-1}+2^{q-1}-2$ ?

Question

Un amigo matemático me hizo esta pregunta (en parte como broma) hace unos meses y me ha dejado perplejo durante mucho tiempo:-

¿Existen infinitos pares de primos $(p,q)$ tal que $pq|2^{p-1}+2^{q-1}-2$ ?

La ecuación parece tan aleatoria que no he podido hacer ningún progreso significativo en ella (sólo puedo derivar condiciones igualmente horribles).

Agradecería enormemente si alguien pudiera ponerme en el camino correcto con respecto a esto.

Answer 1

Edición: El principal resultado demostrado en este post (indicado al final del mismo) se conoce en realidad como el teorema de Zsigmondy, en el que he omitido el caso $n=2$ que es fácil de analizar. Se puede encontrar una prueba más ordenada en una línea similar aquí . De alguna manera se me olvidó que este resultado era en realidad un teorema con nombre, hasta que volví a ver esta pregunta hoy.

El siguiente resultado acaba con el problema:

Resultado: Dejemos que $n \geq 49$ sea un número entero positivo y que $a$ sea un número entero positivo par. Entonces existe un primo $q$ s.t. $q \nmid a$ y $ord_q(a)=n$ .

Nota: He editado una versión mejorada de esto al final.

Para ver por qué esto es suficiente, supongamos por un momento que hemos demostrado este resultado (La prueba se proporciona al final). Tomemos cualquier primo $p \geq 99, p \equiv 3 \pmod{8}$ y tomar $n=\frac{p-1}{2}, a=2$ en la declaración anterior. Entonces existe un primo $q \not =2$ s.t. $ord_q(2)=\frac{p-1}{2}$ . Desde $p \equiv 3 \pmod{8}$ , $(\frac{2}{p})=-1$ por lo que esto implica que $p \not =q$ . (ya que $ord_p(2) \not =\frac{p-1}{2}$ por el criterio de Euler).

Ahora, por el pequeño teorema de Fermat y la definición de orden, tenemos $\frac{p-1}{2}=ord_q(2) \mid q-1$ . También $2 \mid q-1$ . Desde $\frac{p-1}{2}$ es impar, obtenemos $p-1 \mid q-1$ . El pequeño teorema de Fermat da $ord_p(2) \mid p-1$ Así que $ord_p(2) \mid q-1$ . Así, $p \mid 2^{q-1}-1, q \mid 2^{p-1}-1, p \not =q$ Así que $pq \mid (2^{p-1}-1)+(2^{q-1}-1)$ . Dado que hay infinitas opciones para $p$ tenemos infinitos pares de primos $(p, q)$ satisfaciendo la condición.

Ahora viene la parte difícil. La siguiente es la prueba para el resultado que dije anteriormente.

Prueba del resultado: Tenemos $\prod_{d \mid n}{\Phi_d(x)}=x^n-1$ , donde $\Phi_n(x)$ es el $n$ th polinomio ciclotómico (que siempre es un polinomio con coeficientes enteros). Así, $a^n-1=\prod_{d \mid n, d \not =n}{\Phi_d(a)}\Phi_n(a)=k\Phi_n(a)$ , donde $k=\prod_{d \mid n, d \not =n}{\Phi_d(a)}$ es claramente un número entero que es divisible por $a^{\frac{n}{r}}-1$ para cada primo $r$ dividiendo $n$ .

Es evidente que basta con demostrar que existe un primo $q$ s.t. $q \mid \Phi_n(a), q \nmid k$ . Esto se debe a que entonces tenemos $q \mid k\Phi_n(a)=a^n-1$ y $q \nmid a^{\frac{n}{r}}-1$ para cada primo $r$ dividiendo $n$ (ya que $k$ es un múltiplo de $a^{\frac{n}{r}}-1$ ). Por lo tanto, $ord_q(a)=n$ . Está claro que $q \nmid a$ .

Considere un primo $p$ dividiendo ambos $\Phi_n(a)$ y $k=\prod_{d \mid n, d \not =n}{\Phi_d(a)}$ . Entonces $p \mid \Phi_d(a)$ para algunos $d \mid n, d \not =n$ Así que $p \mid a^d-1$ así que $p \mid a^{\frac{n}{r}}-1$ para algún primo $r$ dividiendo $n$ . Sea $b=a^{\frac{n}{r}}$ Así que $p \mid b-1$ . Tenga en cuenta que $b-1 \mid k$ Así que $\Phi(n)(a) \mid \frac{k}{b-1}\Phi_n(a)=\frac{a^n-1}{b-1}=\frac{b^r-1}{b-1}=1+b+b^2+ \ldots +b^{r-1}$ . Desde $b \equiv 1 \pmod{p}$ obtenemos $0 \equiv 1+b+b^2+ \ldots +b^{r-1} \equiv r \pmod{p}$ Así que $p=r \mid n$ . Por lo tanto, cualquier primo que divida a ambos $\Phi_n(a)$ y $k$ debe necesariamente dividir $n$ . Supongamos ahora que $r^i \|a^{\frac{n}{r}}-1$ . Desde $p=r$ y $p \mid a^{\frac{n}{r}}-1$ tenemos $i \geq 1$ . Desde $a$ es par, tenemos $r \not =2$ . Por lo tanto, por el lema de elevación del exponente, tenemos $r^{i+1} \|a^n-1=k\Phi_n(a)$ . Desde $a^{\frac{n}{r}}-1 \mid k$ tenemos $r^i \mid k$ Así que $r^2 \nmid \Phi_n(a)$ . Así, $p=r \|\Phi_n(a)$ .

Así, podemos escribir $\Phi_n(a)=st$ donde $s$ contiene todos los primos $p$ dividiendo $\Phi_n(a), k$ y $n$ simultáneamente, y cualquier primo que divida $t$ no divide $k$ . Por lo tanto, basta con demostrar que $t>1$ para que $t$ tiene un factor primo $q$ que luego se dividiría naturalmente $\Phi_n(a)$ pero no $k$ . Por encima, $s$ es libre de cuadrados, con todos los factores primos que dividen a $n$ Así que $s \mid n$ . Así, $s \leq n$ . Por lo tanto, basta con demostrar que $\Phi_n(a)>n$ (ya que implicaría $t>1$ ).

Ahora terminamos la prueba mostrando que $\Phi_n(a)>n$ . Recordemos que tenemos $n \geq 49$ . Para ello, utilizamos la fórmula de inversión de Möbius para obtener $\Phi_n(a)=\prod_{d \mid n}{(a^d-1)^{\mu(\frac{n}{d})}}$ . Así,

$$\Phi_n(a)=\frac{\prod_{d \mid n, \mu(\frac{n}{d})=1}{(a^d-1)}}{\prod_{d \mid n, \mu(\frac{n}{d})=-1}{(a^d-1)}}>\frac{\prod_{d \mid n, \mu(\frac{n}{d})=1}{a^{d-1}}}{\prod_{d \mid n, \mu(\frac{n}{d})=-1}{a^d}}=a^{\sum_{d \mid n}{d\mu(\frac{n}{d})}-\sum_{d \mid n, \mu(\frac{n}{d})=1}{1}}$$

donde hemos utilizado los límites brutos $a^d-1 \geq a^{d-1}$ y $\frac{1}{a^d-1}>\frac{1}{a^d}$ .

Es fácil ver que $\phi(n)=\sum_{d \mid n}{d\mu(\frac{n}{d})}$ . Si suponemos que $n=\prod_{i=1}^{m}{p_i^{a_i}}>1, m \geq 1$ , donde $a_i \geq 1$ y $p_1<p_2< \ldots$ entonces $\sum_{d \mid n, \mu(\frac{n}{d})=1}{1}=\sum_{d \mid n, \mu(d)=1}{1}=\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}$ . Tenga en cuenta que $0=\sum_{d \mid \prod_{i=1}^{m}{p_i}}{\mu(d)}=\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}-\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=-1}{1}$ y $\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}+\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=-1}{1}=\sum_{d \mid \prod_{i=1}^{m}{p_i}}{1}=2^m$ . Así, $\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}=2^{m-1}$ .

Por lo tanto, $$\Phi_n(a)>a^{\phi(n)-2^{m-1}} \geq 2^{\phi(n)-2^{m-1}}$$

Si $m=1$ entonces $n$ es un primo, por lo que claramente $2^{\phi(n)-2^{m-1}}=2^{n-2} \geq n$ desde $n \geq 49$ (De hecho, es cierto para $n \geq 4$ ). Por lo tanto, sólo tenemos que considerar el caso en el que $m \geq 2$ . Ahora bien, tenga en cuenta que $\phi(n)=n\prod_{i=1}^{m}{\frac{p_i-1}{p_i}} \geq n\prod_{i=1}^{m}{\frac{i}{i+1}}=\frac{n}{m+1}$ desde $p_i \geq i+1$ . Así, $\Phi_n(a)>2^{\frac{n}{m+1}-2^{m-1}}$ . Por lo tanto, basta con demostrar que $2^{\frac{n}{m+1}-2^{m-1}} \geq n$ . Esto parece sencillo.

Obsérvese el límite trivial $n=\prod_{i=1}^{m}{p_i^{a_i}} \geq \prod_{i=1}^{m}{p_i} \geq 2\prod_{i=2}^{m}{2(i-1)}=2^m(m-1)!$ . También tenemos la desigualdad $2^z \geq z^2$ para $z \geq 4$ .

Si $m \geq 5$ . Entonces $2^{2m-2}=2^m(2^{m-2}) \leq 2^m(m-1)! \leq n$ así que $2^{m-1} \leq \sqrt{n}$ . También $n \geq 2^m(m-1)! \geq m^2(m-1)! \geq 24m^2>4(m+1)^2$ Así que $m+1 \leq \frac{\sqrt{n}}{2}$ . Así, $\frac{n}{m+1}-2^{m-1} \geq 2\sqrt{n}-\sqrt{n}=\sqrt{n}$ . Así, $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq (\sqrt{n})^2=n$ desde $n \geq 49>16$ .

Por lo tanto, basta con considerar $m=2, 3, 4$ .

Si $m=4$ entonces $n \geq \prod_{i=1}^{m}{p_i} \geq 2(3)(5)(7) \geq 210$ Así que $\sqrt{n} \geq 10$ . Así, $n \geq 10\sqrt{n} \geq 5\sqrt{n}+50$ Así que $\frac{n}{m+1}-2^{m-1}=\frac{n}{5}-8 \geq \sqrt{n}+10-8>\sqrt{n}$ Así que, como $\sqrt{n} \geq 4$ , $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq n$ .

Si $m=3$ Entonces, como $n \geq 49$ tenemos $\sqrt{n} \geq 7$ Así que $n \geq 7\sqrt{n} \geq 4\sqrt{n}+21>4\sqrt{n}+16$ así que $\frac{n}{m+1}-2^{m-1}=\frac{n}{4}-4 \geq \sqrt{n}$ Así que, como $\sqrt{n} \geq 4$ , $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq n$ .

Si $m=2$ Entonces, como $n \geq 49$ tenemos $\sqrt{n} \geq 7$ Así que $n \geq 7\sqrt{n} \geq 3\sqrt{n}+28>3\sqrt{n}+6$ así que $\frac{n}{m+1}-2^{m-1}=\frac{n}{3}-2\geq \sqrt{n}$ Así que, como $\sqrt{n} \geq 4$ , $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq n$ .

Por lo tanto, hemos demostrado que $\Phi_n(a)>n$ y hemos terminado.

Para los que hayan leído hasta el final, siento que acabo de hacer el equivalente a matar un mosquito... Seguramente hay una manera más sencilla de resolver el problema, sin probar un resultado más fuerte.

Edición: Aquí he incorporado los comentarios de abajo a mi respuesta, para obtener una versión mejorada del resultado expuesto anteriormente.

Consideraremos el caso general, en el que $a>1$ y $n>2$ son enteros positivos. Cuando $a$ es par, ya hemos demostrado el resultado para $n \geq 49$ . Considere impar $a>1$ y $n>2$ . La prueba anterior sigue funcionando hasta el punto en el que utilicé el Lemma del Exponente Elevado, ya que ahora desde $a$ es impar, podríamos tener $r=2$ .

Si $n$ es impar, entonces $p=r \mid n$ así que $r \not =2$ y el resto de la prueba es la siguiente. Si $4 \mid n$ , entonces para $r \not =2$ la prueba sigue funcionando. Considere $r=2$ . Desde $\frac{n}{r}$ es par, tenemos $4 \mid a^{\frac{n}{r}}-1$ por lo que aún podemos utilizar el lema de elevación del exponente para obtener $r^{i+1} \|a^n-1$ y el resto de la prueba es la siguiente. Por último, si $n \equiv 2 \pmod{4}$ ya que $n>2$ , $n$ tiene un factor primo impar $u$ Así que, como $4 \mid a^{\frac{n}{u}}-1$ y $2 \nmid u$ tenemos $v_2(a^{\frac{n}{u}}-1)=v_2(a^n-1)$ mediante la elevación del lema del exponente. Dado que $a^{\frac{n}{u}}-1 \mid k$ y $a^n-1=k\Phi_n(a)$ Esto implica que $\Phi_n(a)$ es impar, así que $r \not =2$ y el resto de la prueba es la siguiente.

Para ello, basta con comprobar que $\Phi_n(a)>n$ . Esto ya se ha demostrado anteriormente para $n \geq 49$ Así que sólo tenemos que preocuparnos de $n \leq 48$ . Ahora consideramos que impar e incluso $a>1$ juntos. (Tenga en cuenta que sólo utilizamos $n \geq 49$ para demostrar que $\Phi_n(a)>n$ anterior, por lo que la prueba hasta este punto sigue funcionando para pequeños $n$ )

(Gracias a @DavidSpeyer por esta simplificación) Considera $\zeta$ , un primitivo $n$ raíz de la unidad. Entonces $(a-\zeta)(a-\zeta^{-1}) \geq (a-1)^2$ Así que $\Phi_n(a)=\prod_{1 \leq k \leq n \atop \gcd(k, n=1)}{a-e^{2i \pi \frac{k}{n}}} \geq (a-1)^{\phi(n)}$ . Tenemos $\phi(n) \geq \sqrt{n}$ para $n \not =2, 6$ . Si $a \geq 4$ , entonces para $n \not =6$ tenemos $\Phi_n(a) \geq (a-1)^{\phi(n)} \geq 3^{\sqrt{n}}>n$ . Para $n=6$ tenemos $\Phi_6(a) \geq 3^{\phi(6)}=9>6$ . Por lo tanto, hemos terminado cuando $a \geq 4$ .

Cuando $a=3$ el mismo enfoque da para $n \geq 17$ que $\Phi_n(3) \geq 2^{\sqrt{n}}>n$ . Por lo tanto, nos queda considerar $a=2, 3 \leq n \leq 49$ y $a=3, 3 \leq n \leq 16$ que se puede comprobar fácilmente con un ordenador para ver que la única excepción es $(a, n)=(2, 6)$ .

Por lo tanto, tenemos:

Teorema: Dejemos que $a>1, n>2$ sean enteros positivos y supongamos que $(a, n) \not =(2, 6)$ . Entonces existe un primo $q$ s.t. $q \nmid a$ y $ord_q(a)=n$ .

Answer 2

Nadie lo ha dicho explícitamente todavía: La fórmula de Robert Israel siempre funciona. Dejemos que $(p,q) = (4k+1, 8k+1)$ . En una dirección, $2^{q-1} -1 = (2^{p-1})^2-1$ y sabemos $2^{p-1} \equiv 1 \mod p$ así que $p | 2^{q-1}-1$ . En la otra dirección, ya que $q \equiv 1 \mod 8$ tenemos $\left( \frac{2}{q} \right) = 1$ así que $2^{(q-1)/2} \equiv 1 \mod q$ y $q | 2^{(q-1)/2}-1=2^{p-1}-1$ .

Answer 3

Una pista:

$p,q > 3$

$pq|2^{p-1}+2^{q-1}-2$

Reencuadrar para $pq|(2^{q-1}-1)+(2^{p-1}-1)$ Ahora ya sabes $2^{q-1}-1 \equiv 0(\mod q)$ y de manera similar $2^{p-1}-1 \equiv 0(\mod p)$ .

$\dfrac{pk+qt}{pq}=s$ Para algunos $k,t,s \in \mathbb{N}$

Si consideramos el caso, $p$ y $q=2p-1$ (Sí, tomando la pista del comentario de Robert Israel, $p \equiv 1(\mod 4)$ )

$2^{p-1}-1 \equiv 0(\mod p)$ y $2^{2p-2}-1 \equiv (\mod q) \implies (2^{\frac{2p-2}{2}}-1)(2^{\frac{2p-2}{2}}+1) \equiv 0(\mod q)$

Todavía no se sabe que $(p,2p-1)$ los pares de primos son infinitos.

Answer 4

Ver también http://www.mathsolympiad.org.nz/wp-content/uploads/2010/04/2010squad-nt-soln.pdf (última página) para una solución elemental que no se basa en el teorema de Zsigmondy.