Since $$\frac{a_{n+2}+a_{n}}{a_{n+1}}=14=\frac{a_{n+1}+a_{n-1}}{a_{n}},$$$$a_{n+1}^2-a_{n+2}a_{n}=-12.$$Therefore if $p|a_n$, then $p|a_{n+1}^2+12$, so $$\left( \frac{-12}{p} \right)=1,$$which is equivalent to $3 | p-1$. We still need to check about $4 | p-1$. (will fix later)

wow! made by Jeon

mathlove_13520 wrote: Since $$\frac{a_{n+2}+a_{n}}{a_{n+1}}=14=\frac{a_{n+1}+a_{n-1}}{a_{n}},$$$$a_{n+1}^2-a_{n+2}a_{n}=-12.$$Therefore if $p|a_n$, then $p|a_{n+1}^2+12$, so $$\left( \frac{-12}{p} \right)=1,$$which is equivalent to $12 | p-1$, as desired. 근데 p가 12k+7꼴일 때도 (-12/p)=1 아닌가요..?

foolish07 wrote: mathlove_13520 wrote: Since $$\frac{a_{n+2}+a_{n}}{a_{n+1}}=14=\frac{a_{n+1}+a_{n-1}}{a_{n}},$$$$a_{n+1}^2-a_{n+2}a_{n}=-12.$$Therefore if $p|a_n$, then $p|a_{n+1}^2+12$, so $$\left( \frac{-12}{p} \right)=1,$$which is equivalent to $12 | p-1$, as desired. 근데 p가 12k+7꼴일 때도 (-12/p)=1 아닌가요..? Yes, indeed $\left( \frac{-12}{p} \right)=1$ only implies $p\equiv 1\pmod3$, so more work needs to be done.

For proving $4\mid p-1$ we can do as follows: Let $a=2+\sqrt{3}$ and note $7+4\sqrt 3=a^2$ We can see easily that $a_{n+1}=\frac{(2-\sqrt 3)(7+4\sqrt 3)^n+(2+\sqrt 3)(7-4\sqrt 3)^n}{4}=\frac{1}{4}\cdot (a^{2n-1}+\frac{1}{a^{2n-1}})$ The key is that $a_n=x^2+(x+1)^2$ for some $x\in \mathbb{Z}$ which clearly finishes the problem. Solving the equation we get that $$x=\frac{\sqrt{2a^{2n-1}+\frac{2}{a^{2n-1}}-4}-2}{4}$$But $2a^{2n-1}+\frac{2}{a^{2n-1}}-4=((\sqrt{3}+1)\cdot a^{n-1}-(\sqrt{3}-1)\cdot \frac{1}{a^{n-1}})^2$ so we have to prove that $$\frac{(\sqrt{3}+1)\cdot a^{n-1}-(\sqrt{3}-1)\cdot \frac{1}{a^{n-1}}-2}{4}\in \mathbb{Z}$$. Write $a^{n-1}=A+B\sqrt{3}$ and $\frac{1}{a^{n-1}}=A-B\sqrt{3}$ and plugging in we want to show that $A+B$ is odd,but this is simple: $$A=\sum_{k=0,even}^{n}{3^{\frac{k}{2}}\cdot 2^{n-k}\cdot \binom{n}{k}}$$and $$B=\sum_{k=0,odd}^{n}{3^{\frac{k-1}{2}}\cdot 2^{n-k}\cdot \binom{n}{k}}$$and it is easy to see that for parity only $k=n$ matters which appears in one sum which is odd,the other is even and so the problem is solved.

motannoir wrote: For proving $4\mid p-1$ we can do as follows: Let $a=2+\sqrt{3}$ and note $7+4\sqrt 3=a^2$ We can see easily that $a_{n+1}=\frac{(2-\sqrt 3)(7+4\sqrt 3)^n+(2+\sqrt 3)(7-4\sqrt 3)^n}{4}=\frac{1}{4}\cdot (a^{2n-1}+\frac{1}{a^{2n-1}})$ The key is that $a_n=x^2+(x+1)^2$ for some $x\in \mathbb{Z}$ which clearly finishes the problem. Solving the equation we get that $$x=\frac{\sqrt{2a^{2n-1}+\frac{2}{a^{2n-1}}-4}-2}{4}$$But $2a^{2n-1}+\frac{2}{a^{2n-1}}-4=((\sqrt{3}+1)\cdot a^{n-1}-(\sqrt{3}-1)\cdot \frac{1}{a^{n-1}})^2$ so we have to prove that $$\frac{(\sqrt{3}+1)\cdot a^{n-1}-(\sqrt{3}-1)\cdot \frac{1}{a^{n-1}}-2}{4}\in \mathbb{Z}$$. Write $a^{n-1}=A+B\sqrt{3}$ and $\frac{1}{a^{n-1}}=A-B\sqrt{3}$ and plugging in we want to show that $A+B$ is odd,but this is simple: $$A=\sum_{k=0,even}^{n}{3^{\frac{k}{2}}\cdot 2^{n-k}\cdot \binom{n}{k}}$$and $$B=\sum_{k=0,odd}^{n}{3^{\frac{k-1}{2}}\cdot 2^{n-k}\cdot \binom{n}{k}}$$and it is easy to see that for parity only $k=n$ matters which appears in one sum which is odd,the other is even and so the problem is solved. It's hard for me.. And thank you for writing the solution

