# For which $n$ is $2^{2x+2} \equiv 2\pmod n \quad\text{and}\quad 2^{2x+2} \equiv 4\pmod {n-1}$

We begin with \begin{align*} 2(2^p+n^2-1-2n) \equiv 0\pmod n \quad&\text{and}\quad 2(2^p+n^2-1-2n) \equiv 0\pmod {n-1} \\ \end{align*} Which we reduce to \begin{align*} 2^p\equiv1\pmod{\frac n{2}} \quad&\text{and}\quad 2^{p-1}\equiv1\pmod{\frac{n-1}{4}}. \end{align*}

We are looking to prove that $p$ cannot be odd, considering that $n \ge 3$

So we let $p=2x+1$ (looking to prove by contradiction) \begin{align*} 2^{2x+2} \equiv 2\pmod n \quad&\text{and}\quad 2^{2x+2} \equiv 4\pmod {n-1} \\ \end{align*}

I know that $a^b \equiv a\pmod b$, so I am assuming that I should go somewhere in that direction. And one more thing, $$\frac{2(2^{p} + n^{2} - 1 - 2n)}{n(n-1)} = s$$ where $s$ is an integer and $s \ge 3$. I have reason to believe that the only time that $p$ can be odd is when $n=2, s=2^p-1$

Also all 3 variables must be positive integers ($s,n,p$)

EDIT: It seems that there are solutions even when $n$ does not equal $2$, but the question still remains, for which $n$ can it hold true

• Any ideas on how to solve this? – redelectrons Nov 7 '15 at 16:45

EDIT: For a counterexample, try $p=11$ and $n=23$ We have $2(2^p+n^2−1−2n)=5060=10 \cdot 23 \cdot 22$.
INCORRECT ANSWER: I think I found a counterexample. Set $p = 3$ and $n = 7$. Then, $2(2^p+n^2−1−2n) = 2(8+49-1-14) = 2(42) = 84$. This is divisible by both $n = 7$ and $n-1 = 6$, but $p = 3$ is odd.
• Sorry but that is not a counter example, since s=2, and I stated where $s$ is an integer and $s \ge 3$ – redelectrons Nov 7 '15 at 18:06
• My apologies, I somehow missed the last condition. How about $p = 11$ and $n = 23$? We have $2(2^p + n^2 - 1 - 2n) = 5060 = 10 \cdot 23 \cdot 22$. – Eric Nov 8 '15 at 2:14
• It seems that you are right. I have also now found a few more, such as $n=7, p=33, s=409044506$ – redelectrons Nov 8 '15 at 2:23