# Last digit of a number

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

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

## 1 Answer

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.

• 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)? – S.C.B. Apr 9 '16 at 10:51
• @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.) – joriki Apr 9 '16 at 11:00
• Thanks thats really good way using binary – Archis Welankar Apr 9 '16 at 11:04