6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Strikes me that either $q$ will be a factor or not requardless as to whether it is prime and $q > N/q$ or not regardless. So $q$ is largest factor only if $N/q$ is prime. So I'd think that'd be the thing to prove: if $q$ is prime then $[{2^n \choose 2} - 1]/q$ is also prime. Not sure how to do that, but that is what I think need to be done $\endgroup$
    – fleablood
    Sep 2, 2016 at 21:09
  • $\begingroup$ Cannot quite follow you. Note that $q =\frac{2^{29}+1}{3}$ is not a factor of $\binom{2^{29}}{2}-1$ $\endgroup$
    – Anthony
    Sep 2, 2016 at 21:21
  • $\begingroup$ It's not? 178956971 isn't a factor of 144115187807420415? It is when I do it. 178956971 x 805306365 = 144115187807420415. Thing is whether q is prime or not isn't going to effect whether it is a factor or not. If it's a factor then N/q is also going to be a factor. q being prime isn't going to affect whether q > N/q or not. But if N/q isn't prime then N/q = km and $m*q > q$ is a factor. So q is the largest factor of N only if N/q is prime. That could be affect by q being prime. $\endgroup$
    – fleablood
    Sep 2, 2016 at 23:22

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This is really nice although the last line in the proof for me was hard to follow. And there were other excellent proofs in this post. So this settles the case for the largest factor but I am curious if we can extend any of the answers given in this post to tackle the following: There does not exist an integer $m$ greater than $5$ such that $3^m$ divides $\binom{2^n}{2}-1$. I am asking this here just to keep the discussion going rather than making another post. $\endgroup$
    – Anthony
    Sep 3, 2016 at 12:41
  • 1
    $\begingroup$ This is a false statement: I will provide the proof in my answer that in fact we can find $n$ such that $3^k$ divides it for any given $k$. $\endgroup$
    – Rellek
    Sep 3, 2016 at 18:00
  • $\begingroup$ I made that claim on a small computer check using GAP. A counter example or proof would be nice. $\endgroup$
    – Anthony
    Sep 3, 2016 at 18:02
  • 1
    $\begingroup$ Edited answer. The counterexample is included -- do not worry if you don't understand the proof. $\endgroup$
    – Rellek
    Sep 3, 2016 at 18:25
  • $\begingroup$ Here for those that don't want to do the search and apparently the LTE method is related to a theorem of Zsigmondy's. $\endgroup$
    – Anthony
    Sep 4, 2016 at 12:32
3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ This answers the question if you add just one step more: if $n$ is an odd prime we have $n=2k+1$ and therefore $$2^{n-1}-1=2^{2k}-1=(2^k+1)(2^k-1)$$ and these factors are less than $q$. $\endgroup$
    – String
    Sep 2, 2016 at 22:05
  • 1
    $\begingroup$ Thank you, @String! I updated the answer. $\endgroup$
    – rtybase
    Sep 2, 2016 at 22:19
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Maybe I am missing something but ${2^{29}+1 \above 1.5pt 3} =178956971$ is not prime and the largest prime factor of $\binom{2^{29}}{2}-1$ is $3033169$. Surely $178956971 >3033169$ $\endgroup$
    – Anthony
    Sep 2, 2016 at 23:14
  • $\begingroup$ In your question, you assumed that $\frac{2^n+1}{3}$ is prime, or did I understand something wrong ? $\endgroup$
    – Peter
    Sep 2, 2016 at 23:16
  • $\begingroup$ Oh ok gotcha. It seemed that you were trying to show that it was true for every $n$. Where did you explicity use the primality of $q$ ? $\endgroup$
    – Anthony
    Sep 2, 2016 at 23:22
  • 1
    $\begingroup$ If $q$ is composite, $q$ is not the largest factor and of course not the largest prime factor. But $q$ must be larger than any prime factor in this case , if $n$ is odd. $\endgroup$
    – Peter
    Sep 2, 2016 at 23:39
  • 1
    $\begingroup$ I did not explicitely use that $q$ is prime, I showed that no prime factor larger than $q$ can exist, if $n$ is odd. In particular, if $q$ is a prime factor, it is the largest and it has multiplicity $1$. (To show the last claim, we only have to consider $3^2\cdot (\frac{2^n+1}{3})^2>2^{2n}+2^n+1>\frac{2^{2n}-2^n-2}{2}$). $\endgroup$
    – Peter
    Sep 2, 2016 at 23:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .