Ulas: A note on Erdős–Straus and Erdős–Graham divisibility problems (with an appendix by Andrzej Schinzel)

../

table_2: The least k with (n+1)...(n+k) | (n+k+1)...(n+2k) for n <= 16, and a solution not checked to be least for 17 <= n <= 20: witnesses for Problem 389 at each n from 2 to 21.

table_4: The least k > n with k(k-1)...(k-n) | C(2k, k) for n <= 9, from a search up to 2^30; the rows n = 2 to 9 are Problem 396's least witnesses for its k = 2 to 9, and the rows n = 0 and 1 are not least.

theorem_2_1: For positive n and k, (n+1)...(n+k) divides (n+k+1)...(n+2k) exactly when every prime p dividing (k+1)...(k+n) has 2s_p(k+n) - s_p(2k+n) - s_p(n) >= 0, where s_p is the base-p digit sum.

theorem_2_2: Infinitely many k = pq - 1, with p and q primes and 3p/2 < q < 2p, have k + 1 dividing C(2k+1, k), and k - 1 then solves the case n = 2, so Problem 389 has infinitely many solutions at its n = 2 and n = 3.

theorem_2_7: For every positive n, infinitely many k fail the Erdős–Straus divisibility: k = 2p^m - n, with p a prime above n and at least 5, violates the digit-sum criterion at p.

theorem_3_1: For integers n >= 0 and k > n, k(k-1)...(k-n) divides C(2k, k) exactly when every prime p dividing that product has 3s_p(k) - s_p(2k) - s_p(k-n-1) >= n + 1, where s_p is the base-p digit sum.

theorem_3_2: Every k in S_1 gives k + 1 dividing C(2k+2, k+1), so infinitely many k divide C(2k, k); Corollary 3.3 restates this as k dividing the Catalan number C_k for infinitely many k.

theorem_3_4: For every n >= 0, infinitely many k fail k(k-1)...(k-n) | C(2k, k): each power of 2 that is at least 4 and exceeds n + 1 violates the digit-sum criterion at 2.

theorem_a_1: For f(x) = ax + b with a > 1 and gcd(a, b) = 1, each n has only finitely many k with f(n+1)...f(n+k) | f(n+k+1)...f(n+2k); the printed choice of prime needs a small repair when n >= 1.

theorem_a_2: States that for gcd(a, b) = 1 and every n infinitely many k have (ak+b)^n | C(2k, k); the printed proof omits the factor p - 1 of Legendre's formula, so it establishes only the exponent one, and not even that when a = 2 and b > 0.

---

M. Ulas, A note on Erdős–Straus and Erdős–Graham divisibility problems (with an appendix by Andrzej Schinzel), International Journal of Number Theory 9 (2013), no. 3, 583–599, DOI. The first page names Maciej Ulas and Andrzej Schinzel as authors, and the running heads read "M. Ulas & A. Schinzel". Appendix A (pp. 597–598) is headed as Schinzel's, and the acknowledgments (p. 597) call it his note, included with his permission; the rest of the paper is Ulas's. The first page records receipt on 2012-01-17, acceptance on 2012-09-05 and publication on 2013-01-25.

The copy read for this card is the publisher's PDF of the published article: 17 pages, printed pp. 583–599 = PDF pp. 1–17. Provenance: the publisher's site, https://www.worldscientific.com, which the download stamp names. The file prints "© World Scientific Publishing Company" on its first page and, at the end of the publisher's download stamp in the left margin of every page, "Re-use and distribution is strictly not permitted, except for Open Access articles.", every other right reserved; it names no open license. In the copy read, the network address of the downloading connection, which the stamp printed, is blanked, and the rest of the stamp is kept as printed.

Read status: claims checked. Questions 1.1 and 1.2 (p. 584), Theorem 2.1 (p. 585), Theorem 2.2 (p. 586), Theorem 2.7 (p. 589), Table 2 with its account of the search (p. 590), Conjectures 2.9–2.11 (p. 591), Theorems 3.1 and 3.2 (p. 592), Table 4, Corollary 3.3 and Theorem 3.4 (p. 593), the search account of p. 594, Table 5 and Conjectures 3.5, 3.6 and 3.8 (pp. 593–595), Theorem 4.3 (p. 596) and Theorems A.1 and A.2 with Remark A.3 (pp. 597–598) were read clause by clause on the page images. The proofs of the theorems that have result pages were followed on the page images to write the sketches there; that reading found the slips the pages record, among them a gap in the printed proof of Theorem A.2. No table entry was recomputed and no search was rerun. Nothing here is independently reviewed.

