Problem 541

Let $a_1,\ldots,a_p$ be (not necessarily distinct) residues modulo $p$ , such that there exists some $r$ so that if $S\subseteq [p]$ is non-empty and

\sum_{i\in S}a_i\equiv 0\pmod{p}

then $\lvert S\rvert=r$ . Must there be at most two distinct residues amongst the $a_i$ ?

Source: erdosproblems.com/541

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site's label is PROVED (LEAN). Gao, Hamidoune and Wang's Theorem 1.1 (J. Number Theory 2010, refereed): a sequence of $n$ integers in $[0,n-1]$ taking at least three distinct values has two nonempty zero-sum subsequences modulo $n$ of distinct lengths. Read contrapositively with $n=p$ (an authored one-line deduction, below), it gives the site's statement for every prime, and indeed for every modulus. Erdős and Szemerédi proved the conjecture for all sufficiently large primes in 1976, for nonzero residues, by a longer argument. The site's (LEAN) suffix refers to the Lean proof described under Formalization and the Lean label below. The claim pages Gao, Hamidoune and Wang 2009 and Grynkiewicz 2009 record the accepted proofs, Erdős and Szemerédi 1976 the accepted partial claim for large primes, and Alexeev's Lean proof of 2025 the accepted formal proof for every prime, built and audited by this corpus; the frontmatter standing derives from them.

GHW10: Gao, W., Hamidoune, Y. O. and Wang, G., Distinct length modular zero-sum subsequences: a proof of Graham's conjecture. J. Number Theory 130 (2010), no. 6, 1425--1431, DOI 10.1016/j.jnt.2009.11.012; arXiv:0902.4758v1 (27 February 2009, the first posting, with the theorem in its abstract); Theorem 1.1, p. 2 of an author preprint dated January 2010, a later version than the arXiv posting (the journal text not compared). Library home: Gao and Wang 2010.
ErSz76: Erdős, P. and Szemerédi, E., On a problem of Graham. Publ. Math. Debrecen 23 (1976), no. 1--2, 123--127, DOI 10.5486/pmd.1976.23.1-2.20 (the byline prints "E. Erdős" [sic]); the conjecture and Theorem 1, p. 123. Library home: Erdős and Szemerédi 1976.
Gr11: Grynkiewicz, D. J., Note on a conjecture of Graham. European J. Combin. 32 (2011), no. 8, 1336--1344, DOI 10.1016/j.ejc.2011.06.004; arXiv:0903.3200v1 (18 March 2009, the only arXiv version). Theorem 3.4, p. 5 of the preprint. Library home: Grynkiewicz 2011 (the card carries the row for this problem). Cited in the thread (14 April 2026) as an easy proof of the Erdős--Szemerédi theorem from the Cauchy--Davenport theorem and the pigeonhole principle (Crossref record of 2026-09-18).
Er73: Erdős, P., Problems and results on combinatorial number theory (1973), 117--138; printed p. 126. Library home: Erdos 1973.
Er80: Erdős, P., A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; printed p. 112. Library home: Erdos 1980.
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980); printed p. 95. Library home: Erdős and Graham 1980.

Problem 541

Status

Proof claims

Discussion