5
$\begingroup$

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.

2 Answers 2

5

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$

2

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

  • 0
    Argh, I already knew $p|b$, I forgot to put in the "it can be shown" part.2011-10-31