The two questions. Question 1.1 (p. 584), which the paper credits to Erdős and Straus, asks whether every positive integer $n$ has a positive integer $k$ with

$$(n+1)(n+2)\cdots(n+k)\mid(n+k+1)(n+k+2)\cdots(n+2k).$$

Question 1.2 (p. 584), credited to Erdős and Graham, asks whether every nonnegative integer $n$ has an integer $k$ with $k(k-1)\cdots(k-n)\mid\binom{2k}{k}$. The paper takes both from pp. 75 and 76 of Erdős and Graham's 1980 problem book. It writes $S_n$ for the set of positive $k$ answering Question 1.1 for $n$ and $k_n$ for its least element (p. 585), and $Z_n$ for the set of $k>n$ answering Question 1.2 for $n$ and $z_n$ for its least element (p. 592), so that $Z_0\supset Z_1\supset\cdots$. Question 1.1 at $n$ is Problem 389 at $n+1$, and Question 1.2 is Problem 396 with its two letters exchanged.

Method. Legendre's formula turns each divisibility into inequalities between base-$p$ digit sums, one for each prime $p$ dividing the left side: Theorem 2.1 for Question 1.1 and Theorem 3.1 for Question 1.2. The searches test these inequalities prime by prime instead of computing binomial coefficients (pp. 589–590 and 594).

Question 1.1. Theorem 2.2 shows that $S_1$ is infinite and that $S_1-1\subset S_2$. Propositions 2.4 and 2.5 (pp. 587–588) show that every element of $S_2\setminus(S_1-1)$ is even and every element of $S_4\setminus(S_3-1)$ is $0$ or $1$ modulo $4$. Theorem 2.7 shows that infinitely many $k$ lie outside each $S_n$. Table 2 reports $k_n$ for $n\le16$ and, for $17\le n\le20$, an element of $S_n$ not checked to be the least, and Table 3 (p. 591) counts $S_n\cap[1,2^i]$ for $n\le10$ and $i\le26$. The paper conjectures that every $S_n$ is nonempty (Conjecture 2.9), that a nonempty $S_n$ is infinite (Conjecture 2.10) and that $k_{2n-1}-1\in S_{2n}$ (Conjecture 2.11), and asks how $|S_n\cap[1,x]|$ grows (Question 2.8).

Question 1.2. Theorem 3.2 shows that $S_1+1\subset Z_0$, so infinitely many $k$ divide $\binom{2k}{k}$, and Corollary 3.3 (p. 593) that $k$ divides the Catalan number $C_k$ for infinitely many $k$. Theorem 3.4 shows that infinitely many $k$ lie outside each $Z_n$. Table 4 reports $z_n$ for $n\le9$ from a search up to $2^{30}$; p. 594 lists the 25 elements of $Z_7$ up to $2^{30}$ and the four of them in $Z_8$, and reports one in $Z_9$; and Table 5 counts $Z_n\cap[1,2^i]$ for $n\le6$. Conjectures 3.5 and 3.6 (p. 595) mirror Conjectures 2.9 and 2.10. Conjecture 3.8 (p. 595) links the two questions: $z_n-(2n+1)\in S_{2n+1}$. The paper used it to find the rows $17\le n\le20$ of Table 2, and notes that the same shift fails for other elements of $Z_n$, for instance $20\in Z_0$ while $19\notin S_1$.

Section 4 and the appendix. Section 4 generalizes both questions to a polynomial $f_A$ with positive leading coefficient. Question 4.1 asks for $k$ with $f_A(n+1)\cdots f_A(n+k)\mid f_A(n+k+1)\cdots f_A(n+2k)$; Questions 4.2, 4.4 and 4.5 ask when $f_A(k)\mid\binom{2k}{k}$ has a solution $k$, or infinitely many; and Theorem 4.3 (p. 596) gives the digit-sum criterion for $f_A(k)\mid\binom{2k}{k}$. For $f_A(x)=2x-1$ and $n=1$, Question 4.1 has no solution (pp. 595–596). Schinzel's appendix takes $f(x)=ax+b$ with $\gcd(a,b)=1$. Theorem A.1 shows that for $a\ge2$ each $n$ has only finitely many solutions of the analogue of Question 1.1. Theorem A.2 states that for every $n$ infinitely many $k$ have $(ak+b)^n\mid\binom{2k}{k}$; its printed proof establishes only the exponent one, and in the case $a=2$, $b>0$ not even that.

