How many subsets $T$ of $X$ are such that the sum of the elements of $T$ is divisible by 5? Let the $X = \{1,2,\ldots,2000\}$. How many subsets $T$ of $X$ are such that the sum of the elements of $T$ is divisible by 5?
 A: Some thoughts, not a full answer:  You only care about the remainder of your numbers when divided by $5$.  Your set has $400$ with each remainder.  You can ignore the multiples of $5$ and multiply by $2^{400}$ at the end.  The answer will be a large number-it should be around $\frac 15 2^{2000}$
I would start by finding how many ways to pick from the $400$ items with remainder $1$ to get each remainder.  So to get remainder $2$ you have ${400 \choose 2} + {400 \choose 7} + \ldots +{400 \choose 397}$.  This will be the same as the number of ways to get remainder $4$ from the $2$'s.  Then find the number of ways to get each remainder from the $1$'s and $2$'s together, and so on.
A: An idea which might not lead anywhere.
Let $T_1, T_2, T_3, T_4$ denote the subsets of $X$ with the sum having a remainder of $1,2,3,4$ when divided by 5.
The complement function is a bijection from $T_1 \to T_4$ and $T_2 \to T_3$. So, if we find the cardinality of $T_1, T_2$ we are done.
Now, what I would do is looking to the subsets of $T_1, T_2$ which contain/don't contain any combination of $1,2,3$ (and maybe 4). Basically we are partitioning these sets in some subsets. If you can find a bijection between these partitions you are done.
A: Construct a generating function $g(x) = \prod_{i=1}^{2000} (1+x^i) = \sum a_n x^n$. We are looking for the sum of all $a_n$ where $5/n$.
Precisely those can be filtered out by plugging in powers of the fifth root of unity $\gamma$.
$$\dfrac{\sum_{i=0}^4 g(\gamma^i)}{5} = \dfrac{4\left(\prod_{k=1}^5(1+\gamma^i)\right)^{400}+2^{2000}}{5} = \dfrac{4.2^{400}+2^{2000}}{5}$$
This was just a quick sketch, but there is also a 3 blue 1 brown video on this problem https://www.youtube.com/watch?v=bOXCLR3Wric&t=1280s&ab_channel=3Blue1Brown
