Junior Balkan Mathematics Olympiad

Solution:

a) Note that $65 = 5 \cdot 13$.
Obviously, $5 = 2^{2} + 1$ is a divisor of $\left(2^{2}\right)^{2n+1} + 1 = 2^{4n+2} + 1$ for any positive integer $n$. Since $2^{12} \equiv 1 \pmod{13}$, if $n \equiv r \pmod{3}$, then $2^{4n+2} + 1 \equiv 2^{4r+2} + 1 \pmod{13}$. Now, $2^{4 \cdot 0 + 2} + 1 = 5$, $2^{4 \cdot 1 + 2} + 1 = 65$, and $2^{4 \cdot 2 + 2} + 1 = 1025 = 13 \cdot 78 + 11$. Hence $13$ is a divisor of $2^{4n+2} + 1$ precisely when $n \equiv 1 \pmod{3}$. Hence, $A_{n}$ is an integer iff $n \equiv 1 \pmod{3}$.

b) Applying the identity $4x^{4} + 1 = \left(2x^{2} - 2x + 1\right)\left(2x^{2} + 2x + 1\right)$, we have $2^{4n+2} + 1 = \left(2^{2n+1} - 2^{n+1} + 1\right)\left(2^{2n+1} + 2^{n+1} + 1\right)$. For $n = 1$, $A_{1} = 1$, which is not a prime. According to a), if $n \neq 1$, then $n \geq 4$. But then $2^{2n+1} + 2^{n+1} + 1 > 2^{2n+1} - 2^{n+1} + 1 > 65$, and $A_{n}$ has at least two factors. We conclude that $A_{n}$ can never be a prime.

Solution:

Alternative Solution to b): Knowing that $n = 3k + 1$ in order for $A_{n}$ to be an integer, $2^{4n+2} + 1 = 2^{12k+6} + 1 = \left(2^{4k+2}\right)^{3} + 1 = \left(2^{4k+2} + 1\right)\left(2^{8k+4} - 2^{4k+2} + 1\right)$ $\quad(*)$. As in the previous solution, if $k = 0$, then $A_{1} = 1$, if $k = 1$, then $A_{4} = 2^{12} - 2^{6} + 1 = 4033 = 37 \cdot 109$, and for $k \geq 2$ both factors in $(*)$ are larger than $65$, so $A_{3k+1}$ is not a prime.