Si $a_{n}$ es un número primo, es $n$ es también un número primo?

Question

Deje que $a_{n}$ ser el $n^ \text {th}$ término de una secuencia. Deje que $a_{n}$ se definirá de la siguiente manera:

$$a_n= \begin {cases} 1 & n = 1 \\ 2 & n = 2 \\ 2a_{n-1}+a_{n-2} & n \ge 3 \end {cases}$$

¿Podemos decir que "si $a_{n}$ es un número primo, entonces $n$ es también un número primo" ?

Answer 1

Pista Así como aquí son un fuerte divisibilidad secuencia, es decir. $\, \gcd (a_m,a_n) = a_{ \gcd (m,n)}.\,$ En particular $\, m \mid n\, \Rightarrow\ , a_m \mid a_n,\,$ así que $\,n\,$ compuesto $\, \Rightarrow\ , a_n\,$ compuesto así, contra+, $\, a_n\,$ prime $\, \Rightarrow\ , n\,$ de primera clase.

Answer 2

Aquí hay un esquema de una prueba que si $m|n$ entonces $a_m|a_n;$ a partir de ahí, es fácil argumentar su reclamo.

Deje que $n=km.$ Basta con mostrar $a_m|a_{km}$ para $k=2$ y $k$ impar.

Como se ha mencionado en los comentarios, $a_n= \dfrac { \alpha ^n- \dfrac1 {(- \alpha )^n}}{2 \sqrt2 }$ donde $\alpha =1+ \sqrt2$ .

Definir otra secuencia $b_n$ de la misma manera que $a_n$ excepto $b_2=3$ . Luego $b_n= \dfrac { \alpha ^n+ \dfrac1 {(- \alpha )^n}}{2}.$

Es fácil mostrar que $a_{2m}=2a_mb_m$ así que $a_m|a_{2m},$ y hemos terminado con el caso $\dfrac nm=2$ .

Para probar $a_m|a_{(2l-1)m},$ usar una fuerte inducción en $l$ .

El caso base ( $l=1$ ) es trivial.

Ahora asume $a_m|a_{(2i-1)m}$ para $i=1$ a $l.$ Para mostrar $a_m|a_{(2l+1)m}$ ,

nota $a_m^{2l+1}= \left ( \dfrac { \alpha ^m+ \dfrac {(-1)^{m+1}}{ \alpha ^m}}{2 \sqrt2 } \right )^{2l+1}= \dfrac { \left ( \alpha ^m+ \dfrac {(-1)^{m+1}}{ \alpha ^m} \right )^{2l+1}}{2^{3l}2 \sqrt2 }.$

Por lo tanto, usando la expansión del binomio, $2^{3l}a_m^{2l+1}= \dfrac { \left ( \alpha ^{m(2l+1)}- \dfrac1 {(- \alpha )^{m(2l+1)}} \right )}{2 \sqrt2 }+...$

$=a_{m(2l+1)}+$ suma de términos que son coeficientes binomiales veces $a_{(2i-1)m}, 1 \le i \le l.$

El lado izquierdo de esta ecuación $(2^{3l}a_m^{2l+1})$ es un múltiplo de $a_m$ ,

y la suma de los términos es un múltiplo de $a_m$ (debido a la hipótesis de la inducción),

así que $a_{m(2l+1)}$ es un múltiplo de $a_m$ .

Answer 3

Deje que $S$ ser el operador de turno en las secuencias ( $Sa_n=a_{n+1})$ . Luego $$(S^2-2S-1)a_n=0 \tag1$$ Por inducción, también tenemos $$\left (S^{2k}-d_kS^k+(-1)^k \right )a_n=0 \tag2$$ donde $d_k$ se define por $d_0=2$ , $d_1=2$ , $d_k=2d_{k-1}+d_{k-2}$ . Además, mediante la inducción en $m$ , $$\left (S^{km}-e_{k,m}S^k+(-1)^ke_{k,m-1} \right )a_n=0 \tag3$$ donde $e_{k,m}$ se define por $e_{k,0}=0$ , $e_{k,1}=1$ , $e_{k,m}=d_ke_{k,m-1}-(-1)^ke_{k,m-2}$ . Entonces, ya que $a_0=0$ , $$a_{km}=e_{k,m}a_k \tag4$$ Por lo tanto, si $k \mid n$ Entonces $a_k \mid a_n$ . Contrapositivo, si $a_n$ es primordial, entonces $n$ es primordial.

Answer 4

Si no estás tan familiarizado con este material como yo, puede que encuentres esta "incursión" en las técnicas de matrices de Bill Dubuque una forma útil de poner tu dedo en el agua.

Mono ver, mono hacer (sólo rascando la superficie):

$$A_n := \begin {bmatrix} a_{n+1} &\!\! a_{n} \\ a_{n} &\!\!\! a_{n-1} \end {bmatrix} = \begin {bmatrix}2 &1 \\ 1 & 0 \end {bmatrix}^n\! =\, A_1^n$$

$$\,A_{m+n} = A_1^{m+n} = A_1^m A_1^n = A_m A_n,\ $$

$$\ a_{m+n} =\, a_{m+1} a_n +a_m a_{n-1}$$

Ejemplo de divisibilidad:

$a_6 \;= a_4 a_3 + a_3 a_2$
$a_9 \;= a_7 a_3 + a_6 a_2$
$a_{12} = a_{10} a_3 + a_9 a_2$
etc.

Así que $a_3 \mid a_{3k}$ para todos $k \ge 1$ .

Con este ejemplo en mente, se puede construir una prueba que muestre que cuando $\, m \mid n$ ,
debe seguir que $\, a_m \mid a_n$ .

---

Es interesante comparar esta secuencia con el tema

Generando todos los pares de coprime

La secuencia de la OP corresponde al uso de $\text {[Branch 2]}$ para definir una recursividad que comienza con $(2,1)$ .
Así que cualquier dos términos adyacentes $a_n$ y $a_{n+1}$ son coprimas.