Erdős Problem #770

Problem 770 (Round 2)

1. ROUND-2 OBJECTIVE

Path (C): repair the only real Round-1 gap, and then push the structure of $h(n)$ substantially further.

Round 1 already established the useful characterization \[ h(n)=n+1 \iff n+1 \text{ is prime}, \] but the Round-1 proof that $h(n)$ is unbounded on odd $n$ had a gap: it intersected two prime conditions without proving that the intersection is infinite. The most promising Round-2 strategy is therefore:

1. first, repair that gap cleanly with one Chebotarev argument;
2. second, look for a new structural theorem about the values of $h(n)$ themselves.

That second step succeeds: $h(n)$ is always prime.

2. Round-1 FOUNDATION USED

I use the following Round-1 results.

1. The definition \[ h(n)=\min\left\{m\ge 2:\ \gcd(2^n-1,3^n-1,\dots,m^n-1)=1\right\}. \]
2. The Round-1 theorem \[ h(n)=n+1 \iff n+1 \text{ is prime}. \]

I also explicitly identify a flaw in the Round-1 proof of odd unboundedness and replace it by a correct proof.

3. NEW INSIGHT / TOOL (ROUND 2)

There are two new ideas.

1. Subgroup closure forces primality of $h(n)$. If $m=h(n)$ and a prime $p$ divides the gcd up to $m-1$, then the residues \[ 1,2,\dots,m-1 \] all lie in the subgroup of $n$th roots of unity modulo $p$. If $m$ were composite, then $m=ab$ with $2\le a,b\le m-1$, so subgroup closure would force $m$ itself to be an $n$th root, contradicting the minimality of $m$. Thus $h(n)$ is always prime.

2. The odd-$n$ argument should live in a single Galois extension. To force simultaneously \[ q\equiv 3\pmod 4 \qquad\text{and}\qquad 2,3,\dots,M \text{ all quadratic residues mod } q, \] one should work in the compositum \[ L_M=\mathbb Q(\sqrt 2,\sqrt 3,\dots,\sqrt M,i) \] and choose a Frobenius element that is trivial on the totally real part and nontrivial on $i$. Chebotarev then gives infinitely many such primes, indeed with positive density.

4. ATTACK PLAN (ROUND 2)

The exact Round-1 gaps were:

1. no structural theorem about the values of $h(n)$;
2. one missing justification in the odd-unboundedness proof.

I now prove three new statements.

1. For every $n\ge 1$, the integer $h(n)$ is prime.
2. For every $n\ge 1$, one has $h(n)\le n+1$.
3. For every fixed $M\ge 2$, the number of odd integers $n\le x$ with $h(n)>M$ is \[ \gg_M \frac{x}{\log x}. \] In particular, $h(n)$ is unbounded on odd $n$.

Statement $3$ repairs and strengthens the Round-1 odd-unboundedness claim.

5. WORK (ROUND 2)

For convenience write \[ g_m(n):=\gcd(2^n-1,3^n-1,\dots,m^n-1). \]

Theorem 1.

For every integer $n\ge 1$, the value $h(n)$ is prime.

Proof.

Set \[ m:=h(n). \] Then \[ g_{m-1}(n)>1 \qquad\text{and}\qquad g_m(n)=1. \] Choose a prime \[ p\mid g_{m-1}(n). \] Then \[ p\mid a^n-1 \qquad\text{for every } a=2,3,\dots,m-1. \] I claim that \[ p>m-1. \] Indeed, if $p\le m-1$, then taking $a=p$ gives \[ p^n-1\equiv -1\pmod p, \] contradicting $p\mid p^n-1$.

Now suppose, for contradiction, that $m$ is composite. Then we can write \[ m=ab \] with \[ 2\le a,b\le m-1. \] Since $p>m-1$, we actually have $p>m$ (because $p$ is prime while $m$ is composite), so the congruence class of $m$ modulo $p$ is represented by the ordinary integer $m$.

Let \[ H:=\{x\in \mathbb F_p^\times : x^n=1\}. \] This is a multiplicative subgroup of $\mathbb F_p^\times$. By choice of $p$, the residues of \[ 1,2,\dots,m-1 \] all belong to $H$. In particular, $a,b\in H$. Since $H$ is closed under multiplication, \[ m=ab\in H. \] Therefore \[ m^n\equiv 1\pmod p, \] so \[ p\mid m^n-1. \] But $p$ already divides $g_{m-1}(n)$, hence it divides $g_m(n)$, contradicting $g_m(n)=1$.

