Do you mean $2^{p-1}-1$ is not a multiple of $p^2$?

PhilippineMonkey wrote: Do you mean $2^{p-1}-1$ is not a multiple of $p^2$? Yes. My bad.

I solved this problem using the generating function, but I've heard there's a simpler solution than this Def) for $1\le i\le p-1$, $a_i$ the number of subsets of $\{1,2,\cdots,p-1\}$ such that the sum of elements of the subset is $i \, (mod p)$ ($\Sigma a_i =2^{p-1}$) Def) for polynomial $L(x)$, $n(L)$ as the sum of coefficient of the terms that have degree that is multiple of p Def) $f(x)=1+x+\cdots+x^{p-1}$ , and its root as $\omega, \omega^2, \cdots, \omega^{p-1}$ Def) $g(x)=(1+x)(1+x^2)\cdots(1+x^{p-1})$ Def) $h(x)=a_0 +a_1 x+\cdots+a_{p-1} x^{p-1}$ Def) $a=\frac{2^p -1}{p}$ Claim 1) for any polynomial $L(x)$, $n(L)=\frac{L(1)+L(\omega)+\cdots+L(\omega^{p-1})}{p}$

pf

Claim 2) for $1\le i\le p-1$, $g(\omega^i)=1$

pf

Claim 3) for $1\le i\le p-1$, $a_i=a$

pf

Now lets prove the original problem. We will take the $m=np$. While counting $A(m)$, firstly note that multiple of p doesnt affect the sum of element's modulo. It is enough to count $\frac{A(m)}{2^n}$, with not using the multiple of p. Say S is the subset of $\{1,2,\cdots,p-1\}$ Lets denote $x_1=\Sigma_{s\in S, \, s<p} \, s\, (mod \,p)$ $x_2=\Sigma_{s\in S, \, p<s<2p} \,s \,(mod \,p)$, and on to $x_n$. For S to be counted as A(m), $p\mid x_1+x_2+...+x_n$ . $\therefore \frac{A(m)}{2^n}=\Sigma_{\{x_1, x_2, ..., x_n\}, \, p\mid x_1+x_2+...+x_n } \,a_{x_1} a_{x_2}\cdots a_{x_n} $ We can see that the right side is $n(h(x)^n)$. By using Claim 1), $\therefore \frac{A(m)}{2^n} p=h(1)^n+h(\omega)^n+\cdots+h(\omega^{p-1})^n$ Meanwhile, $h(x)=(2^{p-1}-(p-1)a)+a(x+x^2+\cdots+x^{p-1})$ $h(1)=2^{p-1}$ for $ 1\le i\le p-1$, $h(w^i)=2^{p-1}-pa=1$ $\therefore \frac{A(m)}{2^n} p=2^{(p-1)n} +(p-1)=(pa+1)^n+(p-1)$ $RHS \equiv npa+p \, (mod \,p^2 )$ $\therefore A(m) \equiv 2^n (na+1) \, (mod \,p^2)$ take $p-1 \mid n$, then the set of remainder of A(m) by p represents all 0 to p-1 by infinite times.

How sad, this is just routine complex combinatorics. See, for instance, PFTB chapter 4, example 7. Lemma: The number of subsets of $\{1,2,\ldots,an\}$ whose sum of elements is divisible by $n{}$ is equal to \[\frac{1}{n}\sum_{\substack{d\mid n \\ 2\nmid d}}\varphi(d)\cdot2^{an/d}.\]Proof: Consider the polynomial \[f(X)=\prod_{i=1}^{an}(a+X^i)=\sum_{i\geqslant 0}a_iX^i.\]We are interested in the sum $a_0+a_n+a_{2n}+\cdots$. Let $\omega$ be an $n^{\text{th}}$ root of unity. By the so-called root of unity filter, we have \[\sum_{i\geqslant 0}a_{in}=\frac{1}{n}\sum_{i=1}^n f(\omega^i).\]Fix an $i{}$ and let $d=n/\gcd(i,n)$, hence $\omega^i$ is a $d^{\text{th}}$ root of unity. There are $\varphi(d)$ values of $i{}$ for which this happens. We have \[(-1)^d(X^d-1)=\prod_{i=1}^d(\omega^{id}-X),\]hence $f(\omega^i)$ equals $2^a$ for odd $d{}$ and $0{}$ otherwise. This, along with the formula for $a_0+a_n+a_{2n}+\cdots$ finishes. $\square$ Back to our problem, we naturally want to take $m=pk$ for some adequately chosen $k{}$. That is, we set $n=p$ and $a=k$ in our lemma, hence \[A(pk)=\frac{1}{p}\left(2^{pk}+(p-1)2^k\right)=2^k\left(1+\frac{2^{(p-1)k}-1}{p}\right).\]Letting $\lambda\neq 0$ be the residue of $(2^{p-1}-1)/p$ modulo $p{}$, we easily evaluate $A(pk)\equiv 2^k(1+\lambda k)\bmod{p}$, done.

Well I disagree with this being "sad", in fact this idea is quite beautiful and seems novel every time I apply it. I agree that it is pretty routine, however. Also it is quite funny that I have the same choice of variables and similar structure to #5 as I typed the rest of the solution elsewhere originally. $\textbf{Lemma:}$ $$A(pk) = 2^k\left(1+\frac{2^{k(p-1)}-1}{p}\right)$$$\textbf{Proof)}$ Let $$F(x) = \prod_{i=1}^{kp}(1+x^i) = \sum_{i \geq 0} a_ix^i$$and $P(x) = x^p-1$. By root of unity filter, we have that $$\text{number of subsets with sum a multiple of p} = \sum_{p \mid i} a_i = \frac{1}{p} \sum_{\zeta} F(\zeta)$$where $\zeta$ varies among the $p$-th roots of unity. Then, notice that $F(\zeta) = (-1)^{pk} \cdot (P(-\zeta))^k = ((-1) \cdot (-2))^{k} = 2^{k}$ unless $\zeta = 1$ in which case $F(\zeta) = 2^{pk}$. Therefore $$A(pk) = \frac{1}{p}(2^{pk}+(p-1)2^k) = 2^k\left(1+\frac{2^{k(p-1)}-1}{p}\right)$$which proves the $\textbf{Lemma}$. $\blacksquare$ Now, fix $k \pmod{p-1}$ and vary $k \pmod{p}$, we can see that $\frac{2^{k(p-1)}-1}{p}$ will vary freely $\pmod{p}$ as $\varphi(p^2) = p(p-1)$, so we are done. $\blacksquare$ $\blacksquare$

It's also true that $p|A(m)$ has a solution for all $p$.