Let $n \in \mathbb{N}$ such that $p=17^{2n}+4$ is a prime. Show \begin{align*} p \mid 7^{\tfrac{p-1}{2}} +1 \end{align*}
Problem
Source: Balkan MO ShortList 2011 N2
Tags:
06.04.2020 17:16
Clearly $p \equiv 1 \mod 4$. $\left( \dfrac{7}{p} \right) = -1 \Longleftrightarrow \left( \dfrac{p}{7} \right) = -1 \Longleftrightarrow p \equiv 3,5,6 \mod 7$. $17^{2n}+4 \equiv 2^{n} + 4 \mod 7$, but since $2^{n} \equiv 1,2,4 \mod 7$. Note that $2^{n} \equiv 4 \mod 7$ is the only problem. We show it's not feasible as this is true iff $n \equiv 2 \mod 3$, and for even $n$, Sophie Germain suggests $p$ isn't a prime therefore implying $2n \equiv 10 \mod 12$. This means $17^{2n}+4 \equiv 0 \mod 13$ and we are done.
06.04.2020 17:29
By Euler Criterion, This is equivalent to proving \[ \left( \frac{7}{p} \right) = -1\]But by Quadratic Reciproty, we have \[ \left( \frac{7}{p} \right) \left( \frac{p}{7} \right) = (-1)^{\frac{6 \cdot (17^{2n} + 3)}{4}} = 1 \]Since $17^{2n} + 3 \equiv 289^n + 3 \equiv 0 \ (\text{mod} \ 4)$. Therefore, we have \[ \left( \frac{7}{p} \right) = \left( \frac{p}{7} \right) \]Notice that when $n$ is even, then let $n = 2k$. We have $17^{4k} + 4$, which is not a prime number by Sophie Germain Identity. Hence, $n$ must be odd. This gives us $2^n \equiv 1, 2, 4 \ (\text{mod} \ 7)$. We claim that we can't have $2^n \equiv 4 \ (\text{mod} \ 7)$. Suppose otherwise, this means that $n \equiv 5 \ (\text{mod} \ 6)$. \[ 17^{2n} + 4 \equiv \ 3^n + 4 \ \equiv 0 \ (\text{mod} \ 13) \]which is not a prime number. (Notice that $o_{13}(3) = 6$). Therefore, \[ \left( \frac{p}{7} \right) = \left( \frac{289^n + 4}{7} \right) = \left( \frac{2^n + 4}{7} \right) = -1 \]