mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-08-09, 17:53   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

23·232 Posts
Default 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.)
davar55 is offline   Reply With Quote
Old 2007-08-09, 18:52   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by davar55 View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2007-08-09, 19:22   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

423210 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
davar55 is offline   Reply With Quote
Old 2007-08-09, 20:02   #4
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

455610 Posts
Default

Didn't he just prove it IS DIVISIBLE BY 7?
petrw1 is offline   Reply With Quote
Old 2007-08-09, 20:10   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

17·79 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
2LMs with exponent divisible by 13 Batalov Cunningham Tables 1 2011-04-14 10:23
5th RPS Drive: 14 Ks < 300 divisible by 3 Kosmaj Riesel Prime Search 756 2008-07-04 12:50
Divisible by a Prime davar55 Puzzles 13 2007-09-12 17:35
Divisible up to Square Root davar55 Puzzles 3 2007-09-05 15:59
Divisible by 7 davar55 Puzzles 3 2007-05-14 22:05

All times are UTC. The time now is 08:03.

Tue Mar 9 08:03:03 UTC 2021 up 96 days, 4:14, 0 users, load averages: 1.89, 1.96, 1.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.