Prove $\prod_{i=1}^{2^{N-1}} (1+i-i^2) \equiv 1+2^N \bmod 2^{N+1}$ I want to prove $\prod_{i=1}^{2^{N-1}} (1+i-i^2) \equiv 1+2^N \bmod 2^{N+1}$ for $N\geq 4$.
First, let's prove $\prod_{i=1}^{2^{N-1}} (1+i-i^2) \equiv 1 \bmod 2^{N}$.
$$1+i-i^2\equiv1+j-j^2$$
$$\Leftrightarrow (i-j)(i+j-1)\equiv0$$
Since the parity of $i-j$ and $i+j-1$ are different, $j\equiv i \lor j=2^N-i+1$.
Thus, $1+i-i^2$ takes all odd number below $2^{N-1}$ once. From Gauss-Wilson's theorem, $\prod_{i=1}^{2^{N-1}} (1+i-i^2) \equiv 1 \bmod 2^N$ holds 
I found  $\prod_{i=1}^{2^{N-1}} (1+i-i^2) \equiv 1+2^N \bmod 2^{N+1}$ up to $N=27$ by numerical calculation. How can we prove this?
 A: Let $a_i=1+i-i^2$ and
$$p_n=\prod_{i=1}^{2^n}a_i$$
so that we have to show
$$p_{n-1}\equiv 1+2^n\pmod{2^{n+1}}\tag 1$$
Note that $(1)$ implies $p_{n-1}^2\equiv 1+2^{n+1}\pmod{2^{n+2}}$.
By induction on $n\geq 4$, we have:
\begin{align}
p_n
&=p_{n-1}\prod_{i=2^{n-1}+1}^{2^n}a_i\\
&=p_{n-1}\prod_{i=1}^{2^{n-1}}a_{2^{n-1}+i}\\
&=p_{n-1}\prod_{i=1}^{2^{n-1}}(1+2^{n-1}+i-(2^{n-1}+i)^2)\\
&=p_{n-1}\prod_{i=1}^{2^{n-1}}(1+2^{n-1}+i-2^{2n-2}-2^ni-i^2)\\
&=p_{n-1}\prod_{i=1}^{2^{n-1}}(a_i+2^{n-1}(1-2^{n-1}-2i))\\
&\equiv p_{n-1}\left(\prod_{i=1}^{2^{n-1}}a_i+\sum_{j=1}^{2^{n-1}}2^{n-1}(1-2^{n-1}-2j)\prod_{i\neq j}a_i\right)\\
&\equiv p_{n-1}^2\left(1+2^{n-1}\sum_{j=1}^{2^{n-1}}\frac{1-2^{n-1}-2j}{a_j}\right)\\
&\equiv (1+2^{n+1})\left(1+2^{n-1}\sum_{j=1}^{2^{n-1}}\frac{1-2^{n-1}-2j}{a_j}\right)\\
&\equiv 1+2^{n+1}+2^{n-1}\sum_{j=1}^{2^{n-1}}\frac{1-2^{n-1}-2j}{a_j}\pmod{2^{n+2}}
\end{align}
hence the assertion reduces to proving
$$\sum_{j=1}^{2^{n-1}}\frac{1-2^{n-1}-2j}{a_j}\equiv 0\pmod{8}$$
and
\begin{align}
\sum_{j=1}^{2^{n-1}}\frac{1-2^{n-1}-2j}{a_j}
&\equiv\frac{2^{n-1}}8\sum_{j=1}^{8}\frac{1-2^{n-1}-2j}{a_j}\\
&\equiv{2^{n-4}}\sum_{j=1}^{8}\frac{1-2j}{a_j}\pmod{8}
\end{align}
which is clearly $\equiv 0\pmod 8$ if $n\geq 7$
