Determine the largest 3 - digit prime factor of 2000 C 1000.
n C r denotes the number of combinations of n things taking r at a time.
The solution to this puzzle is as follows.<o:p> </o:p>
Let us define [x] as the greatest integer contained in x. For example, [4.5] is 4.
Suppose, r be any 3 digit prime.
Accordingly, r^2 >2000.Thus the highest power of r that divides 2000! is [2000/r] and the highest power of r that divides 1000! is [1000/r].
Now, 2000 C 1000 =(2000!)/(1000!)^2.
Consequently, the highest power of r that divides
2000 C 1000 is [2000/r] – 2*[1000/r].
If r>666, then [2000/r] – 2*[1000/r] =2-2*1=0, so that, r does not divide 2000 C 1000.
Therefore, the desired prime is the largest one such that it is less than 666.
When r=661, we observe that [2000/r] – 2*[1000/r]
= 3 – 2*1 =1.
Consequently, it follows that 661 is the largest 3-digit prime that divides 2000 C 1000.