2003 IMO Shortlist S03

The sequence $a_0$ , $a_1$ , $a_2,$ $\ldots$ is defined as follows: $$a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.$$ Prove that if an odd prime $p$ divides $a_n$ , then $2^{n+3}$ divides $p^2-1$ .

<details><summary>comment</summary>Hi guys ,

Here is a nice problem:

Let be given a sequence $a_n$ such that $a_0=2$ and $a_{n+1}=2a_n^2-1$ . Show that if $p$ is an odd prime such that $p|a_n$ then we have $p^2\equiv 1\pmod{2^{n+3}}$ Here are some futher question proposed by me :Prove or disprove that :
1) $gcd(n,a_n)=1$ 2) for every odd prime number $p$ we have $a_m\equiv \pm 1\pmod{p}$ where $m=\frac{p^2-1}{2^k}$ where $k=1$ or $2$ Thanks kiu si u

*Edited by Orl.*</details>

序列 $a_0$ , $a_1$ , $a_2,$ $\ldots$ 定义如下： $$a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.$$ 证明如果奇素数 $p$ 整除 $a_n$ ，则 $2^{n+3}$ 整除 $p^2-1$ 。

<details><summary>comment</summary>大家好，

这是一个很好的问题：

给定一个序列 $a_n$ ，使得 $a_0=2$ 和 $a_{n+1}=2a_n^2-1$ 。证明如果 $p$ 是奇素数，使得 $p|a_n$ 则我们有 $p^2\equiv 1\pmod{2^{n+3}}$ 以下是我提出的一些进一步的问题：证明或反驳：
1) $gcd(n,a_n)=1$ 2) 对于每个奇素数 $p$ 我们有 $a_m\equiv \pm 1\pmod{p}$ 其中 $m=\frac{p^2-1}{2^k}$ 其中 $k=1$ 或 $2$ 谢谢 kiu si u

*奥尔编辑。*</详情>