mersenneforum.org Divisible by 7 ?
 Register FAQ Search Today's Posts Mark Forums Read

 2007-08-09, 17:53 #1 davar55     May 2004 New York City 3·17·83 Posts Divisible by 7 ? Show that C(1000,500) = 1000C500 = (1000!)/(500!)2 is in fact NOT divisible by 7. (Without of course multiplying it out.)
2007-08-09, 18:52   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by davar55 Show that C(1000,500) = 1000C500 = (1000!)/(500!)2 is in fact NOT divisible by 7. (Without of course multiplying it out.)
Counting the number of times 1000! is divisible by 7 yields

floor(1000/7) + floor(1000/49) + floor(1000/343) = 162

Counting the number of time 500! is divisible by 7 yields (similarly) 81.

Thus (500!)^2 is divisible by 7 162 times, as is 1000!. QED

2007-08-09, 19:22   #3
davar55

May 2004
New York City

423310 Posts

Quote:
 Originally Posted by R.D. Silverman Counting the number of times 1000! is divisible by 7 yields floor(1000/7) + floor(1000/49) + floor(1000/343) = 162 Counting the number of time 500! is divisible by 7 yields (similarly) 81. Thus (500!)^2 is divisible by 7 162 times, as is 1000!. QED
Correct solution except I think you meant the sum for 1000 to be
142 + 20 + 2 = 164,
and the sum for 500 to be
71 + 10 + 1 = 82,
which gives the same result about divisibility.

 2007-08-09, 20:02 #4 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 22·5·233 Posts Didn't he just prove it IS DIVISIBLE BY 7?
 2007-08-09, 20:10 #5 alpertron     Aug 2002 Buenos Aires, Argentina 24·5·17 Posts He proved that it is not divisible by 7. Let a = 1000! = k*7^164 and b = 500!^2 = m*7^164 (where k and m are not divisible by 7). So we get a/b = k/m. The fraction a/b is not divisible by 7 because k is not divisible by 7.

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov Cunningham Tables 1 2011-04-14 10:23 Kosmaj Riesel Prime Search 756 2008-07-04 12:50 davar55 Puzzles 13 2007-09-12 17:35 davar55 Puzzles 3 2007-09-05 15:59 davar55 Puzzles 3 2007-05-14 22:05

All times are UTC. The time now is 00:13.

Sun Jun 20 00:13:08 UTC 2021 up 22 days, 22 hrs, 0 users, load averages: 1.86, 1.71, 1.58