<s>[INST] ${3^n\choose k}$ is divisible by $3$? How can I prove that ${3^n\choose k}$ is divisible by $3$ for all positive integer values of $n$? (where $k$ is any positive integer smaller than $3^n$) Can you use induction? Thanks.
 [/INST] I just want to demonstrate the relevance of if $p$ is prime and $0<t<p$ then $p$ divides $\displaystyle \binom p t$
Consider $$\begin{split}(x+y)^p 
& =\sum_{k=0}^p \binom p k x^{p-l} y^{k} \\
& =x^p+\binom p 1x^{p-1}y+\binom p 2x^{p-2}y^2+\cdots+\binom{p}{p-1}xy^{p-1}+y^p\\
& = x^p + y^p \mod p
\end{split}$$
Hence 
$$\begin{split}
(x+y)^{p^n} &= \left((x+y)^p\right)^{p^{n-1}} \\
&= \left(x^p+y^p \mod p\right)^{p^{n-1}}\\
&= (\left(x^p+y^p \mod p\right)^p)^{p^{n-2}}\\
&= \left(x^{p^2}+y^{p^2} \mod p\right)^{p^{n-2}}\\
& \vdots\\
& = x^{p^n}+y^{p^n} \mod p
\end{split}$$
But also
$$\begin{split}
(x+y)^{p^n} 
& =\sum_{k=0}^{p^n} \binom{p^n}{k} x^{p^n-l} y^{k} \\
& =x^{p^n}+\binom{p^n}{1}x^{p^n-1}y+\binom{p^n}{2}x^{p^n-2}y^2+\cdots+\binom{p^n}{p^n-1}xy^{p^n-1}+y^{p^n}\\
& = x^{p^n}+y^{p^n} \mod p
\end{split}$$
Therefore $p$ divides $\displaystyle\binom{p^n}{k}$ for all $k$ with $0<k<p^n$
</s>