Therefore $m$ cannot be composite. So $h(n)=m$ is prime. $\square$

Corollary 2.

For every $n\ge 1$, \[ h(n)\le n+1. \]

Proof.

If $g_n(n)=1$, then by definition $h(n)\le n$. So suppose $g_n(n)>1$, and choose a prime $p\mid g_n(n)$. Exactly as above, $p>n$. Hence the residues \[ 1,2,\dots,n \] are $n$ distinct roots of the polynomial $X^n-1$ in $\mathbb F_p$. A degree-$n$ polynomial has at most $n$ roots in a field, so these are all its roots. Since $n+1$ is a distinct residue modulo $p$, it is not a root. Thus \[ p\nmid (n+1)^n-1. \] This holds for every prime divisor $p$ of $g_n(n)$, so \[ \gcd\left(g_n(n),(n+1)^n-1\right)=1. \] Therefore \[ g_{n+1}(n)=1, \] and hence $h(n)\le n+1$. $\square$

Corollary 3.

The Round-1 characterization \[ h(n)=n+1 \iff n+1 \text{ is prime} \] can now be read very quickly as follows.

1. If $h(n)=n+1$, then Theorem 1 shows that $n+1$ is prime.
2. Conversely, if $n+1$ is prime, the Round-1 divisibility argument gives $h(n)=n+1$.

So Theorem 1 strictly strengthens one direction of the Round-1 result.

Theorem 4.

Fix $M\ge 2$. Then the number of odd integers $n\le x$ with $h(n)>M$ is \[ \gg_M \frac{x}{\log x}. \] In particular, $h(n)$ is unbounded on odd $n$.

Proof.

Let \[ K_M=\mathbb Q(\sqrt 2,\sqrt 3,\dots,\sqrt M), \qquad L_M=K_M(i). \] The field $K_M$ is totally real, so complex conjugation acts trivially on $K_M$ and nontrivially on $i$. Hence there is an automorphism \[ \sigma\in \mathrm{Gal}(L_M/\mathbb Q) \] that fixes $K_M$ pointwise and sends $i\mapsto -i$.

By the Chebotarev density theorem, the set of rational primes $q$ with Frobenius element equal to $\sigma$ has positive density in the set of all primes. In particular, the number of such primes $q\le 2x+1$ is \[ \gg_M \frac{x}{\log x}. \]

Fix such a prime $q$. Because the Frobenius at $q$ is trivial on $K_M$, the prime $q$ splits completely in each quadratic field $\mathbb Q(\sqrt a)$ with $2\le a\le M$. Equivalently, each $a\in\{2,\dots,M\}$ is a quadratic residue modulo $q$. Because the Frobenius at $q$ is nontrivial on $\mathbb Q(i)$, we also have \[ q\equiv 3\pmod 4. \]

Set \[ n=\frac{q-1}{2}. \] Then $n$ is odd. For every $2\le a\le M$, Euler's criterion gives \[ a^{(q-1)/2}\equiv 1\pmod q, \] so \[ q\mid a^n-1. \] Therefore \[ q\mid g_M(n), \] hence \[ g_M(n)>1. \] By definition of $h(n)$, \[ h(n)>M. \]

Distinct primes $q$ give distinct integers $n=(q-1)/2$. So the number of odd integers $n\le x$ with $h(n)>M$ is at least the number of such primes $q\le 2x+1$, which is \[ \gg_M \frac{x}{\log x}. \] This proves the theorem. $\square$

6. ADVERSARIAL VERIFICATION

The new work has four possible failure points.

1. Could Theorem 1 fail when $m=4$? No. If $m=4$, then $m=2\cdot 2$ and the same subgroup-closure argument works.

2. Why does $p>m$ in Theorem 1? We first prove $p>m-1$. If $m$ is composite, then $p$ cannot equal $m$ because $p$ is prime. Hence indeed $p>m$.

3. Was the Round-1 odd-unboundedness proof really flawed? Yes. It asserted, without proof, that infinitely many primes can be chosen to split completely in a certain real field and simultaneously satisfy $q\equiv 3\pmod 4$. Theorem 4 fixes this by encoding both conditions inside one Galois extension $L_M$ and invoking Chebotarev once.

