# 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.

-

First, note that $b = \frac{4^{p-1}-1}5$.

But $4^{p-1}-1$ is divisible by $p$, so $p|b$.

Also, note that $4^p \equiv -1 \pmod n$, since $4^p+1 = 5n$.

So $4^b = (4^p)^{b/p} \equiv (-1)^{b/p} = -1 \pmod n$

-

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$.

-
Argh, I already knew $p|b$, I forgot to put in the "it can be shown" part. – Luke Oct 31 '11 at 2:27