1
$\begingroup$

I'm studying for a number theory exam. Our review sheets offers the question:

Under what conditions will $n$ divide $n \choose k$ for all 1 $ \leq k \leq n-1$?

I can see that this will be true for any prime $n$, and don't think that it would be true for any composite $n$, but am unsure in what direction I should proceed with the proof (prime decomposition, congruence, etc). Any and all help will be greatly appreciated!

$\endgroup$
1
$\begingroup$

I always recommend the same thing to my students when faced with such a question: work out a few basic examples first. It is usually a waste of time to think about such a question abstractly before you have a "feel" for it, and examples will almost always help in this regard. Even among advanced graduate students, the most effective problem solvers are, in my observation, very often simply those who think of trying small cases the fastest.

With that in mind, here is a suggestion that comes from playing around with binomial coefficients. If $n$ is composite, then clearly $n\choose 0$, $n\choose 1$, $n\choose {n-1}$, and $n\choose n$ cannot provide counterexamples. But there is one very good number to check, the simplest one that makes use of the fact that $n$ is composite: $n\choose p$, where $p$ is the smallest prime factor of $n$.

(Some of this is mentioned in the link in the comments, but I feel that most of the answers there overcomplicate things just a tad. Still it's good to be aware of the general patterns, so you can check out the link for a more general discussion about what happens for other factors and non-factors of $n$.)

$\endgroup$
  • $\begingroup$ since this is a duplicate, if you think that this answer add contributions to the original question, you should post this answer to the original post $\endgroup$ – user126154 Mar 17 '14 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.