Explore BrainMass

Congruences and Primes

Prove that is p is prime, we have:

n choose m is congruent to [floor(n/p) choose floor(m/p)]*[(n mod p) choose (m mod p)] (mod p)

Hint: show that (1+x)^(pq+r) is congruent to (1+x)^r * (1+x^p)^q (mod p)

If you can point me to a book or website explaining how to do this type of problem, and give a sketch of the proof, that would be great.


Solution Summary

Congruences and Primes are investigated. The solution is detailed and well presented.