Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's consider $C(n,k)$ as newton symbol. Lucas Theorem states that $C(n,k)$ is divisable by prime $p$ if and only if at least one of the base $p$ digits of $k$ is greater than the corresponding digit of $n$.

But what if we have p non-prime? Is it only way to factorize it to $p_1^{a_1}, p_2^{a_2}....p_n^{a_n}$ and check if this relation is true for each $p_i$?

Is there any faster approach? Cheers

share|improve this question

1 Answer 1

up vote 5 down vote accepted

I do not believe that there is a generalization of Lucas's Theorem for general composite integers. However, there is a generalization for prime powers. I read the paper a while ago, and I'm no longer incredibly familiar with the proof, but the paper is here.

The big idea is Theorem 1 in the paper linked above. It states

Suppose that a prime power $p^q$ and positive integers $m = n + r$ are given. Write $n = n_0 + n_1p + ... + n_dp^d$ in base $p$, and let $N_j$ be the least positive residue of $[n/p^j] \mod p^q$ for each $j \geq 0$ (i.e. $N_j = n_j + n_{j+1}p + ...$). Define $m_j, M_j, r_j, R_j$ likewise. Let $e_j$ be the number of indices $i \geq j$ for which $n_i < m_i$ (the number of 'carries' when adding $m$ and $r$ in base $p$. Then

$$\frac{1}{p^{e_0}} {n \choose m} \equiv (\pm 1)^{e_q - 1} \left( \frac{ (N_0 !)_p}{(M_0!)_p(R_0!)_p} \right)\left( \frac{ (N_1 !)_p}{(M_1!)_p(R_1!)_p} \right) ... \left( \frac{ (N_d !)_p}{(M_d!)_p(R_d!)_p} \right) \mod p^q$$ where $\pm1$ is $-1$ except if $p = 2$ and $q \geq 3$, and $(n!)_p$ is the product of the integers less than or equal to $n$ that are not divisible by $p$.

The paper goes on to explain how it can be computed quickly, i.e. in time $O(\log ^2n + q^4\log n \log p + q^4 p \;\log^3 p)$. This is the best generalization of Lucas's Theorem that I've ever come across.

share|improve this answer
For the above generalization of Lucas' Theorem, should it be n=m+r instead of m=n+r? In addition, I don't think the number of indices $i \ge j$ for which $n_i < m_i$ is the same as the number of 'carries' when adding m and r in base p. For example, base 10, n=190, m=94, r=94, for $e_0$ the number of carries is 2 but using another definition it is 1. Can anyone clarify this for me?Thanks, –  csLittleye Nov 29 '12 at 3:45
I think the number carries when you are adding a and b in base p is same as the number of power p in (a+b)Cb. Am I right ? –  rnbcoder Jul 28 '13 at 22:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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