Tagged Questions
0
votes
1answer
30 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
139 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 understand ...
1
vote
3answers
56 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 ...
3
votes
1answer
282 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
123 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
742 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
233 views
Lucas Theorem for combinatorics?
Can anyone give me an example of Lucas Theorem and how it works? What about for composite modulus?
3
votes
1answer
356 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, ...
