user51819
Reputation
317
Top tag
Next privilege 500 Rep.
Access review queues
 Aug 30 awarded Nice Question Aug 27 awarded Yearling Aug 23 comment How do I get rid of the coefficient in this congruence? Also interested in this. What does your last sentence mean? Aug 15 accepted $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ Aug 15 comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ So with the edit to p^a I now use inverse mod (extended gcd), answers still do not seem to match the correct results (I am comparing against a slow but correct n choose k mod p^e implementation) Aug 15 comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ I tested it and it does not seem to work (although the error may be mine). For the line "currentans * numer / denom (mod p)" I tried "currentans * numer * denom^(p-2) mod p" Aug 15 comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ I have to compute the coefficients over many $k$ (so for example for $k=1$ to $10^5$, for some unchanging $n$), and so if max $k$ is $10^5$ then that's $O(k^2)$ runtime for $10^5$. I also tested it for speed. Aug 15 comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ Although I thought it was $\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$ ? Aug 15 comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ As mentioned in the original post, iterative identities like these are prone to coprimality issues when the denominator $k$ is not invertible mod $p^a$. I am not sure what you mean by tracking exponents separately. Aug 15 revised $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ added 116 characters in body Aug 15 comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ I should add that $k$ is small, but not so small where I can store all values of $k!$ in memory (without modulus applied). Otherwise I'd have a solution for this. Aug 15 asked $\binom{n}{k}$ modulo prime power for large $n$ and small $k$ Aug 3 comment Solutions to ax = by mod m? @GregMartin There isn't a complete solution anywhere, either in a book or online Aug 3 asked Solutions to ax = by mod m? Apr 4 accepted Can this congruence be reduced? Apr 4 comment Can this congruence be reduced? @JBKing Oh, in this case, no I don't think that applies here Apr 4 comment Can this congruence be reduced? @JBKing I am not sure what you are asking, but it is possible for there to be no solutions to this congruence depending on the value of $x$ I suppose Apr 4 asked Can this congruence be reduced? Apr 2 awarded Curious Apr 1 comment How to compute this limit with different operations of $x$? Wouldn't that just be 0?