If $7$ Divides $\binom{2^n}{2}+1$ then $n =3k+2$ for some positive integer $k$

Question

It is a straightforward question.

If $$ 7 \text{ }\Bigg | \binom{2^n}{2}+1$$ then $n=3k+2$ for some positive integer $k$.

This is just curiosity no motivation just rummaging through some old question in a notebook. A simple counter example would work.

Note if $\mathfrak a(n) =\binom{2^n}{2}+1$ then $7$ divides $\mathfrak a(n)$ for $n=2,5,8,11,14,17,\ldots$ and from this I am guessing that $n=3k+2$

Answer 1

$$\binom{2^n}2+1=\frac{2^n(2^n-1)}2+1=2^{2n-1}-2^{n-1}+1$$

Now, let's apply mod $7$. Note that $2^3\equiv 1\pmod 7$.

If $n=3k$ we have $4-4+1\neq 0$.

If $n=3k+1$ we have $2-1+1\neq 0$.

This proves your statement, but we can check easily if the "iff" statement is true:

If $n=3k+1$ we kave $1-2+1=0$.

So $7$ divides $\binom{2^n}n+1$ if and only if $n\equiv 2\pmod 3$.

Answer 2

$7|\binom{2^n}{2}+1\iff \binom{2^n}{2}\equiv -1 \bmod 7\iff 2^n(2^{n}-1)2^{-1}\equiv -1 \bmod 7\iff $

$2^n(2^n-1)\equiv -2\equiv 5\bmod 7$.

Now notice that $2^n\bmod 7$ repeats with period $3$, so $2^n(2^n-1)$ also repeats with period three.

In particular it goes: $2,5,0,2,5,0\dots$

Answer 3

The binomial coefficient is $2^n (2^n -1)/2 = 2^{n-1} (2\cdot 2^{n-1} -1)$. For the divisibility to hold you need this to be $-1 \pmod{7}$.

Now the sequence nonnegative powers of $2$ modulo $7$ have a period of at most $6$, by Fermat's little theorem, but actually it is just has period $3$, and it starts $2^0 = 1, 2^1 = 2, 2^2 =4, 2^3 =8\equiv 1, 2, 4, \dots$.

So $2^{3k}\equiv 1$, $2^{3k+1}\equiv 2$, and $2^{3k+2}\equiv 4$ modulo $3$.

It remains to check if you have the desire congruence $$2^{n-1} (2\cdot 2^{n-1} -1) \equiv -1 \pmod{7}$$ somewhere. Since $$2 (2\cdot 2 -1) \equiv -1 \pmod{7}$$

Indeed you have it for $2^{n-1} \equiv 2 \pmod{7}$, and only for those, that is $n-1 \equiv 1 \pmod{3}$, which is just what you claim.

Answer 4

Something slightly more general: we have ${k\choose 2} \equiv -1 \pmod{7}$ if and only if $k\equiv 4\pmod{7}$.

To see this, write ${k\choose 2} = \frac{k(k-1)}{2}$, so the equation is equivalent to $k^2 - k \equiv -2\pmod{7}$. But $k^2 - k + 2 \equiv (k-4)^2 \pmod{7}$, so this is satisfied exactly when $k\equiv 4\pmod{7}$.

Finally, it is easy to see that $2^n$ cycles through the values $1,2,4\pmod{7}$, and the result follows.