An addition theorem on the integers modulo \(n\) (Q1119963): Difference between revisions

The authors prove the following theorem: Given any positive integer \(d\) and integers \(a_ 1,...,a_ d\), there exists a non-empty subset \(Q\) of \([1,d]\) such that \(d\mid \sum_{i\in Q}a_ i\) and \(\sum_{i\in Q}\gcd (a_ i,d)\leq d\). A corollary of this result is the conjecture of Erdős-Lemke that given any positive integers \(n,d\) and \(a_ 1,...,a_ d\) with \(d\mid n\) and \(a_ i \mid n\), \(i=1,...,d\), there is a non-empty subset \(S\) of \([1,d]\) such that \(d\mid \sum_{i\in S} a_ i\) and \(\sum_{i\in S}a_ i\leq n\). Some related open questions are also described.