## Mr.Math 3 years ago Determine all positive integers $$n\ge 3$$ such that $$2^{2000}$$ is divisible by $$1+\left(\begin{matrix}n \\ 1\end{matrix}\right)+\left(\begin{matrix}n\\ 2\end{matrix}\right)+\left(\begin{matrix}n\\ 3\end{matrix}\right)$$.

1. SqueeSpleen

Combinatory numbers?

2. FoolForMath

Latex tip for Mr.Math : $$\binom{n}{r}$$

3. satellite73

or even $\dbinom{n}{k}$

4. FoolForMath

OR even $$n \choose r$$

5. SqueeSpleen

Impair = odd number, I searched the correct translation xD, I don't know how to write in English the numbers of the kind of 2k where k is an integer.

6. Mr.Math

I don't understand, what's the difference between mine and yours? @Fool and satellite

7. FoolForMath

8. Mr.Math

Oh I got it. Thanks :-)

9. Mr.Math

$n\choose r$

10. Mr.Math

@SqueeSpleen: If you could write it in latex, that would be great!

11. SqueeSpleen

I made some mistakes, I'll start from zero, and I may use latex.

12. Mr.Math

Okay.

13. SqueeSpleen

$1+\left(\begin{matrix}n \\ 1\end{matrix}\right)+\left(\begin{matrix}n \\ 2\end{matrix}\right)+\left(\begin{matrix}n \\ 3\end{matrix}\right)=1+n+n(n+1)/2+n(n+1)(n+2)/6$ $=1+n(1+(n+1)/2+(n+1)(n+2)/6)=1+n(1+((n+1)/2)(1+(n+2)/3)$ Or $1+n!/((n-1)!1!)+n!/((n-2)!2!)+n!/(n-3!3!)=$ $=1+n+n*(n-1)/2+n*(n-1)*(n-2)/6=$ $=(6+6n+3n^2-3n+n^3+2n-3n^2)/6=$ $=(n^3+5n+6)/6$ $=n(n^2+5)/6+1$ I used the division by 6 as if 6 were a prime number, so it was a mistake. n by 2 or 3, or n^2+5 has to be divided by 3 or 2. Let's try: n=6k It's key. n=6k+1 then: $n(n^2+5)/6+1=36 k^3+18 k^2+8 k+1$ But then you get and odd number, you can't divide it by 6. So n isn't of the kind of 6k+1 It's n=6k+2 then $n(n^2+5)/6+1=36 k^3+36 k^2+17 k+3$ It can be divided by 3 only if k is multiple of 3 and cannot be divided by 2 n=6k+3 $n(n^2+5)/6+1=36 k^3+54 k^2+32 k+7$ Then I can't be divided by 2, then it can't be divided by 2. $n=6k'+4=6k-2$ $n(n^2+5)/6+1=36 k^3-36 k^2+17 k-3$ It can be divided by 3 only if k is multiple of 3 and cannot be divided by 2 n=6k'+5=6k-1 $n(n^2+5)/6+1=36 k^3-18 k^2+8 k-1$ But then you get and odd number, you can't divide it by 6. This means the number is of the kind of: 6k, 6k+1, 6k+3 or 6k+5 Where k is an integer. I barely eliminated some choices, so I'll try to take other way to solve this.

14. Ishaan94

Shouldn't it be $$\dbinom{n}{2} = \large\frac{n(n-1)}{2}$$

15. SqueeSpleen

Yes I made the mistake in the first lines, but I didn't in the following lines, thanks for the advice, I don't know how to edit messages.

16. SqueeSpleen

I found n=3, n=7 and n=23 but I can't prove that they're the only solutions. I think they're but I have not idea how to prove this.

17. Ishaan94

I like your dedication! 17 hours and you still wanna solve it! excellent!

18. SqueeSpleen

I was trying to prove that if you pick k big enough then n(n^2+5)/6+1 will not be a power of 2, but I got nothing except some less paper and ink :P

19. mukushla

$1+\dbinom{n}{1}+\dbinom{n}{2}+\dbinom{n}{3}=\frac{n^3+5n+6}{6}$so we must have$\frac{n^3+5n+6}{6}=2^k \ \ \ \ \ \ \ \ k\le2000$or$n^3+5n+6=3\times2^{k+1}$$(n+1)(n^2-n+6)=3\times2^{k+1}$note that$\gcd(n+1\ , \ n^2-n+6)=\gcd(n+1\ , \ n^2-n-n^2-n+6)$$\gcd(n+1\ , \ -2n+6)=\gcd(n+1\ , \ -2n+2n+2+6)=\gcd(n+1 \ , \ 8)$$\Rightarrow \gcd(n+1\ , \ n^2-n+6) | 8$ since $$n^2-n+6>n+1$$ so its immidiate that$$n+1=16$$ or $$n+1|3\times 2^3$$ so we have few cases to check : $$n=1,2,3,5,7,11,15,23$$