قضیه لوکاس $Lucas$ به ما می گوید که اگر $m$ و $s$ اعداد طبیعی باشند و $p$ عددی اول و:
$$ m=m_tp^t+m_{t-1}p^{t-1}+...+m_1p+m_0 $$
$$ ,s=s_tp^t+s_{t-1}p^{t-1}+...+s_1p+s_0 $$
آنگاه داریم:
$$ \binom{m}{s} \equiv \binom{m_t}{s_t} ... \binom{m_1}{s_1} \binom{m_0}{s_0} (modp)$$
طبق تعریف در اینجا اگر $s>m$ آنگاه $ \binom{m}{s} =0$.
حالا در این مسأله داریم:
$$k= \binom{p+n-1}{p} $$
پس می توان نوشت:
$$m=p+n-1=1^1p^1+(n-1)?,s=p=1^1p+0$$
$$ \Rightarrow k= \binom{p+n-1}{p} \equiv \binom{1}{1} \binom{n-1}{0} (modp) \equiv 1(modp)$$
$\Box $
می مونه اثبات قضیۀ لوکاس که در اکثر سایتها یا کتابهای نظریه اعداد هست.
