A community for students.
Here's the question you clicked on:
 0 viewing
mukushla
 2 years ago
Determine all positive integers \(n\ge 3\) for which\[1+\dbinom{n}{1}+\dbinom{n}{2}+\dbinom{n}{3}\]is a divisor of \(2^{2000}\)
mukushla
 2 years ago
Determine all positive integers \(n\ge 3\) for which\[1+\dbinom{n}{1}+\dbinom{n}{2}+\dbinom{n}{3}\]is a divisor of \(2^{2000}\)

This Question is Closed

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1\[ \binom{n}{0} + \binom{n}{1} = \binom{n+1}{1}\] \[ \binom{n}{2} + \binom{n}{3} = \binom{n+1}{3}\] \[ n+1 + {(n + 1 )n (n1)\over 3} = {(n+1)(3 + n(n1))\over 3}\]

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1isn't it 6 instead of 3

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1sorry ... forgot it

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1so\[{(n+1)(6 + n(n1))\over 6}=\frac{(n+1)(n^2n+6)}{6}\]is a divisor of \(2^{2000}\)

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1where do you get this problems?

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1so it must be in the form\[\frac{(n+1)(n^2n+6)}{6}=2^m \ \ \ \ m\le2000\]

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1compititions,books,...

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1ah man ... i thought engineers don't like number theory.

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1\[ (n+1)(n^2n+6) \times k=3 \times 2^{2000+1} \]

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1or we can state problem like this\[(n+1)(n^2n+6)=3\times2^{m+1} \ \ \ \ m\le2000\]

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1n = 2 is one solution

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1n = 3, 4, 5, 6 < these does not work

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1let me try some programming solution up to 100

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1yeah that will give all solutions

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1guys can u find \[\gcd(n+1,n^2n+6)\]?

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1regarding this problem ... i don't have approach ... matlab collapses after 2^100

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1probably i should recursively divide the quotient by 2 after dividing by 3

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1between 1 to 999 1 12 2 24 3 48 7 384 23 12288

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1exper those are only solutions gane 1? how

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1i started loop from 1 clc; for i=1:999 num = (i+1)*(i^2  i + 6); if rem(num, 3) == 0 quo = num/3; while true if quo == 2; disp([i, num]); break; end; if rem(quo, 2) ~= 0; break; end; quo = quo/2; end end end

ganeshie8
 2 years ago
Best ResponseYou've already chosen the best response.0i tried euclid its repeating forever

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1probably are the only solutions (3, 48), (7, 384), (23, 12288)

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1emm... there is useful formula\[\gcd(a,b)=\gcd(a,ak+b) \ \ \ k \in \mathbb{Z}\]

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1\[ \gcd(n+1, n(n+1)  2n + 6) => \gcd(n+1, 2(n 3))\]

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1\[\gcd(n+1,8)= \gcd(n+1, 2(n+1)+2(n 3))\]

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1let's try elimination here ... this is divisible by 2 all times \[ (n+1)(n^2n+6)\] suppose what must be the value of n^2  n + 6 if n+1 is not divisible by 3

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1the point is \[\gcd(n+1,n^2n+6)8\]

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1n+1 = 3k +1, 3k +2 => n = 3k, 3k+1 9k^2  3k+6 < divisible by 3 9k^2 + 6k +1  3k  1 + 6 < divisible by 3 < bad luck

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1this seems to be valid for 3k, 3k+1, 3k+2 let's try for this 3k+2 (3k+3)(9k^2 + 12k + 4  3k  2 + 6) = 3(k+1)(9k^2 + 9 k + 4) (k+1)(9k^2 + 9 k + 4) = 2^x

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1implies k should be odd ... (2y+1) .. such that k+1 = 2^p for some p ie, k+1 = 2, 4, 8, 16, ....

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1for k = 7, the expression (9k^2 + 9 k + 4) is 512 ... which shows that n = 2*7 + 2 = 23

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1it remains to prove that there is no other n for the this type of 3k+2 form ... let k= 2^p  1 (9(2^p 1) ^2 + 9 (2^9 1) + 4) = 9*2^(2p)  18 2^p + 9 + 9 * 2^p  9 + 4 9*2^(2p)  9 *2^p + 4 = 2^q for some integer.

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1man this is tough .. gotta work on classical + statistical mechanics ... have exam five days later.

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1np man...how many exams do u have?

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.11 down three more to go ... + 2 practicals

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1oh man go back to ur work :)

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.1yeah ... i'll watch the developments. physicist are not so good with numbers.

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1we have lots of times to work on brainwashing problems like this

eliassaab
 2 years ago
Best ResponseYou've already chosen the best response.0I wrote a Mathematica Program for \( n \le10^6 \) I found that \[ \frac{1}{6} (n+1) \left(n^2n+6\right) \] is a power of 2 for for \[ n=3, \quad \frac{1}{6} (n+1) \left(n^2n+6\right)=8\\ n=7, \quad \frac{1}{6} (n+1) \left(n^2n+6\right)=64\\ n=23, \quad \frac{1}{6} (n+1) \left(n^2n+6\right)=2048\\ \]

eliassaab
 2 years ago
Best ResponseYou've already chosen the best response.0I just did it \(n = 2 (10^6)\)

eliassaab
 2 years ago
Best ResponseYou've already chosen the best response.0Here is the Mathematica Program Clear[h, n] h[n_] = 1/6 (1 + n) (6  n + n^2); PowerTwoQ[n_] := Module[{x }, x = n; While[ Divisible[x, 2] && x > 1, x = x/2;]; Return[ x == 1]] Q = {}; For [ n = 2, n < 2000000, n++; If [PowerTwoQ[h[n]], Q = Append[Q, {n, h[n]}]]]; Q The output is {{3, 8}, {7, 64}, {23, 2048}}

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1\[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+1)(n^2n+6)=3\times2^{k+1}\]but notice that\[\gcd(n+1\ , \ n^2n+6)=\gcd(n+1\ , \ n^2nn^2n+6)\]\[\gcd(n+1\ , \ 2n+6)=\gcd(n+1\ , \ 2n+2n+2+6)=\gcd(n+1 \ , \ 8)\]\[\Rightarrow \gcd(n+1\ , \ n^2n+6)  8\]since \(n^2n+6>n+1\) power of \(2\) in \(n+1\) can not be greater than \(4\) in other words \(n+1=16\) or \(n+1 3\times 2^3\) so we have few cases to check\[n=3,5,7,11,15,23\]

mukushla
 2 years ago
Best ResponseYou've already chosen the best response.1checking that numbers gives \(3\) solution : \(\color\red{n=3,7,23}\)
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.