¿Existe un número primo $p$ tal que $\gcd(p, 2^n+3^n+6^n-1)=1 \forall n\ge 1$?

Question

¿Existe un número primo $p$ tal que $\gcd(p, 2^n+3^n+6^n-1)=1 \forall n\ge 1$?

Eso fue de una Olimpiada de matemáticas en la que participé hoy. No resolví el problema, pero tengo algo que decir antes de presentar mi enfoque. La formulación del problema me confundió. No sabía cuál declaración era verdadera, típicamente cuando ves este tipo de preguntas probablemente pienses que la respuesta es NO, pero dado que el problema es difícil, pensé que la respuesta era SÍ y luego intenté encontrar tal $p$ pero tampoco funcionó.

Supongamos $\exists p$ tal que $\forall n\ge 1$, $d=\gcd(p,2^n+3^n+6^n-1)=1$. Y nota que $p\neq2$ porque $2^n+3^n+6^n-1$ es par y $p\neq3$ porque $n=2$ es un contraejemplo. Así que $\gcd(2,p)=(3,p)=1$. Aquí intenté construir un contraejemplo es decir, $\exists n$ tal que $\forall p, d>1$ pero no tuve éxito al construirlo.

Answer 1

Este es un problema interesante, hay una solución simple que es difícil de encontrar, y realmente no encaja en un patrón de otros problemas similares.

La respuesta es realmente NO. El OP ya ha descartado $p=2,3$, así que supongamos que $p\ge5$. Afirmamos que $n=p-2$ da un máximo común divisor no trivial, a saber $\gcd(p,K)=p$ cuando $K=2^{p-2}+3^{p-2}+6^{p-2}-1$.

Para ver esto, es suficiente mostrar que $\gcd(p,6K)=p$ ya que sabemos que $\gcd(p,6)=1$. Pero $$ 6K = 3\cdot 2^{p-1}+2\cdot 3^{p-1}+6^{p-1}-6 \equiv 3\cdot1+2\cdot1+1-6=0\pmod p $$ por tres aplicaciones del pequeño teorema de Fermat, ya que $\gcd(p,2)=\gcd(p,3)=\gcd(p,6)=1$.

De forma informal, $a^{p-1}\equiv1\pmod p$ significa que $a^{p-2}\equiv\frac1a\pmod p$, y así $K$ es realmente $\frac12+\frac13+\frac16-1\pmod p$, si eso explica la "coincidencia". También se puede notar el patrón $n=p-2$ al probar varios pequeños primos $p$ individualmente.