设 $p$ 是奇质数，且 $-1$ 不是 $p$ 的二次剩余（即 $p\equiv 3\pmod 4$）。求证：存在自然数 $n$ 使得 $2^n+1$ 不是 $p$ 的二次剩余。

目前的一个做法（来自 UOJ 用户群）：考虑反证，设有奇质数 $p$ 使得对任意的 $n$ 都有 $2^n+1$ 是 $p$ 的二次剩余。令 $n=0$ 知 $2$ 是 $p$ 的二次剩余。设 $2$ 模 $p$ 的阶为 $r$，可知 $r|\dfrac{p-1}{2}$，故 $r$ 是奇数。由欧拉判别法知

方便起见记 $k=\dfrac{p-1}{2}$。将这个式子展开，可以得到上面的命题等价于

但到这里便陷入了瓶颈。哪位大佬能帮忙看看有什么证法，不胜感激 QaQ