Pregunta de Putnam '89: Primas de la forma $101\ldots01$

Question

No soy de matemáticas, pero me gustaría competir en el Putnam. Como se ha sugerido en otras preguntas aquí, estoy trabajando en algunos problemas de concursos antiguos. Me gustaría que me dieran su opinión sobre este intento de prueba. La opinión general es bienvenida, pero tengo algunas preguntas específicas (ver al final del post).

Prompt:

¿Cuántos números primos entre los enteros positivos, escritos como es habitual en la base 10, son tales que sus dígitos son 1's y 0's alternados, empezando y terminando por 1?

Fuente: http://www.math.ksu.edu//events/ksucomp/putnam/examquestions.htm

Respuesta: Sólo hay un primo de este tipo, a saber, $101$ .

Prueba:

Consideremos los números de la forma $101\ldots01$ . Dejemos que $a_n$ sea el número de esta forma con $n$ unos en su representación de base-10. Es decir: $$a_n = \sum_{k=0}^{n-1}10^{2k} \tag{1}$$ Es lo que sigue: $$\begin{align} a_n &= \sum_{k=0}^{n-1}\left(10^2\right)^k \\ &= \frac{\left(10^2\right)^n-1}{10^2-1} \\ &= \frac{(10^n)^2-1}{99} \\ &= \frac{(10^n-1)(10^n+1)}{9\cdot 11} \end{align}$$

Ahora observamos que $10^n-1=9\sum_{k=0}^{n-1}10^k$ . Así:

$$a_n = \frac{\left(\sum_{k=0}^{n-1}10^k\right)(10^n+1)}{11} \tag{2}$$

Dejemos que $b_n$ sea el numerador en $(2)$ eso es: $$b_n = \left(\sum_{k=0}^{n-1}10^k\right)(10^n+1)$$

De la fórmula $(1)$ podemos ver que $a_n$ es la suma de enteros, por lo tanto, $a_n$ es claramente un número entero. Para $a_n$ para ser un primo, $b_n$ debe satisfacer lo siguiente: $$b_n = 11\cdot p\text{, where $ p $ is prime.}$$

Por lo tanto, uno de los dos $\left(\sum_{k=0}^{n-1}10^k\right)$ o $(10^n+1)$ debe ser $11$ y el otro es primo. Para $n=1$ lo vemos: $$\left(\sum_{k=0}^{n-1}10^k\right) = 1;\qquad(10^n+1)=11$$ Para $n=2$ lo vemos: $$\left(\sum_{k=0}^{n-1}10^k\right) = 11;\qquad(10^n+1)=101$$ Como ambos términos son monótonamente crecientes, estas dos son las únicas formas de que cualquiera de ellos sea igual a $11$ . De estos dos, sólo un par contiene un primo (a saber, $101$ ).

---

Mis preguntas:

Ante todo, quiero saber si mi prueba es válida/está bien encaminada. :) Después, me gustaría saber si estoy cubriendo la prueba con suficiente detalle. Específicamente:

1. Afirmo que $10^n-1=9\sum_{k=0}^{n-1}10^k$ . ¿Necesito demostrarlo, o es suficientemente obvio? (Restando $1$ de un poder de $10$ deja un número con tantos $9$ s como hay $0$ 's en el poder de $10$ .)
2. ¿Necesito mostrar más por qué $b_n$ debe ser $11$ ¿veces un primo? ¿O está claro que todos los demás casos son compuestos $a_n$ ?
3. ¿Es legítimo mi razonamiento de que sólo existen estas dos soluciones (es decir, términos monotónicamente crecientes)?

Y, por último, ¿hay algún teorema bien conocido que haya pasado totalmente por alto y que facilite la resolución de este problema?

Answer 1

En realidad, puedes acortar tu prueba un poco antes, una vez que tengas $a_n=(10^n+1)(10^n-1)/99$ se puede observar que para $n\gt 2$ ambos factores son mayores que $2\times 99$ por lo que debe existir una factorización de $a_n$ en dos números, cada uno mayor que $2$ .

Más formalmente, se puede dividir en el caso de incluso $n$ e impar $n$ para incluso $n$ entonces $99|10^n-1$ por lo que tiene $a_n=(10^n+1)\times \left((10^n-1)/99\right)$ con cada factor $\gt 1$ mientras que para impar $n$ $11| 10^n+1$ y $9|10^n-1$ así que $a_n=\left((10^n+1)/11\right)\times\left((10^n-1)/9\right)$ con cada factor $\gt 1$ . (Estas propiedades de divisibilidad son inmediatas a partir de $10\equiv 1\pmod 9$ y $10\equiv -1\pmod{11}$ ). Esto también explica por qué la prueba se rompe en $n=2$ allí, usted todavía tiene $a_n=(10^n+1)\times\left((10^n-1)/99\right)$ pero ya no es el caso que el factor correcto sea $\gt 1$ .

Answer 2

Su prueba me parece buena. Aquí hay una prueba alternativa, que no es necesariamente mejor pero fue lo primero que se me ocurrió:

Dejemos que $a_n$ sea como en su prueba. Es fácil ver que si $m\mid n$ entonces $a_m\mid a_n$ (basta con considerar el proceso de la división larga). Al inspeccionar, encontré que si $n$ es impar entonces $$a_n=\left(\sum\limits_{k=0}^n 10^k\right)\left(1+\sum\limits_{k=0}^{(n-1)/2}9\cdot 10^{2k}\right).$$ Así, $a_n$ sólo puede ser primo cuando $n$ es un primo par, es decir $n=2$ .