<s>[INST] How to prove $n{n+9 \choose 8} \bmod 10 = 5 \Rightarrow n \bmod 16 \in \{1,3,5,15\}$ In reading this question I noticed that the values of $n$ there for which $s(n)$ there has the last digit equal to $5$ are a subset of OEIS A103127. Combining that observation with another comment in the above question, plus a little numerical test, led to the following conjectures:
$$n{n+9 \choose 8} \bmod 10 = 5 \Rightarrow n \bmod 16 \in \{1,3,5,15\}$$
and:
$$n \bmod 16 \in \{1,3,5,15\} \land n \bmod 10 \neq 9 \Rightarrow n{n+9 \choose 8} \bmod 10 = 5$$
Any idea for how to prove them?
 [/INST] Consider mod 2: $ n { n+ 9 \choose 8} \equiv 1 \pmod{2}$.
We must have both

*

*$ n \equiv 1 \pmod{2} $, and

*$ n + 9  \equiv 8, 9, 10, 11, 12, 13, 14, 15 \pmod{16} $ by Lucas theorem.

This simplifies to $ n \equiv 15, 1, 3, 5 \pmod{16}$.
This answers the first part of your question.

Consider mod 5: $ n { n + 9 \choose 8 } \equiv 0 \pmod{5}$, so either

*

*$ n \equiv 0 \pmod{5}$, or

*$ n+ 9 \not \equiv 8, 9, 13, 14, 18, 19, 23, 24 \pmod{25}  $ by Lucas Theorem.

This simplifies to $ n \equiv 1, 2, 3, 6, 7, 8, 11, 12, 13, 16, 17, 18, 19, 20, 21, 22, 23  \pmod{25}$.

Hence, the full solution set could be described in mod $16\times25 = 400$, which I leave you to find the $4\times 17 = 68$ residue classes.
Note that $n = 19 $ is an example of a solution that you've rejected in your classification since $ n \equiv 9 \pmod{10}$. However, it's indeed a solution as verified by Wolfram in your numerical test.

</s>