$C(n,p)$: even or odd? Can we determine if a binomial coefficient $C(n,p)$ is even or odd, without calculating its value? 
($p\lt n$, $p$ and $n$ are positive integers)
 A: There is a beautiful result of Kummer that says that if $q$ is a prime, then the largest power of $q$ that divides $\binom{m+n}{n}$, $m$ and $n$ nonnegative, is the number of carries when $m$ and $n$ are added in base $q$. 
As a corollary, we get the Theorem of Lucas mentioned by Michael Lugo: we get a carry in the addition if and only if there is a $k$ such that the $k$th digit of $m+n$ in base $q$ is smaller than the $k$th digit in the base $q$ expansion of $n$, so $\binom{m+n}{n}$ is divisible by $q$ if and only if there is a $k$ such that the $k$th digit of the base $q$ expansion of $m+n$ is smaller than the $k$th digit of the base $q$ expansion of $n$. 
Thus, to determine if $\binom{n}{p}$ is odd, you just need to know whether there is at least one carry when adding $p$ and $n-p$ in base $2$; you get a carry exactly when the $k$th binary digit of both $n-p$ and $p$ is $1$.
So just write $p$ and $n-p$ in binary, one digit at a time (from least significant to most significant digit), until you get that both are $1$; or write $p$ and $n$ one binary digit at a time, until you get a $1$ in $p$ and a $0$ in $n$. If this happens, $\binom{n}{p}$ is even; otherwise, it is odd. 
Andrew Granville's paper Arithmetic properties of binomial coefficients is chock full of interesting stuff about binomial coefficients and their divisibility. The proof of Kummer's Theorem can be found there. There are also other formats available.  
A: Motivated by a duplicated question that has been asked today, I'd like to offer an alternative approach to the problem.
Let $C_n^r$ be the set of subsets of $\{1,\ldots,n\}$ that have cardinal $r$. Define the function $\sigma:C_n^r\to C_n^r$ given by
$$k\in\sigma(A)\Leftrightarrow n-k\in A$$
Let $S_n^r$ be the set of the fixed points of $\sigma$ and $T_n^r=C_n^r-S_n^r$. It is clear that $f\circ f=id$. Thus, $|T_n^r|$ is even and $|C_n^r|$ and $|S_n^r|$ have the same parity.
Let's study the parity of $|S_n^r|$. Represent each element of $A\in S_n^r$ with a binary word of length $n$ whose $k$th digit is $1$ if $k\in A$ and $0$ otherwise. So, the elements of $S_n^r$ are the symmetric words. For each of these symmetric words:


*

*If $n$ is odd, there is a central digit. If $r$ is odd it must be $1$, otherwise $0$. Any case, the word is determined by the $\lfloor n/2\rfloor$ first digits and $\lfloor r/2\rfloor$ of these digits are $1$'s. Therefore,
$$|S_n^r|=\binom{\lfloor n/2\rfloor}{\lfloor r/2\rfloor}$$

*If $n$ is even, $r$ must be even and there must be $r/2$ of $1$'s each side. Then
$$|S_n^r|=\left\{
\begin{array}{cl}
\binom{\lfloor n/2\rfloor}{\lfloor r/2\rfloor}&\text{ if $r$ is even}\\
0&\text{ otherwise}
\end{array}
\right.$$
Thus, we have a method that allows to obtain the parity of $\binom nr$ in at most $\log_2 r$ steps.
Example:
$$\binom{1000}{376}\equiv\binom{500}{188}\equiv\binom{250}{94}\equiv\binom{125}{47}\equiv\binom{62}{23}\equiv 0\pmod 2$$
A: Yes.
We only need to know how many powers of two appear in the prime factorization of C(n,p). The number of powers of two that appear in the prime factorization of $n!$ is $\lfloor n/2 \rfloor + \lfloor n/4 \rfloor + \lfloor n/8 \rfloor + \cdots$ -- count all the multiples of two, of four, of eight, and so on. This turns out to be $n$ minus the number of ones in the binary expansion of $n$.
It turns out that this reduces to the following: C(n,p) is odd if and only if every bit of the binary expansion of $p$ is less than or equal to the corresponding bit of the binary expansion of $n$. This is due to Lucas.
A: I already commented with one Wikipedia link above, but I just want to add that if you run the Pascal's triangle recurrence $\bmod 2$ what you get is a sequence of approximations to the Sierpinski triangle.  So the result that comes out of Lucas' theorem is an explicit nonrecursive algorithm for plotting the Sierpinski triangle.
I also want to take this opportunity to mention a paper which discusses generalizations of this problem, and which is both quite entertaining to read and perhaps has one of the strangest titles of any math paper: Granville's Zaphod Beeblebrox's Brain and the Fifth-Ninth Row of Pascal's Triangle.
A: I'm surprised that noone mentioned this.
Here is a plot of the parity of ${n\choose p}$ for $n,p\le256$. Black is odd.

You get a pattern that is exactly the Sierpiński triangle. Analyzing this pattern leads naturally to a way to compute directly the parity of ${n\choose p}$.
A: If $n$ is even and $k$ is odd, then $\binom{n}{k}$ is always even, without any additional calculation or condition, see my proof at the and of this article.
