Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

mukushla Group Title

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}\)

  • one year ago
  • one year ago

  • This Question is Closed
  1. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 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 (n-1)\over 3} = {(n+1)(3 + n(n-1))\over 3}\]

    • one year ago
  2. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    isn't it 6 instead of 3

    • one year ago
  3. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    sorry ... forgot it

    • one year ago
  4. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so\[{(n+1)(6 + n(n-1))\over 6}=\frac{(n+1)(n^2-n+6)}{6}\]is a divisor of \(2^{2000}\)

    • one year ago
  5. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    where do you get this problems?

    • one year ago
  6. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so it must be in the form\[\frac{(n+1)(n^2-n+6)}{6}=2^m \ \ \ \ m\le2000\]

    • one year ago
  7. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    compititions,books,...

    • one year ago
  8. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ah man ... i thought engineers don't like number theory.

    • one year ago
  9. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    lol

    • one year ago
  10. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[ (n+1)(n^2-n+6) \times k=3 \times 2^{2000+1} \]

    • one year ago
  11. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    or we can state problem like this\[(n+1)(n^2-n+6)=3\times2^{m+1} \ \ \ \ m\le2000\]

    • one year ago
  12. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    n = 2 is one solution

    • one year ago
  13. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    n = 3, 4, 5, 6 <-- these does not work

    • one year ago
  14. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    let me try some programming solution up to 100

    • one year ago
  15. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah that will give all solutions

    • one year ago
  16. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    guys can u find \[\gcd(n+1,n^2-n+6)\]?

    • one year ago
  17. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    regarding this problem ... i don't have approach ... matlab collapses after 2^100

    • one year ago
  18. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    probably i should recursively divide the quotient by 2 after dividing by 3

    • one year ago
  19. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    between 1 to 999 1 12 2 24 3 48 7 384 23 12288

    • one year ago
  20. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    gcd is 1

    • one year ago
  21. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    exper those are only solutions gane 1? how

    • one year ago
  22. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    i 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

    • one year ago
  23. ganeshie8 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    i tried euclid its repeating forever

    • one year ago
  24. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    probably are the only solutions (3, 48), (7, 384), (23, 12288)

    • one year ago
  25. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    emm... there is useful formula\[\gcd(a,b)=\gcd(a,ak+b) \ \ \ k \in \mathbb{Z}\]

    • one year ago
  26. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[ \gcd(n+1, n(n+1) - 2n + 6) => \gcd(n+1, 2(n -3))\]

    • one year ago
  27. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[\gcd(n+1,8)= \gcd(n+1, -2(n+1)+2(n -3))\]

    • one year ago
  28. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    let's try elimination here ... this is divisible by 2 all times \[ (n+1)(n^2-n+6)\] suppose what must be the value of n^2 - n + 6 if n+1 is not divisible by 3

    • one year ago
  29. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    the point is \[\gcd(n+1,n^2-n+6)|8\]

    • one year ago
  30. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    n+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

    • one year ago
  31. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    this 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

    • one year ago
  32. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    implies k should be odd ... (2y+1) .. such that k+1 = 2^p for some p ie, k+1 = 2, 4, 8, 16, ....

    • one year ago
  33. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    for k = 7, the expression (9k^2 + 9 k + 4) is 512 ... which shows that n = 2*7 + 2 = 23

    • one year ago
  34. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  35. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    man this is tough .. gotta work on classical + statistical mechanics ... have exam five days later.

    • one year ago
  36. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    np man...how many exams do u have?

    • one year ago
  37. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    1 down three more to go ... + 2 practicals

    • one year ago
  38. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    oh man go back to ur work :)

    • one year ago
  39. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah ... i'll watch the developments. physicist are not so good with numbers.

    • one year ago
  40. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    we have lots of times to work on brainwashing problems like this

    • one year ago
  41. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    sure

    • one year ago
  42. eliassaab Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I wrote a Mathematica Program for \( n \le10^6 \) I found that \[ \frac{1}{6} (n+1) \left(n^2-n+6\right) \] is a power of 2 for for \[ n=3, \quad \frac{1}{6} (n+1) \left(n^2-n+6\right)=8\\ n=7, \quad \frac{1}{6} (n+1) \left(n^2-n+6\right)=64\\ n=23, \quad \frac{1}{6} (n+1) \left(n^2-n+6\right)=2048\\ \]

    • one year ago
  43. eliassaab Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I just did it \(n = 2 (10^6)\)

    • one year ago
  44. eliassaab Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Here 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}}

    • one year ago
  45. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 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^2-n+6)=3\times2^{k+1}\]but notice 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\) 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\]

    • one year ago
  46. mukushla Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    checking that numbers gives \(3\) solution : \(\color\red{n=3,7,23}\)

    • one year ago
    • Attachments:

See more questions >>>

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.