Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

 2 Added explicit counterexamples when n0$$ numbers, its sum is $$k$$, which is not divisible by $$m$$. If we require them to be distinct, we can take $$1, m+1, 2m+1, \cdots, (m-2)m+1$$. Thanks to the above stronger proposition, we need to handle only cases of $$n \lt m$$ instead cases of $$n\le m$$ in the original article. Let us prove a slightly stronger statement. Notice that we do not require the given integers to be non-negative nor distinct. Also note that we do not require $$n$$ to be strictly greater than $$m$$. Given an array of $$n$$ integers, and a value m. If $$n \ge m$$ there will always be a subset with sum divisible by m. Suppose $$n\ge m$$. Let $$a_i$$ be the $$i$$-th element of the array, $$0\le i\le m-1$$. Let $$s_i=a_0+a_1+\cdots+a_i$$ and (pigeon) $$r_i=s_i\%m$$, the remainder of $$s_i$$ divided by $$m$$ . Note that $$0\le r_i\le m-1$$, i.e., the number of all possible values of remainders (holes) is $$m$$. Thera are two cases. All $$r_i$$ are distinct. Since the number of $$r_i$$ (pigeons) is $$m$$, all holes must be occupied by a pigeon. That means $$0=r_s$$ for some $$s$$. That is, $$a_0+\cdots+a_s$$ is divisible by $$m$$. All $$r_i$$ are not distinct. Suppose $$r_{i_1}=r_{i_2}$$ for some $$i_1. Then $$(a_{i_1}+a_{i_1+1}+\cdots+a_{i_2-1})\%m=(s_{i_2}-s_{i_1})\%m=s_{i_2}\%m-s_{i_1}\%m=r_{i_2}-r_{i_1}=0$$ Proof is done. Thanks to the above stronger proposition, we need to handle only cases of $$n \lt m$$ instead cases of $$n\le m$$ in the original article. Let us prove the following stronger proposition. Notice that we do not require the given integers to be non-negative nor distinct. Also note that we do not require $$n$$ to be strictly greater than $$m$$. Given an array of $$n$$ integers and a positive integer $$m\le n$$, there will always be a nonempty subset with sum divisible by m. Here is a simple proof.  Let $$a_i$$ be the $$i$$-th element of the array, $$0\le i\le m-1$$. Let $$s_i=a_0+a_1+\cdots+a_i$$ and (pigeon) $$r_i=s_i\%m$$, the remainder of $$s_i$$ divided by $$m$$. That is, $$s_i-r_i$$ is a multiple of $$m$$ and $$0\le r_i\lt m$$. Note that the number of all possible values of remainders (holes) is $$m$$. Thera are two cases. All $$r_i$$ are distinct. Since the number of $$r_i$$ (pigeons) is $$m$$, all holes must be occupied by a pigeon. That means $$0=r_s$$ for some $$s$$. That is, $$a_0+\cdots+a_s$$ is divisible by $$m$$. All $$r_i$$ are not distinct. Suppose $$r_{i_1}=r_{i_2}$$ for some $$i_1. Then $$(a_{i_1}+a_{i_1+1}+\cdots+a_{i_2-1})\%m=(s_{i_2}-s_{i_1})\%m=s_{i_2}\%m-s_{i_1}\%m=r_{i_2}-r_{i_1}=0$$ Proof is done. Note that $$m$$ is best lower bound of $$n$$ to ensure a nonempty subset with sum divisible by $$m$$. If we allow $$n\lt m$$, it is possible that there is no subset with sum divisible by $$m$$. For example, we can have $$m-1$$ 1's. For any subset of $$k>0$$ numbers, its sum is $$k$$, which is not divisible by $$m$$. If we require them to be distinct, we can take $$1, m+1, 2m+1, \cdots, (m-2)m+1$$. Thanks to the above stronger proposition, we need to handle only cases of $$n \lt m$$ instead cases of $$n\le m$$ in the original article. 1 answered Jan 3 at 18:38 Apass.Jack 19.5k22 gold badges1414 silver badges5050 bronze badges Let us prove a slightly stronger statement. Notice that we do not require the given integers to be non-negative nor distinct. Also note that we do not require $$n$$ to be strictly greater than $$m$$. Given an array of $$n$$ integers, and a value m. If $$n \ge m$$ there will always be a subset with sum divisible by m. Suppose $$n\ge m$$. Let $$a_i$$ be the $$i$$-th element of the array, $$0\le i\le m-1$$. Let $$s_i=a_0+a_1+\cdots+a_i$$ and (pigeon) $$r_i=s_i\%m$$, the remainder of $$s_i$$ divided by $$m$$ . Note that $$0\le r_i\le m-1$$, i.e., the number of all possible values of remainders (holes) is $$m$$. Thera are two cases. All $$r_i$$ are distinct. Since the number of $$r_i$$ (pigeons) is $$m$$, all holes must be occupied by a pigeon. That means $$0=r_s$$ for some $$s$$. That is, $$a_0+\cdots+a_s$$ is divisible by $$m$$. All $$r_i$$ are not distinct. Suppose $$r_{i_1}=r_{i_2}$$ for some $$i_1. Then $$(a_{i_1}+a_{i_1+1}+\cdots+a_{i_2-1})\%m=(s_{i_2}-s_{i_1})\%m=s_{i_2}\%m-s_{i_1}\%m=r_{i_2}-r_{i_1}=0$$ Proof is done. Thanks to the above stronger proposition, we need to handle only cases of $$n \lt m$$ instead cases of $$n\le m$$ in the original article.