Every residue modulo a prime as a product of two smaller primes
Let $p$ be a large prime and $A$ the set of primes less than $p$. Walker showed that every nonzero residue is a product of at most $6$ elements of $A$, Shparlinski lowered $6$ to $5$, and for products of exactly $k$ primes Matomäki and Teräväinen reached $k = 3$.
Problem. Is every $x \in \{1, \dots, p - 1\}$ congruent modulo $p$ to a product $a_1 a_2$ with $a_1, a_2 \in A$?
Source: P. Erdős, A. M. Odlyzko and A. Sárközy, On the residues of products of prime numbers, Period. Math. Hungar. 18 (1987). Listed as Problem 62 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- NT — Number Theory
- Keywords
- multiplicative number theory, primes in residue classes, products of primes
References
@article{erdos1987residues,
author = {Erd{\H o}s, P. and Odlyzko, A. M. and S{\'a}rk{\"o}zy, A.},
title = {On the residues of products of prime numbers},
journal = {Periodica Mathematica Hungarica},
volume = {18},
number = {3},
pages = {229--239},
year = {1987},
doi = {10.1007/BF01848086}
}
@article{walker2016schnirelmann,
author = {Walker, Aled},
title = {A multiplicative analogue of {S}chnirelmann's theorem},
journal = {Bulletin of the London Mathematical Society},
volume = {48},
number = {6},
pages = {1018--1028},
year = {2016},
doi = {10.1112/blms/bdw062}
}
@article{shparlinski2019short,
author = {Shparlinski, Igor E.},
title = {On short products of primes in arithmetic progressions},
journal = {Proceedings of the American Mathematical Society},
volume = {147},
number = {3},
pages = {977--986},
year = {2019},
doi = {10.1090/proc/14289}
}
@article{matomaki2024products,
author = {Matom{\"a}ki, Kaisa and Ter{\"a}v{\"a}inen, Joni},
title = {Products of primes in arithmetic progressions},
journal = {Journal f{\"u}r die reine und angewandte Mathematik},
year = {2024},
doi = {10.1515/crelle-2023-0096}
}
@misc{banks2026primepower,
author = {Banks, William and Shparlinski, Igor E.},
title = {On the {E}rd{\H o}s--{O}dlyzko--{S}{\'a}rk{\"o}zy conjecture for prime-power moduli},
year = {2026},
eprint = {2610.19597},
archivePrefix = {arXiv},
note = {Prime-power moduli: three-prime representations with one small prime, and two primes for almost all classes, unconditionally; conditional analogues for general moduli}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 62; version of January 2026, most recent update December 2025},
year = {2026}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01039, "Every residue modulo a prime as a product of two smaller primes", clopen.solutions.