Suppose that $q=\frac{2^n+1}{3}$ is prime then $q$ is the largest factor of $\binom{2^n}{2}-1$

Question

I am curious for a starting point to prove the following claim

Suppose that $q={2^n+1 \above 1.5pt 3}$ is prime then $q$ is the largest factor of $\binom{2^n}{2}-1$

For example take $n=61$. Then $q ={2^{61}+1 \above 1.5pt 3} = 768614336404564651$ which is prime. Then $\binom{2^{61}}{2}-1 = 2658455991569831744654692615953842175$ and it's largest prime factor is $q$. Note ${2^{29}+1 \above 1.5pt 3} =178956971$ is not prime and the largest prime factor of $\binom{2^{29}}{2}-1$ is $3033169$. But even then we could note that $178956971 = 59*3033169$. A counterexample to the claim would suffice to to show it's wrong.

Answer 1

Since you already have other answers, I will instead offer a small generalization.

Suppose $p=\frac{k^n +1}{k+1}$ is a prime number. Then, $p$ is the largest prime factor of $\binom{k^n}{2}-1$ if $k=2j^2$ for some integer $j$.

Proof:

We have:

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

This can of course be rewritten as $\frac{k+1}{2}p (k^n-2)$

Now suppose $k=2j^2$ for some $j \in \mathbb{N}$. Then, note that since $k \equiv -1 \mod (k+1)$, $n$ must be an odd integer in order for $\frac{k^n +1}{k+1}$ to have integer values. Thus, $\frac{n-1}{2}$ is also an integer. Then:

$$\frac{k+1}{2}p (k^n-2) = (k+1)p (2^{n-1}j^{2n}-1) = (k+1)p(2^{\frac{n-1}{2}}j^{n}-1)(2^{\frac{n-1}{2}}j^{n}+1)$$

And certainly we have that all the other factors are less than $p$, so this is the largest prime factor. (Note: this can be seen because the other 3 factors $\neq p$ in $(k+1)p(2^{\frac{n-1}{2}}j^{n}-1)(2^{\frac{n-1}{2}}j^{n}+1)$ must all be less than $p$, regardless of whether or not they are prime, implying $p$ has to be the largest prime factor).

EDIT: At the request of the person who asked the original question, I will provide a proof of the following (a quick counterexample to the contrary statement is $n=81$).

Suppose $k$ arbitrary. Then it is always possible to find $n$ such that $3^k$ divides $\binom{2^n}{2}-1$. In particular, $n = 3^{k-2}$ always works.

Proof:

This proof will use the Lifting the Exponent (LTE) Lemma. I suggest looking up the statement if you want to fully understand the proof.

Let $k$ be given. Then we can rewrite $\binom{2^n}{2}-1 = (2^n+1)(2^{n-1}-1)$. In order for either one of these factors to be divisible by $3$, we must have that $n$ is an odd number (since $(-1)^n \equiv -1 \mod 3$). Then $n-1 = 2j$, an even integer. We can then rewrite the above:

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

We can now apply the LTE Lemma. Define a valuation $v$ as follows: $v_p (x) = y$ implies that $y$ is the largest power of $p$ that divides $x$, where $p$ is prime. Then LTE Lemma says:

$$v_3((2^n+1)(4^{j}-1)) = v_3(2^n+1) + v_3(4^{j}-1) = v_3(3) + v_3(n)+v_3(3)+v_3(j)$$

Note that $v_3(3) = 1$ of course. Then, note $j = (n-1)/2$, we have:

$$v_3((2^n+1)(4^{j}-1)) = 2 + v_3 \Big( \frac{n(n-1)}{2} \Big)$$

Now, in the above, note that either $n$ or $n-1$ can be divisible by $3$, but not both, so we can assume without loss of generality that $n-1$ is not divisible be $3$, ie $v_3(n-1) = 0$. Also, since a valuation is logarithmic, the $2$ in the denominator goes away since $v_3(2) = 0$. Thus we have the following:

$$v_3((2^n+1)(4^{j}-1)) = 2+v_3(n)$$

Then we are done. Suppose $k$ is given. Then firstly, we have that $3^2 = 9$ will always divide $\binom{2^n}{2}-1$. Now suppose we want $3^k$ to divide it. By the above, we only need to choose $n = 3^{k-2}$ (or any multiple of this).

Actually ... you can generalize this to the $\binom{k^n}{2}-1$ case, but don't worry I will spare you the details.

Answer 2

Most probably yes, because:

$$\binom{2^n}{2}-1=\frac{2^n(2^n-1)}{2}-1=2^{n-1}(2^n-1)-1=$$ $$=2^{n-1}(2^n+1 - 2)-1 = 2^{n-1}(2^n+1) - 2^n-1=(2^n+1)(2^{n-1}-1)=$$ $$=3q(2^{n-1}-1)$$ Additionally: $$2 \equiv -1 \pmod{3}$$ $$2^n \equiv (-1)^n \pmod{3}$$ $$2^n + 1 \equiv (-1)^n +1 \pmod{3}$$ So $n$ is odd, further leading to $$2^{n-1}-1=\left(2^{\frac{n-1}{2}}-1\right)\left(2^{\frac{n-1}{2}}+1\right)$$

Answer 3

First of all, we have to show that $\frac{2^n+1}{3}$ is a factor of $$\binom{2^n}{2}-1=\frac{2^n(2^n-1)}{2}-1=\frac{2^{2n}-2^n-2}{2}$$

To show this, we consider

$$(2^n+1)^2-3(2^n+1)=2^{2n}+2\cdot 2^n+1-3\cdot2^n-3=2^{2n}-2^n-2$$

So, $\binom{2^n}{2}-1$ is divisble by $2^n+1$ and therefore by $\frac{2^n+1}{3}$.

But $(\frac{2^n+1}{3})^2>\frac{2^{2n}+2^n+1}{9}$

Since $9$ is a factor of $\binom{2^n}{2}-1$ for odd $n$ (and $n$ must be odd, otherwise $\frac{2^n+1}{3}$ is not an integer) , there cannot be a larger prime factor $p$ because we would have $$3^2\cdot \frac{2^n+1}{3}\cdot p>2^{2n}+2^n+1>\frac{2^{2n}-2^n-2}{2}$$

To show that $9$ is a factor of $2^{2n}-2^n-2$ (for odd n), which implies that $9$ is a factor of $\binom{2^n}{2}-1$ , we consider that $2^n\equiv 2,5 \ or\ 8\mod 9$. In any case we get $2^{2n}-2^n\equiv 2\mod 9$.