Composite numbers dividing binomial coefficients

Let k k be the number of composite integers n n that satisfy the condition that n n is a factor of ( n r ) \dbinom{n}{r} for all r { 1 , 2 , 3 , , n 1 } . r\in \{ 1, 2, 3, \ldots, n-1\}. Which one of the following statements is always true for k k ? Prove that your answer is right.

Note : An integer number is called composite if it is greater than 1 and has at least a factor that is different from 1 and from itself.

0 < k 1000 0<k\leq 1000 k k is infinite k = 0 k=0 1000 < k 1000000 1000<k\leq 1000000

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Arturo Presa
May 6, 2016

The answer is k = 0. k=0. The reason is simple, if n n is composite, then there is a prime number p p that is a factor of n n , and it is easy to see that n n is not a factor of ( n p ) . \binom{n}{p}.

Mark Hennings
May 10, 2016

If n n is composite and p p is a prime dividing n n , then 1 < p < n 1 < p < n and ( n p ) = n ( n 1 ) ( n 2 ) ( n p + 1 ) p ! {n \choose p} \; = \; \frac{n(n-1)(n-2)\cdots(n-p+1)}{p!} Of the p p consecutive integers being multiplied together in the numerator, only n n is a multiple of p p . Thus the index of p p in the numerator (the number of times p p divides the numerator) is equal to the index of p p in n n . On the other hand, the index of p p in the denominator is 1 1 . This tells us that the index of p p in ( n p ) \binom{n}{p} is 1 1 less than the index of p p in n n , which means that n n cannot divide ( n p ) \binom{n}{p} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...