<s>[INST] Tricky congruence question Let $p>5$ be a prime,
$$n\triangleq\frac{4^p+1}{5}\;\quad\text{and}\;\quad b\triangleq\frac{n-1}{4}\quad.$$
It can be shown that both are integers, and also that $n$ is composite, $b$ is odd and $p$ divides $b$.
I'd like to prove that
$$4^b\equiv-1\pmod n\;\quad.$$
I tried rephrasing the congruence in terms of the other variables to see if I could find a way out by applying Fermat's — or even Euler's — Theorem, but I'm not getting anywhere.
 [/INST] We will show the slightly stronger $$ 4^b \equiv -1 \pmod{4^p + 1}. $$ Fermat's theorem implies that $4^{p-1} \equiv 1 \pmod{p}$. Since $b = (4^{p-1}-1)/5$, it follows that $p|b$ (since $p > 5$). Suppose that $b = Xp$. Clearly $b$ is odd, therefore so is $X$. We have
$$\begin{align*} 4^{Xp} + 1 &= (4^{Xp} + 4^{(X-1)p}) - (4^{(X-1)p} - 4^{(X-2)p}) + \cdots + (4^p + 1) \\ &= (4^{(X-1)p} - 4^{(X-2)p} + \cdots + 1)(4^p + 1). \end{align*} $$ Here we used the fact that $X$ is odd. It follows that $4^p + 1$ divides $4^b + 1$.
</s>