Source notes. The result pages state each point of the print that needs care; none is an author erratum. Theorems 2.1 and 3.1 are worded as "there exists an integer $k>n$ such that" one condition holds "if and only if" another does, with $k$ free in the second, and are proved and used as criteria for a given $k$. The proof of Theorem 2.2(2) ends with a misprinted binomial coefficient, and the proof of Theorem 2.7 with a misprinted value and a choice of prime that needs $p\ge5$; neither affects the theorem. Table 4's rows for $n=0$ and $n=1$ are not the least elements of $Z_0$ and $Z_1$ under the paper's own definition. The proof of Theorem A.1 needs its prime above $((2k+n)a+b)/(a+1)$ rather than $(2ka+b)/(a+1)$, a repair that costs nothing for fixed $n$. The proof of Theorem A.2 compares $2s_p(k)-s_p(2k)$ with the exponent without the factor $p-1$ that Legendre's formula and the paper's own Theorem 4.3 carry.

Bears on. #389: the problem at $n+1$ is Question 1.1 at $n$, and its $n=1$ is trivial, since $k!$ divides $(k+1)\cdots(2k)$. Table 2 (p. 590) reports a witness $k$ for each of the problem's $n$ from $2$ to $21$, the least one for $n\le17$. Theorem 2.2 (p. 586) gives infinitely many $k$ for the problem's $n=2$ and $n=3$, and Theorem 2.7 (p. 589) infinitely many failing $k$ for each $n\ge2$. Conjecture 2.9 (p. 591) is the problem's affirmative answer, and Conjecture 2.10 predicts infinitely many $k$ wherever one exists. Schinzel's Theorem A.1 (p. 597) shows that the analogue along a progression $ax+b$ with $a\ge2$ has only finitely many $k$ for each $n$. Nothing in the paper reaches the problem's $n\ge22$.

#396: the problem's $k$ and $n$ are the paper's $n$ and $k$. Table 4 (p. 593) reports, from a search up to $2^{30}$, the least witness for each of the problem's $k$ from $2$ to $9$. These eight values are the terms $a(2)$ to $a(9)$ of the OEIS entry A375077 that the problem's claim pages record and credit to contributors from 2024 to 2026; the paper printed them in 2013. Its rows for $k=0$ and $k=1$ are not least under the paper's definition, as the Table 4 page explains. Theorem 3.2 (p. 592) gives infinitely many $n$ for $k=0$, Theorem 3.4 (p. 593) infinitely many failing $n$ for each $k$, and Conjecture 3.5 (p. 595) is the problem's affirmative answer for $k\ge1$. Schinzel's Theorem A.2 (p. 597) concerns a power of one linear factor and settles no instance with $k\ge1$.

Results.

• Theorem 2.1 (p. 585): the digit-sum criterion for $k\in S_n$.
• Theorem 2.2 (p. 586): $S_1$ and $S_2$ are infinite.
• Theorem 2.7 (p. 589): infinitely many $k$ lie outside each $S_n$.
• Table 2 (p. 590): $k_n$ for $n\le20$, the last four rows not checked to be least.
• Theorem 3.1 (p. 592): the digit-sum criterion for $k\in Z_n$.
• Theorem 3.2 (p. 592): $S_1+1\subset Z_0$, with Corollary 3.3 on Catalan numbers.
• Theorem 3.4 (p. 593): infinitely many $k$ lie outside each $Z_n$.
• Table 4 (p. 593): $z_n$ for $n\le9$.
• Theorem A.1 (p. 597): finitely many solutions along a progression with $a\ge2$.
• Theorem A.2 (pp. 597–598): powers of $ak+b$ dividing $\binom{2k}{k}$, with the gap in its printed proof.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.