we-solve (beta)

Math-5608 · mathematics · Mathematics

Erdős Problem #368

Status Open · erdosproblems.comLLM status Open unverified

Statement

Let \[ F(n) := \max\{p:\ p\text{ prime and }p\mid n(n+1)\}, \] the largest prime divisor of $n(n+1)$.

The prompt asks "How large is $F(n)$?" and then records several known results (e.g. $F(n)\to\infty$, lower bounds, and conjectures).

Ambiguity / minimal correction. "How large" is not a proposition. A precise mathematical statement explicitly present in the prompt is:

(*) $F(n)\to\infty$ as $n\to\infty$.

I will give a complete proof of (*) using Størmer's theorem on consecutive smooth numbers.

Restatement from Math-5608-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 3

Math-5608-A3 · No claim recorded · LLM-generated · gpt pro 5.4 ·

gpt pro 5.4 attempt on Math-5608

Erdős Problem #368 --- ROUND 2

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction.

Round-1 tried to prove the baseline statement $F(n)\to\infty$ by a self-contained Pell/Størmer argument, and it also overclaimed a full resolution of the original problem. The original problem, however, asks for quantitative size of $F(n)$ and remains open. Moreover, the round-1 self-contained proof has a real gap in the $p\ge 5$ part of its uniqueness lemma. So round-2 will replace that flawed subproof by a clean theorem-level citation and correct the overall status.

2) Round-1 FOUNDATION USED

I retain from round-1 only the valid reduction:
  • If $F(n)\le B$ and $S$ is the set of primes at most $B$, then both $n$ and $n+1$ are $S$-smooth.
I do not reuse the round-1 proof of the key Pell uniqueness lemma, because that is exactly where the gap occurs.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a precise external theorem of Størmer, in the form quoted by Klazar:

Størmer's theorem. If $S$ is a finite set of primes, then the equation \[ x-y=1 \] has only finitely many solutions in positive $S$-numbers; in fact at most $3^{|S|}$ such solutions.

This theorem exactly matches the round-1 reduction and removes the need for the flawed self-contained lemma.

4) ATTACK PLAN (ROUND-2)

The gap left after round-1 is now very precise:
  • round-1 reduced $F(n)\to\infty$ to finiteness of consecutive $S$-smooth pairs;
  • round-1 then attempted a self-contained proof of that finiteness, but the contradiction in the $p\ge 5$ case was not valid.
So I will keep the reduction and swap in Størmer's theorem as a black box with verified hypotheses.

Then I will explain why even the repaired statement $F(n)\to\infty$ is still much weaker than the original quantitative problem.

5) WORK (ROUND-2)

Let \[ F(n):=\max\{p : p\mbox{ prime and } p\mid n(n+1)\}. \] Fix a positive integer $B$, and let $S$ be the finite set of all primes $\le B$. Suppose that \[ F(n)\le B. \] Then every prime dividing $n(n+1)$ lies in $S$. Since any prime divisor of $n$ or $n+1$ also divides $n(n+1)$, it follows that both $n$ and $n+1$ are $S$-smooth.

Now apply Størmer's theorem: for a fixed finite set $S$, there are only finitely many pairs of consecutive positive $S$-smooth integers. Therefore, for this fixed $B$, there are only finitely many $n$ such that $F(n)\le B$.

Because $B$ was arbitrary, we conclude: for every $B$ there exists $N(B)$ such that \[ n\ge N(B)\quad\Longrightarrow\quad F(n)>B. \] This is exactly the definition of \[ F(n)\to\infty\qquad (n\to\infty). \] So the baseline statement is proved.

Why this does not solve the original Erdős problem. The original question is not merely whether $F(n)$ is unbounded, but how large it must be quantitatively. The current problem page records much stronger partial results, for example \[ F(n)\gg \frac{(\log\log n)^2}{\log\log\log n}, \] and also records the conjectural scale \[ F(n)\gg (\log n)^2. \] Round-2 proves none of these stronger quantitative statements. It only repairs the weakest baseline fact $F(n)\to\infty$.

