Erdős Problem #1057

Erdős Problem 1057 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1057

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1057.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1057.tex.

FORMAL RESTATEMENT.

Let $C(x)$ denote the number of Carmichael numbers in $[1,x]$. A composite integer $n$ is a Carmichael number if \[ a^{n-1}\equiv 1\pmod n\quad\text{for every integer }a\text{ with }\gcd(a,n)=1. \] Question: is it true that \[ C(x)=x^{1-o(1)}\quad\text{as }x\to\infty? \] Equivalently, does $\log C(x)/\log x \to 1$?

QUICK LITERATURE/CONTEXT CHECK.

I did not use external sources. I only use the statements listed in the problem text (Erdős upper bound, Pomerance heuristic, AGP lower bound, Harman exponent) as context, without re-proving them.

ATTACK PLAN.

Proof-track: establish Korselt's criterion; compute $C(x)$ for small $x$; attempt simple constructions of many Carmichael numbers. Disproof-track: attempt to show $C(x)$ must be much smaller than $x^{1-o(1)}$ using only elementary constraints. Best path here: prove Korselt's criterion and basic necessary conditions and do sanity-check computations; the asymptotic remains open.

WORK.

Lemma 1 (Korselt's criterion). A positive integer $n$ is a Carmichael number if and only if

1. $n$ is composite,
2. $n$ is squarefree, and
3. for every prime $p\mid n$, one has $p-1\mid n-1$.

Proof. ($\Rightarrow$) Assume $n$ is Carmichael. Then $n$ is composite by definition. If $p^2\mid n$ for some prime $p$, take $a=1+p$. Then $\gcd(a,n)=1$, but by the binomial theorem \[ (1+p)^{n-1}\equiv 1+(n-1)p \pmod{p^2}. \] Since $p\mid n$ implies $n-1\equiv -1\not\equiv 0\pmod p$, the term $(n-1)p$ is nonzero modulo $p^2$, so $(1+p)^{n-1}\not\equiv 1\pmod{p^2}$. This contradicts the Carmichael condition modulo $n$, hence $n$ must be squarefree.

Now fix a prime $p\mid n$. Since $n$ is Carmichael, for every integer $a$ coprime to $n$ (hence also coprime to $p$) we have $a^{n-1}\equiv 1\pmod p$. We claim there exists $g\in(\mathbb{Z}/p\mathbb{Z})^\times$ of order $p-1$. To see this, note that for any divisor $d$ of $p-1$, the polynomial $X^d-1$ has at most $d$ roots in the field $\mathbb{F}_p$, hence there are at most $d$ elements of $(\mathbb{Z}/p\mathbb{Z})^\times$ whose order divides $d$. Summing over all proper divisors $d<p-1$ shows that strictly fewer than $p-1$ elements have order dividing a proper divisor, so some element has order exactly $p-1$. Choose such a $g$ and lift it to an integer $a$ coprime to $n$. Then $a^{n-1}\equiv 1\pmod p$ implies $g^{n-1}=1$ in the cyclic subgroup generated by $g$ of size $p-1$, hence $p-1\mid n-1$.

($\Leftarrow$) Conversely, assume $1$--$3$. Let $a$ be coprime to $n$. Because $n$ is squarefree, it is enough to prove $a^{n-1}\equiv 1\pmod p$ for each prime $p\mid n$ and then combine the congruences via the Chinese remainder theorem. Fix such a $p$. By Fermat's little theorem, $a^{p-1}\equiv 1\pmod p$. By $3$, write $n-1=(p-1)t$. Then $a^{n-1}=(a^{p-1})^t\equiv 1^t\equiv 1\pmod p$. Thus $a^{n-1}\equiv 1\pmod p$ for all $p\mid n$, and CRT gives $a^{n-1}\equiv 1\pmod n$. So $n$ is Carmichael. $\square$

Lemma 2 (basic consequences). Every Carmichael number $n$ is odd and has at least three distinct prime factors.

Proof. By Lemma 1, $n$ is squarefree. If $2\mid n$ then $n$ has an odd prime divisor $p$ (since $n$ is composite and squarefree). Condition $3$ gives $p-1\mid n-1$. But $n$ even implies $n-1$ is odd, while $p-1$ is even, so no even number can divide an odd number; contradiction. Hence $n$ is odd.

If $n=pq$ were the product of two distinct primes, then $3$ gives $p-1\mid pq-1$. Reducing $pq-1$ modulo $p-1$ yields $pq-1\equiv 1\cdot q-1=q-1\pmod{p-1}$, so $p-1\mid q-1$. Similarly $q-1\mid p-1$, forcing $p-1=q-1$ and hence $p=q$, contradiction. Therefore $n$ must have at least three prime factors. $\square$

FAST REALITY CHECK (computation). Using Korselt's criterion and a smallest-prime-factor sieve, I computed:

C(10^3)=1
C(10^4)=7
C(10^5)=16
C(10^6)=43
C(10^7)=105
First 20 Carmichael numbers:
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341,
41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401

VERIFICATION.

For $n=561=3\cdot 11\cdot 17$, we have $2\mid 560$, $10\mid 560$, and $16\mid 560$, so Korselt's criterion holds, consistent with it being the first Carmichael number. Lemma 2 is consistent with the computed list: all listed Carmichael numbers are odd and (by factorization) have at least three prime factors.

FINAL: UNRESOLVED.

(i) Strongest proved partial result here. Korselt's criterion (Lemma 1) gives a complete and efficiently checkable characterization; in particular Carmichael numbers are odd, squarefree, and have at least three prime factors (Lemma 2). Computations show $C(10^7)=105$. (ii) First gap. Prove either a lower bound strong enough to force $\log C(x)/\log x\to 1$, or an upper bound that rules this out, using only the information explicitly allowed in the problem file. (iii) Top 3 next moves. $1$ Use Korselt's criterion to design constructive families (e.g. parameterized products of primes) and attempt to count them. $2$ Push computation of $C(x)$ to larger $x$ and compare $\log C(x)/\log x$ to $1$ to see empirical trends. $3$ Try to translate the known lower-bound constructions (as stated in the problem text) into explicit, checkable parameterizations to understand where the exponent comes from and whether it can approach $1$. (iv) What a minimal counterexample would look like. If the statement $C(x)=x^{1-o(1)}$ is false, one would expect an $\varepsilon>0$ and arbitrarily large $x$ with $C(x)\le x^{1-\varepsilon}$; any approach would likely exploit an obstruction that forces Carmichael numbers to have constrained prime-factor patterns (beyond Korselt's divisibility) that prevent them from being too dense.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT.

Let $C(x)$ denote the number of Carmichael numbers in $[1,x]$. A composite integer $n$ is a Carmichael number if \[ a^{n-1}\equiv 1\pmod n\quad\text{for every integer }a\text{ with }\gcd(a,n)=1. \] Question: is it true that \[ C(x)=x^{1-o(1)}\quad\text{as }x\to\infty? \] Equivalently, does $\log C(x)/\log x \to 1$?

QUICK LITERATURE/CONTEXT CHECK.

I did not use external sources. I only use the statements listed in the problem text (Erdős upper bound, Pomerance heuristic, AGP lower bound, Harman exponent) as context, without re-proving them.

ATTACK PLAN.

Proof-track: establish Korselt's criterion; compute $C(x)$ for small $x$; attempt simple constructions of many Carmichael numbers. Disproof-track: attempt to show $C(x)$ must be much smaller than $x^{1-o(1)}$ using only elementary constraints. Best path here: prove Korselt's criterion and basic necessary conditions and do sanity-check computations; the asymptotic remains open.

WORK.

Lemma 1 (Korselt's criterion). A positive integer $n$ is a Carmichael number if and only if

1. $n$ is composite,
2. $n$ is squarefree, and
3. for every prime $p\mid n$, one has $p-1\mid n-1$.

Proof. ($\Rightarrow$) Assume $n$ is Carmichael. Then $n$ is composite by definition. If $p^2\mid n$ for some prime $p$, take $a=1+p$. Then $\gcd(a,n)=1$, but by the binomial theorem \[ (1+p)^{n-1}\equiv 1+(n-1)p \pmod{p^2}. \] Since $p\mid n$ implies $n-1\equiv -1\not\equiv 0\pmod p$, the term $(n-1)p$ is nonzero modulo $p^2$, so $(1+p)^{n-1}\not\equiv 1\pmod{p^2}$. This contradicts the Carmichael condition modulo $n$, hence $n$ must be squarefree.

Now fix a prime $p\mid n$. Since $n$ is Carmichael, for every integer $a$ coprime to $n$ (hence also coprime to $p$) we have $a^{n-1}\equiv 1\pmod p$. We claim there exists $g\in(\mathbb{Z}/p\mathbb{Z})^\times$ of order $p-1$. To see this, note that for any divisor $d$ of $p-1$, the polynomial $X^d-1$ has at most $d$ roots in the field $\mathbb{F}_p$, hence there are at most $d$ elements of $(\mathbb{Z}/p\mathbb{Z})^\times$ whose order divides $d$. Summing over all proper divisors $d<p-1$ shows that strictly fewer than $p-1$ elements have order dividing a proper divisor, so some element has order exactly $p-1$. Choose such a $g$ and lift it to an integer $a$ coprime to $n$. Then $a^{n-1}\equiv 1\pmod p$ implies $g^{n-1}=1$ in the cyclic subgroup generated by $g$ of size $p-1$, hence $p-1\mid n-1$.

($\Leftarrow$) Conversely, assume $1$--$3$. Let $a$ be coprime to $n$. Because $n$ is squarefree, it is enough to prove $a^{n-1}\equiv 1\pmod p$ for each prime $p\mid n$ and then combine the congruences via the Chinese remainder theorem. Fix such a $p$. By Fermat's little theorem, $a^{p-1}\equiv 1\pmod p$. By $3$, write $n-1=(p-1)t$. Then $a^{n-1}=(a^{p-1})^t\equiv 1^t\equiv 1\pmod p$. Thus $a^{n-1}\equiv 1\pmod p$ for all $p\mid n$, and CRT gives $a^{n-1}\equiv 1\pmod n$. So $n$ is Carmichael. $\square$

Lemma 2 (basic consequences). Every Carmichael number $n$ is odd and has at least three distinct prime factors.

Proof. By Lemma 1, $n$ is squarefree. If $2\mid n$ then $n$ has an odd prime divisor $p$ (since $n$ is composite and squarefree). Condition $3$ gives $p-1\mid n-1$. But $n$ even implies $n-1$ is odd, while $p-1$ is even, so no even number can divide an odd number; contradiction. Hence $n$ is odd.

If $n=pq$ were the product of two distinct primes, then $3$ gives $p-1\mid pq-1$. Reducing $pq-1$ modulo $p-1$ yields $pq-1\equiv 1\cdot q-1=q-1\pmod{p-1}$, so $p-1\mid q-1$. Similarly $q-1\mid p-1$, forcing $p-1=q-1$ and hence $p=q$, contradiction. Therefore $n$ must have at least three prime factors. $\square$

FAST REALITY CHECK (computation). Using Korselt's criterion and a smallest-prime-factor sieve, I computed:

C(10^3)=1
C(10^4)=7
C(10^5)=16
C(10^6)=43
C(10^7)=105
First 20 Carmichael numbers:
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341,
41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401

VERIFICATION.

For $n=561=3\cdot 11\cdot 17$, we have $2\mid 560$, $10\mid 560$, and $16\mid 560$, so Korselt's criterion holds, consistent with it being the first Carmichael number. Lemma 2 is consistent with the computed list: all listed Carmichael numbers are odd and (by factorization) have at least three prime factors.

FINAL: UNRESOLVED.

(i) Strongest proved partial result here. Korselt's criterion (Lemma 1) gives a complete and efficiently checkable characterization; in particular Carmichael numbers are odd, squarefree, and have at least three prime factors (Lemma 2). Computations show $C(10^7)=105$. (ii) First gap. Prove either a lower bound strong enough to force $\log C(x)/\log x\to 1$, or an upper bound that rules this out, using only the information explicitly allowed in the problem file. (iii) Top 3 next moves. $1$ Use Korselt's criterion to design constructive families (e.g. parameterized products of primes) and attempt to count them. $2$ Push computation of $C(x)$ to larger $x$ and compare $\log C(x)/\log x$ to $1$ to see empirical trends. $3$ Try to translate the known lower-bound constructions (as stated in the problem text) into explicit, checkable parameterizations to understand where the exponent comes from and whether it can approach $1$. (iv) What a minimal counterexample would look like. If the statement $C(x)=x^{1-o(1)}$ is false, one would expect an $\varepsilon>0$ and arbitrarily large $x$ with $C(x)\le x^{1-\varepsilon}$; any approach would likely exploit an obstruction that forces Carmichael numbers to have constrained prime-factor patterns (beyond Korselt's divisibility) that prevent them from being too dense.