anonymous
  • anonymous
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}\)
Meta-math
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
experimentX
  • experimentX
\[ \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}\]
anonymous
  • anonymous
isn't it 6 instead of 3
experimentX
  • experimentX
sorry ... forgot it

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
so\[{(n+1)(6 + n(n-1))\over 6}=\frac{(n+1)(n^2-n+6)}{6}\]is a divisor of \(2^{2000}\)
experimentX
  • experimentX
where do you get this problems?
anonymous
  • anonymous
so it must be in the form\[\frac{(n+1)(n^2-n+6)}{6}=2^m \ \ \ \ m\le2000\]
anonymous
  • anonymous
compititions,books,...
experimentX
  • experimentX
ah man ... i thought engineers don't like number theory.
anonymous
  • anonymous
lol
experimentX
  • experimentX
\[ (n+1)(n^2-n+6) \times k=3 \times 2^{2000+1} \]
anonymous
  • anonymous
or we can state problem like this\[(n+1)(n^2-n+6)=3\times2^{m+1} \ \ \ \ m\le2000\]
experimentX
  • experimentX
n = 2 is one solution
experimentX
  • experimentX
n = 3, 4, 5, 6 <-- these does not work
experimentX
  • experimentX
let me try some programming solution up to 100
anonymous
  • anonymous
yeah that will give all solutions
anonymous
  • anonymous
guys can u find \[\gcd(n+1,n^2-n+6)\]?
experimentX
  • experimentX
regarding this problem ... i don't have approach ... matlab collapses after 2^100
experimentX
  • experimentX
probably i should recursively divide the quotient by 2 after dividing by 3
experimentX
  • experimentX
between 1 to 999 1 12 2 24 3 48 7 384 23 12288
ganeshie8
  • ganeshie8
gcd is 1
anonymous
  • anonymous
exper those are only solutions gane 1? how
experimentX
  • experimentX
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
ganeshie8
  • ganeshie8
i tried euclid its repeating forever
experimentX
  • experimentX
probably are the only solutions (3, 48), (7, 384), (23, 12288)
anonymous
  • anonymous
emm... there is useful formula\[\gcd(a,b)=\gcd(a,ak+b) \ \ \ k \in \mathbb{Z}\]
experimentX
  • experimentX
\[ \gcd(n+1, n(n+1) - 2n + 6) => \gcd(n+1, 2(n -3))\]
anonymous
  • anonymous
\[\gcd(n+1,8)= \gcd(n+1, -2(n+1)+2(n -3))\]
experimentX
  • experimentX
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
anonymous
  • anonymous
the point is \[\gcd(n+1,n^2-n+6)|8\]
experimentX
  • experimentX
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
experimentX
  • experimentX
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
experimentX
  • experimentX
implies k should be odd ... (2y+1) .. such that k+1 = 2^p for some p ie, k+1 = 2, 4, 8, 16, ....
experimentX
  • experimentX
for k = 7, the expression (9k^2 + 9 k + 4) is 512 ... which shows that n = 2*7 + 2 = 23
experimentX
  • experimentX
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.
experimentX
  • experimentX
man this is tough .. gotta work on classical + statistical mechanics ... have exam five days later.
anonymous
  • anonymous
np man...how many exams do u have?
experimentX
  • experimentX
1 down three more to go ... + 2 practicals
anonymous
  • anonymous
oh man go back to ur work :)
experimentX
  • experimentX
yeah ... i'll watch the developments. physicist are not so good with numbers.
anonymous
  • anonymous
we have lots of times to work on brainwashing problems like this
experimentX
  • experimentX
sure
anonymous
  • anonymous
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\\ \]
anonymous
  • anonymous
I just did it \(n = 2 (10^6)\)
anonymous
  • anonymous
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}}
anonymous
  • anonymous
\[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\]
anonymous
  • anonymous
checking that numbers gives \(3\) solution : \(\color\red{n=3,7,23}\)

Looking for something else?

Not the answer you are looking for? Search for more explanations.