Hence the correct global status is still unresolved.

6) ADVERSARIAL VERIFICATION

  • Hypothesis check for Størmer: the set $S=\{p\le B\}$ is finite, so the theorem applies.
  • Quantifier check: for each fixed $B$ there are only finitely many $n$ with $F(n)\le B$; this is exactly the statement $F(n)\to\infty$.
  • Gap check: the flawed round-1 Pell uniqueness lemma is no longer used anywhere.
  • Scope check: proving $F(n)\to\infty$ does not answer "how large is $F(n)$?" in the quantitative sense intended by the open problem.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

Round-2 repairs the proof of the baseline statement $F(n)\to\infty$ and corrects the round-1 overclaim. But the original quantitative Erdős problem remains open.

8) COMPLETION ESTIMATE

COMPLETION: 40%

9) REFERENCES

Go to contribution →

Math-5608-A1 · No claim recorded · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-5608

Erdős Problem 368: a repaired Størmer argument

Statement and outcome

Let $F(n)$ be the largest prime factor of $n(n+1)$. The question is to estimate its growth, including the conjectural uniform scale $(\log n)^2$. We prove the explicit counting statement \[ \#\{n\ge1:F(n)\le y\}\le3^{\pi(y)}, \tag{1} \] and hence $F(n)\to\infty$. We also extract an almost-everywhere lower bound from $1$. These do not settle the uniform quantitative question.

The previous GPT-5.2 proof mishandled the last binomial term in its Pell argument, and the GPT-Pro-5.4 revision replaced that argument with a theorem citation. We supply the missing divisibility reasoning and the Pell structure here. This is a reconstruction of Størmer's classical theorem, not a new result; see Klazar's exposition, https://kam.mff.cuni.cz/~klazar/stormer.pdf, Theorems 1--2.

The Pell lemma, with all index cases checked

For a fixed positive integer $d$, the equation $x^2-dy^2=1$ has at most one positive solution for which every prime dividing $y$ divides $d$. If $d$ is a square, factoring the left side proves that no positive solution exists. Otherwise suppose one exists, and let $a+b\sqrt d=\varepsilon>1$ be the smallest positive solution. Every positive solution $u=x+y\sqrt d$ is a power of $\varepsilon$: choose $j\ge0$ with $\varepsilon^j\le u<\varepsilon^{j+1}$. Then $v=u\varepsilon^{-j}$ has integer coefficients and norm one. If $v>1$, its coefficients \[ (v+v^{-1})/2,\qquad(v-v^{-1})/(2\sqrt d) \] are positive integers, and $v<\varepsilon$ contradicts minimality. Thus $v=1$.

Write $a_j+b_j\sqrt d=\varepsilon^j$. Expansion shows $b_r\mid b_{rs}$, and $b_j=b c_j$ where \[ c_j=\sum_{\substack{1\le \ell\le j\\\ell\ \mathrm{odd}}} \binom j\ell a^{j-\ell}b^{\ell-1}d^{(\ell-1)/2}. \tag{2} \] Suppose $b_j$ has only prime factors dividing $d$ and $j>1$. For a prime $p\mid j$, the divisor $c_p$ also has this property. Since $\gcd(a,d)=1$, reduction of $2$ modulo any prime $q\mid c_p$ shows $q=p$; thus $c_p$ is a power of $p$ and $p\mid d$.

If $p=2$, then $c_2=2a$, whose factor $a>1$ is coprime to $d$, a contradiction. If $p=3$, then \[ c_3=3a^2+b^2d=4a^2-1=(2a-1)(2a+1). \] The two odd factors are coprime and greater than one, so cannot both be powers of $3$. If $p\ge5$, every term after the first in $2$ is divisible by $p^2$. For $3\le\ell<p$, the binomial coefficient supplies one $p$ and the positive power of $d$ another. For the final term $\ell=p$, the binomial coefficient is $1$, but $d^{(p-1)/2}$ itself supplies $p^2$. This is the missing endpoint check in the inherited proof. Consequently \[ c_p\equiv p a^{p-1}\not\equiv0\pmod{p^2}. \] Since $c_p$ is a power of $p$, it must equal $p$, whereas its positive first term is $p a^{p-1}>p$. Contradiction. Thus $j=1$, proving the lemma.

Finitely many smooth consecutive pairs

Fix a finite prime set $S$ with $r$ members. If $n,n+1$ have all prime factors in $S$, then $2\in S$ and $(2n+1)^2-1=4n(n+1)$ is also $S$-smooth. In each prime exponent $e$ of this last integer, retain exponent $0$ if $e=0$, exponent $1$ if $e$ is odd, and exponent $2$ if $e>0$ is even. The remaining exponent is nonnegative and even. Hence \[ (2n+1)^2-dy^2=1, \] where $d$ has each prime exponent in $\{0,1,2\}$, and every prime of $y$ divides $d$. There are at most $3^r$ possible $d$, and the Pell lemma supplies at most one pair for each. This proves $1$ on taking $S=\{p:p\le y\}$. For each fixed $y$ only finitely many $n$ have $F(n)\le y$, which is precisely the claimed limit.

A density consequence and the remaining gap

Fix $0<c<1/\log3$ and put $y=c\log X\log\log X$. Using the prime number theorem $\pi(y)\sim y/\log y$ as an explicit external standard input, $1$ gives \[ \#\{n\le X:F(n)\le c\log X\log\log X\} \le X^{c\log3+o(1)}=o(X). \] Thus this lower scale holds for almost all $n\le X$. The estimate does not constrain the size of the largest exceptional $n$ for a fixed $y$; it cannot be inverted into that same lower bound for every $n$. The stronger uniform bounds and conjectures on the current page, https://www.erdosproblems.com/368, remain unresolved in this attempt. In particular neither the proposed $(\log n)^2$ uniform lower bound nor infinitely many values below $(\log n)^{2+\epsilon}$ is proved. Completion rate estimate: 40%.

Go to contribution →

Math-5608-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-5608

Problem 368: Largest prime factor of $n(n+1)$

FORMAL RESTATEMENT

Let \[ F(n) := \max\{p:\ p\text{ prime and }p\mid n(n+1)\}, \] the largest prime divisor of $n(n+1)$.

The prompt asks "How large is $F(n)$?" and then records several known results (e.g. $F(n)\to\infty$, lower bounds, and conjectures).

Ambiguity / minimal correction. "How large" is not a proposition. A precise mathematical statement explicitly present in the prompt is:

(*) $F(n)\to\infty$ as $n\to\infty$.

I will give a complete proof of (*) using Størmer's theorem on consecutive smooth numbers.

QUICK LITERATURE/CONTEXT CHECK

The Erdős-problems page for #368 attributes $F(n)\to\infty$ to Pólya $1918$ and also notes Størmer's earlier work. A standard effective route is Størmer's theorem $1897$ that for any finite set of primes $S$, there are only finitely many pairs of consecutive $S$-smooth integers; an expository proof is given by M. Klazar $2010$ via Pell equations.

ATTACK PLAN

  1. Fix a bound $B$ and let $S$ be the set of primes $\le B$.
  2. Show: if $F(n)\le B$ then both $n$ and $n+1$ are $S$-smooth (all prime factors in $S$).
  3. Apply Størmer's theorem to conclude there are only finitely many such $n$.
  4. Conclude: for each fixed $B$ there exists $N(B)$ such that $n\ge N(B)\Rightarrow F(n)>B$, i.e. $F(n)\to\infty$.

WORK (complete proof of (*))

1. Smooth numbers and reduction to Størmer

Let $S$ be a finite set of primes. Call a positive integer $S$-smooth if all its prime factors lie in $S$.
Observation 1.1.
If $F(n)\le B$ and $S:=\{p\text{ prime}:p\le B\}$, then both $n$ and $n+1$ are $S$-smooth.
Proof: If $F(n)\le B$ then every prime dividing $n(n+1)$ is $\le B$, hence lies in $S$. Since $\gcd(n,n+1)=1$, any prime dividing $n$ (resp. $n+1$) also divides $n(n+1)$, so it lies in $S$. ∎

Thus, to prove $F(n)\to\infty$, it suffices to show:

Claim. For each finite set of primes $S$, there are only finitely many $n$ such that both $n$ and $n+1$ are $S$-smooth.

This is (a special case of) Størmer's theorem. We now prove it.

2. A key finiteness lemma for Pell equations

For $d\in\mathbb{N}$, consider the Pell equation \[ x^2-dy^2=1. \tag{Pell}_d \] Say that $y$ is a $d$-number if every prime factor of $y$ divides $d$.
Lemma 2.1 (structure of Pell solutions).
Assume $d$ is not a perfect square and $(\mathrm{Pell})_d$ has at least one positive integer solution. Let $(a_1,b_1)$ be the fundamental solution, i.e. the solution with $a_1>1$ minimal. Then every positive solution $(a_n,b_n)$ is given by \[ a_n+b_n\sqrt d = (a_1+b_1\sqrt d)^n\qquad(n\ge 1), \] and conversely each $n\ge 1$ produces a positive solution.
Proof: Work in the quadratic ring $\mathbb{Z}[\sqrt d]$. If $(x,y)$ solves $(\mathrm{Pell})_d$, then $u:=x+y\sqrt d$ satisfies $N(u)=u\,\overline u=x^2-dy^2=1$, so $u$ is a unit of norm $1$. If $u=x+y\sqrt d$ and $u'=x'+y'\sqrt d$ both have norm $1$, then $uu'$ also has norm $1$, and its coefficients are integers, so solutions form a multiplicative group.

Let $\varepsilon:=a_1+b_1\sqrt d>1$. Then $\varepsilon^n$ has norm $1$ and equals $a_n+b_n\sqrt d$ with integers $a_n,b_n$ (by repeated multiplication), so each $n$ yields a solution.

Conversely, let $u=x+y\sqrt d>1$ be any solution. Choose $n\in\mathbb{Z}$ such that $\varepsilon^n\le u<\varepsilon^{n+1}$. Then $v:=u/\varepsilon^n$ is again a unit of norm $1$, and satisfies $1\le v<\varepsilon$. Writing $v=r+s\sqrt d$ with $r,s\in\mathbb{Z}$ (closure under multiplication and inversion in this unit group), the inequalities $1\le v<\varepsilon$ force $s=0$ and $r=1$ (since $|r-s\sqrt d|=|\overline v|=1/v\le 1$ and $r,s$ are integers). Hence $v=1$ and $u=\varepsilon^n$. Therefore every solution is a power of the fundamental unit. ∎

Lemma 2.2 (Størmer's Pell finiteness).
For fixed $d\in\mathbb{N}$, the Pell equation $(\mathrm{Pell})_d$ has at most one positive integer solution $(x,y)$ for which $y$ is a $d$-number.
Proof: If $(\mathrm{Pell})_d$ has no positive solutions, there is nothing to prove. Otherwise let $(a_1,b_1)$ be its fundamental solution and write all solutions as in Lemma 2.1. Suppose for some $m\ge 1$ the solution $(a_m,b_m)$ has $b_m$ a $d$-number. We will show $m=1$.

Step 1: basic coprimality. From $a_1^2-db_1^2=1$, any common divisor of $a_1$ and $d$ must divide $1$, so $\gcd(a_1,d)=1$ and in particular $a_1>1$.

Step 2: divisibility in the $b_n$ sequence. For $n=kl$ we have \[ a_{kl}+b_{kl}\sqrt d = (a_k+b_k\sqrt d)^l. \] Expanding the right-hand side by the binomial theorem, every term contributing to the $\sqrt d$-coefficient contains a factor $b_k$, so $b_k\mid b_{kl}$. In particular, taking $k=1$ shows $b_1\mid b_n$ for all $n$, so we may write \[ b_n=b_1c_n\qquad (c_n\in\mathbb{N}). \] Moreover, for any $l\ge 1$, dividing the binomial expansion for $(a_1+b_1\sqrt d)^l$ by $b_1$ yields the explicit identity \[ c_l = l a_1^{l-1} + \binom{l}{3} a_1^{l-3} b_1^2 d + \binom{l}{5} a_1^{l-5} b_1^4 d^2 + \cdots, \tag{1} \] a sum over odd indices.

Step 3: prime divisors of $m$ lead to contradiction. Assume for contradiction that $m>1$. Let $p$ be any prime divisor of $m$, and write $m=pr$. Then $b_p\mid b_m$, hence $c_p=b_p/b_1\mid b_m$. Since $b_m$ is a $d$-number, every prime factor of $c_p$ divides $d$, i.e. $c_p$ is a $d$-number. We now show this is impossible for any prime $p$.

Case $p=2$. From $1$ with $l=2$ we have $c_2=2a_1$. If $c_2$ is a $d$-number, every prime factor of $a_1$ divides $d$, contradicting $\gcd(a_1,d)=1$ unless $a_1=1$. But $a_1>1$, contradiction.

Case $p=3$. From $1$ with $l=3$ we get \[ c_3 = 3a_1^2 + b_1^2 d. \] Using $a_1^2-db_1^2=1$ we rewrite $b_1^2 d=a_1^2-1$, hence \[ c_3 = 4a_1^2-1=(2a_1-1)(2a_1+1). \] Let $q$ be any prime divisor of $c_3$. Since $c_3$ is a $d$-number, $q\mid d$. Reducing $c_3=3a_1^2+b_1^2d$ modulo $q$ gives $0\equiv 3a_1^2\pmod q$. As $\gcd(a_1,q)=1$ (because $q\mid d$ and $\gcd(a_1,d)=1$), we conclude $q=3$. So $c_3$ is a power of $3$, meaning both $2a_1-1$ and $2a_1+1$ are powers of $3$ differing by $2$. The only positive powers of $3$ differing by $2$ are $1$ and $3$, which forces $a_1=1$, contradiction.

Case $p\ge 5$. Let $q$ be any prime divisor of $c_p$. Again $c_p$ is a $d$-number, so $q\mid d$. Reduce identity $1$ modulo $q$ with $l=p$: all terms after the first contain a factor $d$, hence vanish modulo $q$, so \[ 0\equiv c_p \equiv p a_1^{p-1}\pmod q. \] Since $\gcd(a_1,q)=1$, this implies $q\mid p$, so $q=p$. Thus every prime factor of $c_p$ is $p$, so $c_p=p^r$ for some $r\ge 1$. In particular $p\mid c_p$, hence $p\mid d$. Now in $1$ with $l=p$, every term after the first is divisible by $p^2$ because it has a factor $d$ (hence $p$) and a binomial coefficient $\binom{p}{j}$ (hence $p$). Therefore $c_p > p a_1^{p-1}$ (since all summands are positive), and because $a_1\ge 2$ we have $p a_1^{p-1}\ge p\cdot 2^{p-1} > p$. So $c_p>p$, contradicting $c_p=p^r$ with $r=1$, and also contradicting $r\ge 2$ because then $c_p\ge p^2$ would force $p^2\mid p a_1^{p-1}$ and hence $p\mid a_1$, again contradicting $\gcd(a_1,d)=1$.

In all cases we obtain a contradiction, so $m$ has no prime divisors, hence $m=1$. Thus the only solution with $y$ a $d$-number is the fundamental one, proving uniqueness. ∎

3. Størmer's theorem for consecutive $S$-smooth integers

Theorem 3.1 (Størmer; difference $1$ case).
Let $S=\{p_1,\dots,p_r\}$ be a finite set of primes. Then the equation \[ x-y=1 \] has only finitely many solutions in positive $S$-smooth integers $x,y$. In fact, there are at most $3^r$ such solutions.
Proof: If $2\notin S$, then every $S$-smooth integer is odd, so no two can differ by $1$. So assume $2\in S$.

Let $y$ be $S$-smooth and set $a:=2y+1$. If also $y+1$ is $S$-smooth then $4y(y+1)$ is $S$-smooth, and \[ 4y(y+1)=(2y+1)^2-1=a^2-1. \] So it suffices to bound the number of $S$-smooth integers of the form $a^2-1$.

Write $a^2-1=\prod_{i=1}^r p_i^{e_i}$. Define integers $b_i\ge 0$ by:

  • if $e_i$ is odd, set $b_i:=e_i-1$ (so $e_i-b_i=1$);
  • if $e_i\in\{0,2\}$, set $b_i:=0$ (so $e_i-b_i\in\{0,2\}$);
  • if $e_i\ge 4$ is even, set $b_i:=e_i-2$ (so $e_i-b_i=2$).
Then set \[ d:=\prod_{i=1}^r p_i^{e_i-b_i},\qquad b:=\prod_{i=1}^r p_i^{b_i/2}. \] By construction, $e_i-b_i\in\{0,1,2\}$, so there are at most $3^r$ possible values of $d$. Also $a^2-1=db^2$, i.e. $a^2-d b^2=1$, and whenever $b_i>0$ we have $e_i-b_i=2$, so $p_i\mid d$. Thus every prime dividing $b$ divides $d$, i.e. $b$ is a $d$-number.

For each fixed $d$, Lemma 2.2 shows there is at most one positive solution $(a,b)$ to $a^2-d b^2=1$ with $b$ a $d$-number. Hence there are at most $3^r$ possible values of $a$, and therefore at most $3^r$ possible values of $y=(a-1)/2$. This proves finiteness. ∎

4. Proof that $F(n)\to\infty$

Fix $B\ge 2$ and set $S:=\{p\text{ prime}:p\le B\}$. If $F(n)\le B$, Observation 1.1 implies $n$ and $n+1$ are both $S$-smooth. By Theorem 3.1, there are only finitely many such $n$. Therefore for each $B$ there exists $N(B)$ such that $n\ge N(B)\Rightarrow F(n)>B$. This is exactly the statement that $F(n)\to\infty$ as $n\to\infty$.

VERIFICATION

  • The reduction $F(n)\le B\Rightarrow n,n+1\text{ are }S\text{-smooth}$ used only $\gcd(n,n+1)=1$.
  • Lemma 2.2 was proved by contradiction using only integer divisibility and the explicit binomial expansion identity $1$.
  • The final quantifier structure matches the limit definition: for each fixed $B$ only finitely many exceptions.

META-CHECK (common failure modes)

  • Confusing "unbounded" with "tends to infinity": we proved the stronger statement "for each $B$ only finitely many $n$ have $F(n)\le B$", which implies $F(n)\to\infty$.
  • Hidden use of deep theorems: the argument uses only Pell-equation structure and elementary divisibility (no Baker theory, etc.).
  • Ring issues for Pell: we only used closure of $\mathbb{Z}[\sqrt d]$ under multiplication and the norm map.

FINAL

FINAL: LABEL: FULL SOLUTION   SUBLABEL: FULL PROOF.

COMPLETION ESTIMATE

COMPLETION ESTIMATE: 100%.

Bibliographic pointers (non-exhaustive)

References

  • [KlazarStormer] M. Klazar, Størmer's solution of the unit equation $x-y=1$, 2010,
    https://kam.mff.cuni.cz/~klazar/stormer.pdf.
  • [Polya1918] G. Pólya, Zur arithmetischen Untersuchung der Polynome, Math. Z. 1 $1918$, 143--148.
  • [OEISA060355] OEIS Foundation, A060355: Numbers $k$ such that $k$ and $k+1$ are powerful,
    https://oeis.org/A060355.
  • [OEISA074399] OEIS Foundation, A074399: $a(n)$ is the largest prime divisor of $n(n+1)$,
    https://oeis.org/A074399.

Go to contribution →

Reviews 1

Historical problem-level reviews keep their original scope; they do not assess every contribution.