0
$\begingroup$

I was currently solving a question of permutations and in that I had to find the total ways of something. The answer was ${8\choose 4}$ which has last digit $0$ .

A random thought that came to my mind was that whether we had a manual way to compute the last digit of a number such as ${369\choose 233}$ . I know after $4!$ all have last digit $0$ but somehow it might be possible that it gets cancelled and we have last digit as $5$. I know basics of modular algebra but not much in deep so can you guys help. Thanks

$\endgroup$
  • $\begingroup$ Sorry, but is the bracket notation for number of permutations or for combinations? $\endgroup$ – N.S.JOHN Apr 9 '16 at 10:55
  • 1
    $\begingroup$ @N.S.JOHN: This is the standard notation for a binomial coefficient $\binom nk$, which counts the number of $k$-combinations of $n$ elements. $\endgroup$ – joriki Apr 9 '16 at 11:03
  • 1
    $\begingroup$ Combinations are represented by it $\endgroup$ – Archis Welankar Apr 9 '16 at 11:03
  • $\begingroup$ @joriki@Archis Welankar Thanks. $\endgroup$ – N.S.JOHN Apr 9 '16 at 11:06
5
$\begingroup$

The remainder of binomial coefficients with respect to primes is given by Lucas' theorem: For non-negative integers $m$ and $n$ and a prime $p$,

$$\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\bmod p\;,$$

where $m_i$ and $n_i$ are the $i$-th digits of $m$ and $n$, respectively. To find the last digit of a binomial coefficient, we need its remainders modulo $2$ and $5$. For $\binom84$ we have

\begin{align} 8_{10}&=1000_2\;,\\ 4_{10}&=100_2\;,\\ 8_{10}&=13_5\;,\\ 4_{10}&=4_5\;, \end{align}

so

$$ \binom84\equiv\binom00\binom00\binom01\binom10\equiv0\bmod2 $$

and

$$ \binom84\equiv\binom34\binom10\equiv0\bmod5\;, $$

confirming that $\binom84\equiv0\bmod10$. For $\binom{369}{233}$ we have

\begin{align} 369_{10}&=101110001_2\;,\\ 233_{10}&=11101001_2\;,\\ 369_{10}&=2434_5\;,\\ 233_{10}&=1413_5\;, \end{align}

so

$$ \binom{369}{233}\equiv\binom11\binom00\binom00\binom01\binom10\binom11\binom11\binom01\binom10\equiv0\bmod2 $$

and $$\binom{369}{233}\equiv\binom43\binom31\binom44\binom21\bmod5\equiv4\bmod5\;,$$

yielding $\binom{369}{233}\equiv4\bmod10$, and indeed $\binom{369}{233}$ is

129169640332119737443677929159655724937368247006147295954110094567417591725745376306913730846211971776964.
$\endgroup$
  • $\begingroup$ If we were trying to find if it was $0$, which was your previous answer, couldn't we also just check how much trailing $0$s the above and the below has(without using Lucas's Theorem)? $\endgroup$ – S.C.B. Apr 9 '16 at 10:51
  • $\begingroup$ @MXYMXY: No, it's not just the number of trailing $0$s. The remainder with respect to $p$ is zero if and only if some digit of $m$ (in base $p$) is greater than the corresponding digit of $n$. (This is a direct corollary of Lucas' theorem.) $\endgroup$ – joriki Apr 9 '16 at 11:00
  • $\begingroup$ Thanks thats really good way using binary $\endgroup$ – Archis Welankar Apr 9 '16 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.