Wikipedia:Reference desk/Archives/Mathematics/2023 November 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 30

Binomial and Prime

Let n be a positive integer, and p be a prime number such that n! is divisible by p²⁰²², but not p²⁰²³. Define m as the number of terms in the expansion of (1+x)ⁿ that are divisible by p. (This is not my HW question so don't tag that, but I just want to know if the data is sufficient and if answer is m=2022 or 2023). ExclusiveEditor _{Notify Me!} 19:21, 30 November 2023 (UTC)

Let e=2022. Take p>e so n can be any number between ep and ep+p-1. By terms in the expansion of (1+x)ⁿ I assume you mean binomial coefficients choose(n, i). If n=ep+k where 0≤k<p then (assuming my calculations are correct) number of i for which choose(n, i) is divisible by p is e(p-k-1). So there is not enough information given and the m would only be e if k=p-2. --RDBury (talk) 02:36, 1 December 2023 (UTC)

PS. In general, if p is prime and the base p representation of n is (d_kd_k-1...d₁d₀)_p, then the number of nonzero binomial coefficients choose(n, i) which are not divisible by p is (d_k+1)(d_k-1+1)...(d₁+1)(d₀+1). --RDBury (talk) 10:37, 1 December 2023 (UTC)

That's an extraordinarily interesting relation. Working with Legendre's formula, one gets that $p\not |{n \choose m}$ if and only if $\forall k\in \mathbb {Z} _{\geq 1},\lfloor {\frac {n}{p^{k}}}\rfloor =\lfloor {\frac {m}{p^{k}}}\rfloor +\lfloor {\frac {n-m}{p^{k}}}\rfloor$. I was stuck on obtaining the number of $m$ satisfying this, but upon reviewing the relation you have established it becomes clear once you realize that in order for this relation to hold, all the digits $m_{k}$ of $m$ in base $p$ must be at most equal to the corresponding digit $d_{k}$. So $p\not |{n \choose m}$ if and only if each digit of $m$ is less than or equal to each digit of $n$ in base $p$, and from the number of choices for each $d_{k}$ being $d_{k}+1$ one obtains the formula you found of $\prod _{k=0}^{\infty }(d_{k}+1)$. GalacticShoe (talk) 14:22, 1 December 2023 (UTC)

Yes, and you can say more. I assume this is well known though I don't know if it has a name, but if the base p expansion of n is (d_kd_k-1...d₁d₀)_p and the base p expansion of i is (a_ka_k-1...a₁a₀)_p, where padding with 0's is used if necessary, then:

${n \choose i}\equiv {d_{k} \choose a_{k}}{d_{k-1} \choose a_{k-1}}\dots {d_{1} \choose a_{1}}{d_{0} \choose a_{0}}\mod p.$

Here the binomial coefficient is taken to be 0 if the "numerator" is less than the "denominator". If you consider S_n acting on the subsets of order i in {0, 1, ..., n-1}, then the lhs is the total number of elements and the rhs is the number of fixed points of a Sylow p-subgroup of S_n. The article Sierpiński triangle is relevant here, specifically the sections on Pascal's triangle and Generalization to other moduli. --RDBury (talk) 17:05, 1 December 2023 (UTC)

I looked it up and Wikipedia apparently has it under Lucas's theorem, named after Édouard Lucas of Lucas number fame. GalacticShoe (talk) 06:58, 5 December 2023 (UTC)

Moreover, Kummer's theorem is the theorem that the largest integer $k$, such that $p^{k}$ divides the binomial coefficient $n \choose m$, is equal to the number of carries that occur when $m$ is added to $n-m$ in base $p$. This theorem implies that $p$ does not divide $n \choose m$ if and only if there are zero carries, and of course this corresponds to the expression involving floors in my original reply. GalacticShoe (talk) 07:10, 5 December 2023 (UTC)