Lucas Theorem but without prime numbers

Question

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

Answer 1

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.