4. Does Theorem 4 really produce many odd $n$, not just infinitely many? Yes. Chebotarev gives a positive-density set of primes $q$. The map $q\mapsto (q-1)/2$ is injective, so the number of resulting odd integers $n\le x$ is also $\gg_M x/\log x$.

So the Round-2 additions are gap-free.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 gives three genuine advances.

1. It repairs the only actual Round-1 gap in the odd-unboundedness argument.
2. It proves the new structural theorem that $h(n)$ is always prime.
3. It strengthens odd unboundedness to the quantitative statement \[ \#\{n\le x:\ n \text{ odd and } h(n)>M\}\gg_M \frac{x}{\log x}. \]

The density questions from Erdős still remain open, but the structural understanding of $h(n)$ is now significantly sharper than in Round 1.

8. COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 63%

9. REFERENCES

• T. F. Bloom, Erdős Problem #770, ErdosProblems.com, accessed 2026-03-07.
• Classical input used in the proofs: the Chebotarev density theorem and Euler's criterion.

Problem 770 (Round 2)

1. ROUND-2 OBJECTIVE

Path (C): repair the only real Round-1 gap, and then push the structure of $h(n)$ substantially further.

Round 1 already established the useful characterization \[ h(n)=n+1 \iff n+1 \text{ is prime}, \] but the Round-1 proof that $h(n)$ is unbounded on odd $n$ had a gap: it intersected two prime conditions without proving that the intersection is infinite. The most promising Round-2 strategy is therefore:

1. first, repair that gap cleanly with one Chebotarev argument;
2. second, look for a new structural theorem about the values of $h(n)$ themselves.

That second step succeeds: $h(n)$ is always prime.

2. Round-1 FOUNDATION USED

I use the following Round-1 results.

1. The definition \[ h(n)=\min\left\{m\ge 2:\ \gcd(2^n-1,3^n-1,\dots,m^n-1)=1\right\}. \]
2. The Round-1 theorem \[ h(n)=n+1 \iff n+1 \text{ is prime}. \]

I also explicitly identify a flaw in the Round-1 proof of odd unboundedness and replace it by a correct proof.

3. NEW INSIGHT / TOOL (ROUND 2)

There are two new ideas.

1. Subgroup closure forces primality of $h(n)$. If $m=h(n)$ and a prime $p$ divides the gcd up to $m-1$, then the residues \[ 1,2,\dots,m-1 \] all lie in the subgroup of $n$th roots of unity modulo $p$. If $m$ were composite, then $m=ab$ with $2\le a,b\le m-1$, so subgroup closure would force $m$ itself to be an $n$th root, contradicting the minimality of $m$. Thus $h(n)$ is always prime.

2. The odd-$n$ argument should live in a single Galois extension. To force simultaneously \[ q\equiv 3\pmod 4 \qquad\text{and}\qquad 2,3,\dots,M \text{ all quadratic residues mod } q, \] one should work in the compositum \[ L_M=\mathbb Q(\sqrt 2,\sqrt 3,\dots,\sqrt M,i) \] and choose a Frobenius element that is trivial on the totally real part and nontrivial on $i$. Chebotarev then gives infinitely many such primes, indeed with positive density.

4. ATTACK PLAN (ROUND 2)

The exact Round-1 gaps were:

1. no structural theorem about the values of $h(n)$;
2. one missing justification in the odd-unboundedness proof.

I now prove three new statements.

1. For every $n\ge 1$, the integer $h(n)$ is prime.
2. For every $n\ge 1$, one has $h(n)\le n+1$.
3. For every fixed $M\ge 2$, the number of odd integers $n\le x$ with $h(n)>M$ is \[ \gg_M \frac{x}{\log x}. \] In particular, $h(n)$ is unbounded on odd $n$.

Statement $3$ repairs and strengthens the Round-1 odd-unboundedness claim.

5. WORK (ROUND 2)

For convenience write \[ g_m(n):=\gcd(2^n-1,3^n-1,\dots,m^n-1). \]

Theorem 1.

For every integer $n\ge 1$, the value $h(n)$ is prime.

Proof.

Set \[ m:=h(n). \] Then \[ g_{m-1}(n)>1 \qquad\text{and}\qquad g_m(n)=1. \] Choose a prime \[ p\mid g_{m-1}(n). \] Then \[ p\mid a^n-1 \qquad\text{for every } a=2,3,\dots,m-1. \] I claim that \[ p>m-1. \] Indeed, if $p\le m-1$, then taking $a=p$ gives \[ p^n-1\equiv -1\pmod p, \] contradicting $p\mid p^n-1$.

Now suppose, for contradiction, that $m$ is composite. Then we can write \[ m=ab \] with \[ 2\le a,b\le m-1. \] Since $p>m-1$, we actually have $p>m$ (because $p$ is prime while $m$ is composite), so the congruence class of $m$ modulo $p$ is represented by the ordinary integer $m$.

Let \[ H:=\{x\in \mathbb F_p^\times : x^n=1\}. \] This is a multiplicative subgroup of $\mathbb F_p^\times$. By choice of $p$, the residues of \[ 1,2,\dots,m-1 \] all belong to $H$. In particular, $a,b\in H$. Since $H$ is closed under multiplication, \[ m=ab\in H. \] Therefore \[ m^n\equiv 1\pmod p, \] so \[ p\mid m^n-1. \] But $p$ already divides $g_{m-1}(n)$, hence it divides $g_m(n)$, contradicting $g_m(n)=1$.

Therefore $m$ cannot be composite. So $h(n)=m$ is prime. $\square$

Corollary 2.

For every $n\ge 1$, \[ h(n)\le n+1. \]

Proof.

If $g_n(n)=1$, then by definition $h(n)\le n$. So suppose $g_n(n)>1$, and choose a prime $p\mid g_n(n)$. Exactly as above, $p>n$. Hence the residues \[ 1,2,\dots,n \] are $n$ distinct roots of the polynomial $X^n-1$ in $\mathbb F_p$. A degree-$n$ polynomial has at most $n$ roots in a field, so these are all its roots. Since $n+1$ is a distinct residue modulo $p$, it is not a root. Thus \[ p\nmid (n+1)^n-1. \] This holds for every prime divisor $p$ of $g_n(n)$, so \[ \gcd\left(g_n(n),(n+1)^n-1\right)=1. \] Therefore \[ g_{n+1}(n)=1, \] and hence $h(n)\le n+1$. $\square$

Corollary 3.

The Round-1 characterization \[ h(n)=n+1 \iff n+1 \text{ is prime} \] can now be read very quickly as follows.

1. If $h(n)=n+1$, then Theorem 1 shows that $n+1$ is prime.
2. Conversely, if $n+1$ is prime, the Round-1 divisibility argument gives $h(n)=n+1$.

So Theorem 1 strictly strengthens one direction of the Round-1 result.

Theorem 4.

Fix $M\ge 2$. Then the number of odd integers $n\le x$ with $h(n)>M$ is \[ \gg_M \frac{x}{\log x}. \] In particular, $h(n)$ is unbounded on odd $n$.

Proof.

Let \[ K_M=\mathbb Q(\sqrt 2,\sqrt 3,\dots,\sqrt M), \qquad L_M=K_M(i). \] The field $K_M$ is totally real, so complex conjugation acts trivially on $K_M$ and nontrivially on $i$. Hence there is an automorphism \[ \sigma\in \mathrm{Gal}(L_M/\mathbb Q) \] that fixes $K_M$ pointwise and sends $i\mapsto -i$.

By the Chebotarev density theorem, the set of rational primes $q$ with Frobenius element equal to $\sigma$ has positive density in the set of all primes. In particular, the number of such primes $q\le 2x+1$ is \[ \gg_M \frac{x}{\log x}. \]

Fix such a prime $q$. Because the Frobenius at $q$ is trivial on $K_M$, the prime $q$ splits completely in each quadratic field $\mathbb Q(\sqrt a)$ with $2\le a\le M$. Equivalently, each $a\in\{2,\dots,M\}$ is a quadratic residue modulo $q$. Because the Frobenius at $q$ is nontrivial on $\mathbb Q(i)$, we also have \[ q\equiv 3\pmod 4. \]

Set \[ n=\frac{q-1}{2}. \] Then $n$ is odd. For every $2\le a\le M$, Euler's criterion gives \[ a^{(q-1)/2}\equiv 1\pmod q, \] so \[ q\mid a^n-1. \] Therefore \[ q\mid g_M(n), \] hence \[ g_M(n)>1. \] By definition of $h(n)$, \[ h(n)>M. \]

Distinct primes $q$ give distinct integers $n=(q-1)/2$. So the number of odd integers $n\le x$ with $h(n)>M$ is at least the number of such primes $q\le 2x+1$, which is \[ \gg_M \frac{x}{\log x}. \] This proves the theorem. $\square$

6. ADVERSARIAL VERIFICATION

The new work has four possible failure points.

1. Could Theorem 1 fail when $m=4$? No. If $m=4$, then $m=2\cdot 2$ and the same subgroup-closure argument works.

2. Why does $p>m$ in Theorem 1? We first prove $p>m-1$. If $m$ is composite, then $p$ cannot equal $m$ because $p$ is prime. Hence indeed $p>m$.

3. Was the Round-1 odd-unboundedness proof really flawed? Yes. It asserted, without proof, that infinitely many primes can be chosen to split completely in a certain real field and simultaneously satisfy $q\equiv 3\pmod 4$. Theorem 4 fixes this by encoding both conditions inside one Galois extension $L_M$ and invoking Chebotarev once.

4. Does Theorem 4 really produce many odd $n$, not just infinitely many? Yes. Chebotarev gives a positive-density set of primes $q$. The map $q\mapsto (q-1)/2$ is injective, so the number of resulting odd integers $n\le x$ is also $\gg_M x/\log x$.

So the Round-2 additions are gap-free.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 gives three genuine advances.

1. It repairs the only actual Round-1 gap in the odd-unboundedness argument.
2. It proves the new structural theorem that $h(n)$ is always prime.
3. It strengthens odd unboundedness to the quantitative statement \[ \#\{n\le x:\ n \text{ odd and } h(n)>M\}\gg_M \frac{x}{\log x}. \]

The density questions from Erdős still remain open, but the structural understanding of $h(n)$ is now significantly sharper than in Round 1.

8. COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 63%

9. REFERENCES

• T. F. Bloom, Erdős Problem #770, ErdosProblems.com, accessed 2026-03-07.
• Classical input used in the proofs: the Chebotarev density theorem and Euler's criterion.

Erdős Problem #770: independent continuation

Date: 23 September 2026. Source versions read in full: 770.tex, 770_v2.tex in gpt_pro_5.4.

1) OBJECTIVE AND ALL-VERSION AUDIT

Both supplied versions use the common-gcd definition \[ h(n)=\min\{m\ge2:\gcd_{2\le a\le m}(a^n-1)=1\}. \] This is the convention used here; pairwise coprimality would be a different problem. The original questions concern densities of fixed values, limiting behaviour, and the greatest prime $p$ with $p-1\mid n$. Proving odd unboundedness alone does not settle them.

2) DIVISIBILITY MONOTONICITY AND POSITIVE LOWER DENSITY

