Problem 1421

To prove that for each positive integer $n$, $n$ and $a_n$ are coprime, we will use induction and properties of the sequence defined by $a_1 = 2$ and $a_{n+1} = 2a_n^2 - 1$.

1. Base Case:
For $n = 1$, $a_1 = 2$. Clearly, $\gcd(1, 2) = 1$, so $1$ and $a_1$ are coprime.

2. Inductive Step:
Assume that for some $k \geq 1$, $k$ and $a_k$ are coprime, i.e., $\gcd(k, a_k) = 1$. We need to show that $k+1$ and $a_{k+1}$ are also coprime.

Given $a_{k+1} = 2a_k^2 - 1$, we need to show that $\gcd(k+1, 2a_k^2 - 1) = 1$.

3. Using the Inductive Hypothesis:
Suppose $p$ is a prime divisor of both $k+1$ and $a_{k+1}$. Then $p \mid 2a_k^2 - 1$. Since $p \mid k+1$, we have $k+1 \equiv 0 \pmod{p}$.

4. Residue Analysis:
Let $b_i = a_i \mod p$ be the residue of $a_i$ modulo $p$. We need to analyze the sequence $b_i$ modulo $p$.

- If $b_k = 0$, then $a_k \equiv 0 \pmod{p}$. This implies $a_{k+1} = 2a_k^2 - 1 \equiv -1 \pmod{p}$, so $b_{k+1} \equiv -1 \pmod{p}$. Hence, $p \nmid a_{k+1}$.
- If $b_k = 1$, then $a_k \equiv 1 \pmod{p}$. This implies $a_{k+1} = 2a_k^2 - 1 \equiv 1 \pmod{p}$. Hence, $p \nmid a_{k+1}$.

5. Pigeonhole Principle:
If $b_k \neq 0, 1$ for $1 \leq k \leq p-1$, by the pigeonhole principle, there must exist indices $1 \leq i < j \leq p-1$ such that $b_i = b_j$. This implies that the sequence $b_i$ is periodic with period $j - i$ without ever being zero. Hence, $p \nmid a_{k+1}$.

6. Conclusion:
Since $p \nmid a_{k+1}$ for any prime $p$ dividing $k+1$, it follows that $\gcd(k+1, a_{k+1}) = 1$.

By induction, we have shown that for all $n \geq 1$, $\gcd(n, a_n) = 1$.

$\blacksquare$