5
$\begingroup$

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

2 Answers 2

6

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.

  • 0
    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 ?2013-07-28
1

As far as I know, there isn't a way to figure out the divisibility of a factorial modulo a non-prime without first factoring - though depending on your needs, there might be a faster way.

Lucas' theorem is used for figuring out the exact value of $C(n, k)$ mod prime $p$ without need to use large numbers (it doesn't need to calculate factorials greater than $(p-1)!$). If you only need to know whether or not $p$ divides $C(n, k)$, you can just break $C(n, k)$ into the component parts and use Legendre's Theorem with some basic arithmetic.

Specifically, if we define $L(n, p)$ to be applying Legendre's Theorem to the factorial of an integer $n$ with respect to prime $p$, the maximal power of $p$ that divides $C(n, k)$ is $L(n, p) - L(k, p) - L((n-k), p)$, which I'll refer to as $L_{nCk}(n, k, p)$. $L_{nCk}(n, k, p)$ returns a count of factors of $p$ in $C(n, k)$ by figuring out the maxmal power of $p$ that divides $n!$ and subtracting the maximal power that divides $k!$ and the maximal power that divides $(n-k)!$. If this is $0$, then $p$ does not divide $C(n, k)$ since the factors of $p$ in the numerator of the exapnsion of $C(n, k)$ get canceled by the factors of $p$ in the denominator.

Taking all this together, to find the answer for a generic composite number, break it into its prime factors $\prod p_i^{a_i}$ and verify that $L_{nCk}(n, k, p_i) \ge a_i$ for each $p_i$.

If you do need to know the value of the resultant modulus, the paper that mixedmath linked is currently the only way to get what you need. (You'll need to use the Chinese Remainder Theorem to build up the resultant modulus from the moduli with respect to the factors that build up your generic composite number. This is much more complex than simply using $L_{nCk}(n, k, p)$ unfortunately.)