If $d\mid n$, then $a^d-1\mid a^n-1$ for every $a$, so \[ h(d)\le h(n). \tag{1} \] Take one odd $d$ with $h(d)>M$, whose existence follows from the odd-unboundedness construction in the supplied source (also recorded on the official problem page). Every odd multiple of $d$ has $h(n)>M$. Consequently \[ \liminf_{x\to\infty}\frac{\#\{n\le x:n\text{ odd},\ h(n)>M\}}x\ge\frac1{2d}>0. \] Thus the source's $\gg_M x/\log x$ conclusion can be strengthened to positive lower density, once just one odd witness is available. This does not assert existence of a density for $h(n)=p$.

3) PERIODIC FINITE APPROXIMATIONS

For any prime $q>M$, define \[ d_q=\operatorname{lcm}_{2\le a\le M}\operatorname{ord}_q(a). \] Then \[ h(n)>M\quad\Longleftrightarrow\quad d_q\mid n\text{ for some prime }q>M. \tag{2} \] Indeed a prime dividing every $a^n-1$ must exceed $M$, and for such a prime the simultaneous power congruences are exactly the displayed divisibilities. For a finite set of primes $Q$, the corresponding union of multiples is periodic and has density \[ \sum_{\varnothing\ne S\subseteq Q}(-1)^{|S|+1} \frac1{\operatorname{lcm}_{q\in S}d_q}. \] These are rigorous computable lower bounds. If one could control the density of the tail union uniformly as $Q$ grows, then density existence would follow. The present argument provides no such tail estimate, and an infinite union of periodic sets must not be declared to have a density without it.

7) FINAL

UNRESOLVED. The quantitative odd-unboundedness consequence is strengthened, and the density obstacle is isolated exactly. The source's boundary case $h(1)=2$ must be handled directly when its proof refers to an empty gcd. Statement checked: https://www.erdosproblems.com/forum/thread/770.

8) COMPLETION ESTIMATE

COMPLETION: 15% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.