Let $p$ be an odd prime and $k\in \mathbb{N}$.

Let $S$ be the set of even coprime integers relative to $p^k$.

Question: If we take all the sums of all subsets of $S$ (with at least one element and without repeating elements), can we get all the even numbers up to the sum of all elements of $S$?

I could prove it easily by induction in the case of $k=1$ and I checked it for some low powers for example $9,25,27$. I think that this is true but I don't know how to manage a proof for $k\geq 2$ or find a counterexample. Maybe this is related to the Euler's totient function $\varphi$.

Any comment or sugerence will be appreciated. Thanks!

  • $\begingroup$ Can you give an example of $S$ for some $p^k$? I'm having trouble understanding its construction. $\endgroup$ – Carl Schildkraut Jun 30 at 2:50
  • $\begingroup$ For example for 9, $S=\{2,4,8\}$, 2+4+8=14. In this case 6=2+4, 10=8+2, 12=4+8. $\endgroup$ – Ale Tolcachier Jun 30 at 2:52
  • $\begingroup$ @AleTolcachier Is $p^k$ the upper bound for the elements in $S$ ? $\endgroup$ – Peter Jun 30 at 22:34
  • $\begingroup$ If you mean the last element in $S$, then yes, the last element is $p^k-1$ so $p^k$ is "the" upper bound $\endgroup$ – Ale Tolcachier Jun 30 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.