I want to find $^nC_r \bmod m$, and see this relation that $n!^{-1}\cdot n \equiv (n - 1)^{-1} \pmod{m}$, but didn't get it.
Asked
Active
Viewed 65 times
0
-
2What is m here? Can m be anything? – fGDu94 Nov 20 '19 at 14:06
-
I can see it partially, $(n-1)!\equiv n-1\pmod n$ if $m$ were $n$, then it follows logically. okay partially confusing myself. – Nov 20 '19 at 14:28
-
yes m can be anything – joker Nov 20 '19 at 14:41
-
Multiply both members by $n!$. – Nov 20 '19 at 14:44
-
Should that be a factorial on the right hand side? – Mike Nov 20 '19 at 14:58
-
No @Mike, at least in mod $n$ it's equivalent to ${1\over n!}\cdot n\equiv {1\over n-1}\pmod n$ at least if treated fully like integers it's true. There's 1 catch in theory. – Nov 20 '19 at 15:39
-
If $n=4$ and $m=11$, $n!=24\equiv2\pmod{11}, n!^{-1}\equiv6\pmod{11},(n-1)^{-1}=3^{-1}\equiv4\pmod{11}$ The left side is equivalent to 2. The equivalence as written does not hold. It makes more sense as $\frac1{n!}\times n=\frac1{(n-1)!}$. – Mike Nov 20 '19 at 23:38
-
n = 4 and m = 11 the inverse of 4! mod 11 is 6 and inverse of 3! mod 11 is 2 $6 * 4 = 24 \equiv2\pmod{11}$ – joker Nov 21 '19 at 18:15
-
@joker But the OP claims in a previous comment that it is NOT a factorial on the right hand side. It's not $3!^{-1}$, it's $3^{-1}$. – Mike Nov 26 '19 at 19:40
-
oops! Mistook the person who edited it for the OP. Still, as written, there is no factorial on the right hand side. And it appeared like that before the edits as well. – Mike Nov 26 '19 at 19:45