1
vote
1answer
34 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
1
vote
2answers
110 views

Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.

I've been grappling with this problem for a while but haven't solved it. Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.
14
votes
2answers
353 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
1
vote
2answers
61 views

${{p^k}\choose{j}}\equiv 0\pmod{p}$ for $0 < j < p^k$

$${{p^k}\choose{j}}\equiv 0\pmod{p}.\ \ \ \text{for $0 < j < p^k$ and p is prime}$$ I can show this for $k=1$ using the fact that in denominator all numbers are less than $p$. I need hint ...
0
votes
1answer
55 views

How to maximize $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?

Short Version of the Question: How do I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$? Long Version of the Question: I'm currently attempting ...
1
vote
0answers
337 views

Binomial coefficient modulo prime power without generalized Lucas theorem

I've been working on this problem computing $n \choose r$ for large $n$ and $r$, modulo a composite. I could implement the generalized lucas theorem to handle the prime power case, but I want to ...
1
vote
3answers
76 views

If p is a prime number greater than 2 and k is a natural number so that k<p, how can I prove that…

If $p$ is a prime number greater than 2 and $k\in \mathbb{N}$ so that $k < p$, how can I prove that $p\choose k$ is congruent to $0 \mod p$. I'm sorry I know my formatting is rough but I don't ...
4
votes
1answer
775 views

Binomial coefficient modulo prime power

I am trying to understand how to find binomial coefficients modulo a power of a prime. I am reading the paper by Andrew Granville for this. But I am unable to understand it completely. More ...
1
vote
0answers
168 views

Lucas' theorem Consequence

Lucas' theorem consequence $$\binom {m}{n}=\ \prod_{i=0}^k\;\ \binom {m_i}{n_i} \pmod{p},$$ $$m=m_k\;p^k+m_{k-1}\;p^{k-1}+\cdots +m_1\; p+m_0,$$ $$n=n_k\;p^k+n_{k-1}\;p^{k-1}+\cdots +n_1\;p+n_0$$ ...
1
vote
1answer
974 views

${n \choose k} \bmod m$ using Chinese remainder theorem?

I don't really see too many sites explaining how this is done. Does anyone know how this works? I'm trying to find $\binom{n}{k}\bmod m$, where $n$ and $k$ are large and $m$ is not prime. I think it ...
1
vote
1answer
380 views

Lucas Theorem for combinatorics?

Can anyone give me an example of Lucas Theorem and how it works? What about for composite modulus?
4
votes
1answer
563 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...