I believe this is fairly easy? Tell me if there are any mistakes, thanks. We note that \(\{a_n\}\) represents all solutions for \(x\) in the equation \(4x^2 - 3y^2 = 1\). We will prove that for any prime \(p\) such that \(4x^2 - 3y^2 = 1\) and \(p \mid x\), it follows that \(12 \mid (p-1)\). Since \(y\) is an odd number, considering modulo 8, we have \(p \neq 2\). First, since \(p \mid (3y^2 + 1)\), we have \(\left(\frac{-3}{p}\right) = 1\). By the quadratic reciprocity law, this implies \(\left(\frac{p}{3}\right) = 1\), and hence \(3 \mid (p-1)\). Consider the equation \(3y^2 = (2x+1)(2x-1)\). This implies: \[ \begin{cases} 2x + 1 = 3u^2 \\ 2x - 1 = v^2 \end{cases} \quad \text{or} \quad \begin{cases} 2x + 1 = v^2 \\ 2x - 1 = 3u^2 \end{cases} \] where \(u\) and \(v\) are integers. The second case leads to \(v^2 \equiv 2 \pmod{3}\), which is impossible. Thus, we must have \(2x + 1 = 3u^2\) and \(2x - 1 = v^2\). Hence \(p \mid (v^2 + 1)\), and therefore \(4 \mid (p-1)\). Combining these results, we conclude that \(12 \mid (p-1)\).

zhihanpeng wrote: I believe this is fairly easy? Tell me if there are any mistakes, thanks. We note that \(\{a_n\}\) represents all solutions for \(x\) in the equation \(4x^2 - 3y^2 = 1\). We will prove that for any prime \(p\) such that \(4x^2 - 3y^2 = 1\) and \(p \mid x\), it follows that \(12 \mid (p-1)\). Since \(y\) is an odd number, considering modulo 8, we have \(p \neq 2\). First, since \(p \mid (3y^2 + 1)\), we have \(\left(\frac{-3}{p}\right) = 1\). By the quadratic reciprocity law, this implies \(\left(\frac{p}{3}\right) = 1\), and hence \(3 \mid (p-1)\). Consider the equation \(3y^2 = (2x+1)(2x-1)\). This implies: \[ \begin{cases} 2x + 1 = 3u^2 \\ 2x - 1 = v^2 \end{cases} \quad \text{or} \quad \begin{cases} 2x + 1 = v^2 \\ 2x - 1 = 3u^2 \end{cases} \] where \(u\) and \(v\) are integers. The second case leads to \(v^2 \equiv 2 \pmod{3}\), which is impossible. Thus, we must have \(2x + 1 = 3u^2\) and \(2x - 1 = v^2\). Hence \(p \mid (v^2 + 1)\), and therefore \(4 \mid (p-1)\). Combining these results, we conclude that \(12 \mid (p-1)\). Can you explain me why \(\{a_n\}\) represents all solutions for \(x\) in the equation \(4x^2 - 3y^2 = 1\) ?

(-1/p)=1 because 2a_n-1 is always a perfect square.. It's Romania tst 2002

foolish07 wrote: mathlove_13520 wrote: Since $$\frac{a_{n+2}+a_{n}}{a_{n+1}}=14=\frac{a_{n+1}+a_{n-1}}{a_{n}},$$$$a_{n+1}^2-a_{n+2}a_{n}=-12.$$Therefore if $p|a_n$, then $p|a_{n+1}^2+12$, so $$\left( \frac{-12}{p} \right)=1,$$which is equivalent to $12 | p-1$, as desired. 근데 p가 12k+7꼴일 때도 (-12/p)=1 아닌가요..? Don't use Choseon-eo in AoPS.

hanulyeongsam wrote: foolish07 wrote: mathlove_13520 wrote: Since $$\frac{a_{n+2}+a_{n}}{a_{n+1}}=14=\frac{a_{n+1}+a_{n-1}}{a_{n}},$$$$a_{n+1}^2-a_{n+2}a_{n}=-12.$$Therefore if $p|a_n$, then $p|a_{n+1}^2+12$, so $$\left( \frac{-12}{p} \right)=1,$$which is equivalent to $12 | p-1$, as desired. 근데 p가 12k+7꼴일 때도 (-12/p)=1 아닌가요..? Don't use Choseon-eo in AoPS. 왜

MNJ2357 wrote: Define the sequence $\{a_n\}_{n=1}^\infty$ as \[ a_1 = a_2 = 1,\quad a_{n+2} = 14a_{n+1} - a_n \; (n \geq 1) \]Prove that if $p$ is prime and there exists a positive integer $n$ such that $\frac{a_n}p$ is an integer, then $\frac{p-1}{12}$ is also an integer. Well there are some solutions above, I will present a new one... Let $b_n$ be the $n$-th term of https://oeis.org/A001075. Then $a_n=\frac{b_{2n-3}}{2}$. Since $b_n$ is indeed $\cosh nx$ for some $x$, it satisfies the Chebyshev polynomial: $b_{4n}=8b_n^4-8b_n^2+1$. Then $\Phi_{12}(b_n)=b_n^4-b_n^2+1=\frac{b_{4n}+7}{8}=\frac{b_{4n}+b_2}{8}=\frac{b_{2n+1}b_{2n-1}}{4}=a_{n+1}a_{n+2}$. Yes, $b_n$ has order $12$ mod any prime divisor of $a_{n+1}a_{n+2}$.

Let's define the sequence $b_n $ as $b_{n+2}=4b_{n+1}-b_{n}+1, b_1=-1, b_2=0$. Then $a_{n}=b_{n}^2+(b_{n}+1)^2$