# Finding integer solutions out of a a | b

Determine all positive integer values of (n) such that

$${ n \choose 0 } + { n \choose 1 } + { n \choose 2 } + { n \choose 3 } \ \bigg| \ 2 ^ { 2008 }$$

What is the sum of all these values?

CURRENT PROGRESS:

I was able to find out that this is equivalent to $$(n+1)(n^2 - n + 6) \,| \,3\times (2)^{2009}$$ and opened in 2 cases, $$n+1 = 2^a$$ and $$n+1 = 3\times 2^a$$, trying to solve like: $$n = 2^a - 1$$, then $$n^2 - n + 6 = 2^{2a} - 3\times2^a + 8$$, doing the same to the 2nd case but couldn't find solutions. Something that should be useful is that $$n^2 - n + 6 = 2^{2a} - 3\times2^a + 8 | \space\space 3\times2^{2019-a}$$, it has a factor 3 in it.

• Note: I reformatted your post fairly heavily. Please check to make sure I didn't change your meaning...your use of "." was hard to interpret in places so I might have misread. – lulu Mar 6 at 14:36
• I saw your changes and then reformatted again to what I meant, thanks – Pedro Barros Mar 6 at 14:41
• Welcome to Math.SE. This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc. – Carl Mummert Mar 6 at 15:47
• @Carl Mummert, the context of it is that I am studying number theory aiming to perform good classes about this subject for school students. I showed my strategy: Expanding and then opening in two cases that seemed easy to solve but I could not find solutions in it. I am stuck with two equations and probably need restrictions about integers to narrow my search of solutions. – Pedro Barros Mar 6 at 16:16

Set $$n+1=m$$

$$n^2-n+6=(m-1)^2-(m-1)+6=m^2-3m+8$$

$$g=(m, m^2-3m+8)=(m,8)$$

Check all the four possible cases

For example,

If $$g=4$$

$$\dfrac{n+1}4\cdot\dfrac{ n^2-n+6}4$$ will divide $$3\cdot2^{2008-4}$$

where the two factors are relatively prime

i.e. one of the factors must be odd $$1$$ or $$3$$

• actually you forgot that $-(m-1) = -m + 1$, resulting in:$m^2 -3m + 8$ – Pedro Barros Mar 6 at 15:36

So $$(n+1)(n^2 -n + 6) = 3\cdot 2^{2009}$$ so

So $$n+1 = 3^t2^s; n^2 -n+6 = 3^r2^w; t+r \le 1; s + w \le 2009$$.

Case 1:$$t= 0$$.

$$n = 2^s -1$$ and $$n^2 - n + 6 = 2^{2s} - 2^{s+1} -2^s + 6$$.

If $$s = 0$$ we have $$n=0$$ and that's a solution (if we assume $${0\choose k}=0$$ for $$k \ne 0$$). If $$s \ge 1$$ then

$$n^2 -n +6 = 2(2^{2s-1} -2^s - 2^{s-1} + 3)$$.

If $$s = 1$$ we have $$n=1$$ and that's a solution (if we assume $${n\choose k} = 0$$ if $$n > k$$). If $$s \ge 1$$ then

$$2^{2s-1} - 2^s - 2^{s-1} + 3$$ is odd so either is either equal to $$3$$ or $$1$$.

So either $$2^{2s-1}= 2^s + 2^{s-1}$$

$$2^{s} = 2 + 1$$ which is impossible, or

$$2^{2s-1}+2 = 2^s + 2^{s-1}$$ so

$$2^{2s-2} + 1 = 2^s + 2^{s-2}$$ so $$s-2 =0$$ and $$s = 2s -2$$ or $$s=2$$ so $$n= 3$$ and we have $$n+1 = 4$$ and $$n^2-n+6 = 9$$. That's a solution.

So far: $$n = 0,n=1, n=3$$ are solutions

Case 2: $$t = 1$$

$$n = 3*2^s - 1$$ and $$n^2 - n + 6 = 9*2^{2s} - 3*2^{s+1} + 1 - 3*2^{s} - 1 + 6 = 3(3*2^{2s} - 2^{s+1} + 2^s + 2) = 2^w$$.

That's impossible.

So unless I made a mistake the only solutions are $$0, 1,3$$ and if we don't consider $${n< k \choose k}$$ a legitimate value then the only solution is $$n=3$$.