Erdős Problem #828

Erdős Problem 828 --- collection record

PROVENANCE AND STATUS

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/828.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT

For a fixed integer $a\in\mathbb{Z}$, determine whether there exist infinitely many integers $n\in\mathbb{N}$ such that \[ \varphi(n)\mid (n+a), \] where $\varphi(n)$ is Euler's totient function (the number of integers $1\leq m\leq n$ with $\gcd(m,n)=1$). Equivalently: for fixed $a$, does the congruence $n\equiv -a\pmod{\varphi(n)}$ hold for infinitely many $n\ge1$? Edge cases: $n=1$ has $\varphi(1)=1$ and hence always satisfies $\varphi(1)\mid (1+a)$.

QUICK LITERATURE/CONTEXT CHECK

The problem statement attributes the question to a conjecture of Graham. It notes Lehmer's conjecture: $\varphi(n)\mid (n-1)$ iff $n$ is prime, and the exercise that $\varphi(n)\mid n$ iff $n=2^\alpha 3^\beta$. No other results are assumed below.

ATTACK PLAN

Proof track: $1$ Prove the classification $\varphi(n)\mid n \iff n=2^\alpha 3^\beta$ from scratch. $2$ Use multiplicativity of $\varphi$ to build infinite families of $n$ for some $a$ by forcing $n+a$ to be a multiple of $\varphi(n)$.

Disproof track: Search for an $a$ where the congruence appears to have only finitely many solutions; try to prove finiteness via congruence obstructions. (At present, this seems hard; we only obtain partial families.)

WORK

Lemma 1 (classification of $\varphi(n)\mid n$). For $n\in\mathbb{N}$, one has $\varphi(n)\mid n$ if and only if $n=2^\alpha 3^\beta$ for some integers $\alpha,\beta\ge0$.

Proof. Write the prime factorization $n=\prod_{i=1}^t p_i^{e_i}$ with distinct primes $p_i$ and exponents $e_i\ge1$. Then \[ \varphi(n)=n\prod_{i=1}^t\left(1-\frac1{p_i}\right)=n\prod_{i=1}^t\frac{p_i-1}{p_i}. \] Thus \[ \frac{n}{\varphi(n)}=\prod_{i=1}^t\frac{p_i}{p_i-1}. \] The condition $\varphi(n)\mid n$ is equivalent to $\frac{n}{\varphi(n)}\in\mathbb{Z}$.

Let $S$ be the set of odd primes dividing $n$. For each odd prime $p\in S$, the integer $p-1$ is even, so the denominator of the product above contributes at least one factor $2$. Therefore the denominator of $\prod_{p\mid n} \frac{p}{p-1}$ is divisible by $2^{|S|}$. The numerator of this product is $\prod_{p\mid n} p$, whose $2$-adic valuation is exactly $1$ if $2\mid n$ and $0$ if $2\nmid n$. Hence, for the whole product to be an integer, one must have $|S|\le 1$ (otherwise the denominator has a factor $2^2$ while the numerator has at most one factor $2$).

If $|S|=0$, then $n$ is a power of $2$ (or $n=1$), so $n=2^\alpha 3^\beta$ with $\beta=0$. If $|S|=1$, write $S=\{p\}$ with $p$ an odd prime. Then $2\mid n$, because if $2\nmid n$ then $\frac{n}{\varphi(n)}=\frac{p}{p-1}$ which is not an integer for $p>2$. So the set of primes dividing $n$ is exactly $\{2,p\}$ and \[ \frac{n}{\varphi(n)}=\frac{2}{1}\cdot \frac{p}{p-1} = \frac{2p}{p-1}. \] If this is an integer, then $p-1\mid 2p$. Since $\gcd(p-1,p)=1$, we have $p-1\mid 2$. Thus $p-1\in\{1,2\}$, giving $p\in\{2,3\}$. Because $p$ is odd, $p=3$. So the only possible odd prime divisor is $3$. Therefore $n$ has no prime divisors other than $2$ and $3$, i.e. $n=2^\alpha 3^\beta$.

Conversely, if $n=2^\alpha 3^\beta$, then $\varphi$ is multiplicative on coprime factors and \[ \varphi(2^\alpha)=\begin{cases}1,&\alpha=0,\\2^{\alpha-1},&\alpha\ge1,\end{cases} \qquad \varphi(3^\beta)=\begin{cases}1,&\beta=0,\\2\cdot 3^{\beta-1},&\beta\ge1.\end{cases} \] Hence $\varphi(2^\alpha 3^\beta)$ is a product of powers of $2$ and $3$ and divides $2^\alpha 3^\beta$. This proves the equivalence. $\square$

Lemma 2 (infinite family for many negative shifts). Let $k\in\mathbb{N}$ satisfy $\varphi(k)\mid k$ (equivalently $k=2^\alpha 3^\beta$ by Lemma 1), and let $a=-k$. Then there exist infinitely many $n\in\mathbb{N}$ such that $\varphi(n)\mid (n+a)$.

Proof. Let $k$ be fixed with $\varphi(k)\mid k$ and choose any prime $p\ge5$. Then $\gcd(k,p)=1$, so multiplicativity gives \[ \varphi(kp)=\varphi(k)\varphi(p)=\varphi(k)(p-1). \] Also \[ (kp)+a = kp-k = k(p-1). \] Because $\varphi(k)\mid k$, we may write $k=\varphi(k)\,t$ for some integer $t$. Then \[ kp-k = \varphi(k)\,t\,(p-1), \] which is divisible by $\varphi(k)(p-1)=\varphi(kp)$. Thus $\varphi(kp)\mid (kp-k)$. Since there are infinitely many primes $p\ge5$, this gives infinitely many $n=kp$ solving $\varphi(n)\mid (n-k)$. $\square$

Fast reality check (computation; exact search). Using a brute-force check of $\varphi(n)\mid (n+a)$ for $1\le n\le 200$ and $-10\le a\le 10$, we found the following counts of solutions (and the first few solutions in each case): \[ \begin{array}{r|l} a & \#\{n\le 200: \varphi(n)\mid n+a\}\ \text{ and sample solutions}\\\hline -10 & 6\ \ (1,2,4,6,10,50)\\ -9 & 8\ \ (1,2,3,5,9,21,27,105)\\ -8 & 16\ \ (1,2,4,6,8,12,14,16,24,40,\dots)\\ -7 & 6\ \ (1,2,3,7,15,49)\\ -6 & 15\ \ (1,2,4,6,10,18,30,42,\dots)\\ -5 & 6\ \ (1,2,3,5,25,165)\\ -4 & 19\ \ (1,2,4,6,8,12,20,28,\dots)\\ -3 & 5\ \ (1,2,3,9,195)\\ -2 & 27\ \ (1,2,4,6,10,14,22,26,\dots)\\ -1 & 47\ \ (1,2,3,5,7,11,13,17,\dots)\\ 0 & 21\ \ (1,2,4,6,8,12,16,18,\dots)\\ 1 & 4\ \ (1,2,3,15)\\ 2 & 7\ \ (1,2,4,6,10,30,70)\\ 3 & 7\ \ (1,2,3,5,9,21,45)\\ 4 & 10\ \ (1,2,4,6,8,12,14,20,\dots)\\ 5 & 5\ \ (1,2,3,7,75)\\ 6 & 8\ \ (1,2,4,6,10,18,42,90)\\ 7 & 5\ \ (1,2,3,5,33)\\ 8 & 12\ \ (1,2,4,6,8,12,16,22,\dots)\\ 9 & 10\ \ (1,2,3,9,11,15,27,\dots)\\ 10 & 11\ \ (1,2,4,6,10,14,26,\dots) \end{array} \] These data are only sanity checks (they do not address infinitude), but they confirm the explicit infinite families from Lemma 2 when $a=-k$ with $k=2^\alpha 3^\beta$ (e.g. $a=-6$ has many solutions $n=6p$).

VERIFICATION

$1$ Lemma 1 uses only the exact product formula $\varphi(n)=n\prod_{p\mid n}(1-1/p)$ and a 2-adic valuation argument. The key step is: if $n$ has at least two odd prime divisors, then the denominator contributes $2^2$ while the numerator contributes at most one factor of $2$. This is correct because the numerator is $\prod_{p\mid n} p$ (each prime once). $2$ Lemma 2 checks divisibility by explicit factorization and multiplicativity. The only external input is the infinitude of primes (Euclid), which is standard. $3$ Edge cases: $k=1$ gives $a=-1$ and $n=p$ prime yields $\varphi(p)=p-1\mid p-1$, consistent.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved that $\varphi(n)\mid n$ iff $n=2^\alpha 3^\beta$ (Lemma 1), and consequently for every $a=-2^\alpha 3^\beta$ (including $a=0$ and $a=-1$) there are infinitely many solutions $n$ (Lemma 2, via $n=kp$ with $p$ prime and $k=-a$).

(ii) First gap (crisp statement). For a fixed integer $a$ not of the form $a=-2^\alpha 3^\beta$, prove or disprove: there exist infinitely many $n\in\mathbb{N}$ such that $\varphi(n)\mid (n+a)$.

(iii) Top 3 next moves. 1. Try to construct infinite families for positive $a$ (e.g. $a=1$) by forcing $n+a$ to factor as $\varphi(n)\,t$ with controlled prime factors of $n$. 2. Search systematically for parametric families $n=f(t)$ where $\varphi(n)$ has an explicit form and the congruence $n\equiv -a\pmod{\varphi(n)}$ becomes a manageable congruence in $t$. 3. Computation: for each fixed $a$ (say $|a|\le 20$), search for solutions with restricted prime patterns (e.g. $n=pq$, $n=2^e p$, $n=2^e 3^f p$) to guess candidate infinite families.

(iv) Minimal counterexample structure. A potential counterexample to Graham's conjecture would be an integer $a$ for which all solutions $n$ have bounded size or belong to a very sparse set; computationally, $a=1$ looks comparatively sparse for $n\le 200$ (only $n=1,2,3,15$), suggesting that a minimal counterexample might be a small positive $a$ with strong congruence obstructions.

COMPLETION ESTIMATE

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

For a fixed integer $a\in\mathbb{Z}$, determine whether there exist infinitely many integers $n\in\mathbb{N}$ such that \[ \varphi(n)\mid (n+a), \] where $\varphi(n)$ is Euler's totient function (the number of integers $1\leq m\leq n$ with $\gcd(m,n)=1$). Equivalently: for fixed $a$, does the congruence $n\equiv -a\pmod{\varphi(n)}$ hold for infinitely many $n\ge1$? Edge cases: $n=1$ has $\varphi(1)=1$ and hence always satisfies $\varphi(1)\mid (1+a)$.

QUICK LITERATURE/CONTEXT CHECK

The problem statement attributes the question to a conjecture of Graham. It notes Lehmer's conjecture: $\varphi(n)\mid (n-1)$ iff $n$ is prime, and the exercise that $\varphi(n)\mid n$ iff $n=2^\alpha 3^\beta$. No other results are assumed below.

ATTACK PLAN

Proof track: $1$ Prove the classification $\varphi(n)\mid n \iff n=2^\alpha 3^\beta$ from scratch. $2$ Use multiplicativity of $\varphi$ to build infinite families of $n$ for some $a$ by forcing $n+a$ to be a multiple of $\varphi(n)$.

Disproof track: Search for an $a$ where the congruence appears to have only finitely many solutions; try to prove finiteness via congruence obstructions. (At present, this seems hard; we only obtain partial families.)

WORK

Lemma 1 (classification of $\varphi(n)\mid n$). For $n\in\mathbb{N}$, one has $\varphi(n)\mid n$ if and only if $n=2^\alpha 3^\beta$ for some integers $\alpha,\beta\ge0$.

Proof. Write the prime factorization $n=\prod_{i=1}^t p_i^{e_i}$ with distinct primes $p_i$ and exponents $e_i\ge1$. Then \[ \varphi(n)=n\prod_{i=1}^t\left(1-\frac1{p_i}\right)=n\prod_{i=1}^t\frac{p_i-1}{p_i}. \] Thus \[ \frac{n}{\varphi(n)}=\prod_{i=1}^t\frac{p_i}{p_i-1}. \] The condition $\varphi(n)\mid n$ is equivalent to $\frac{n}{\varphi(n)}\in\mathbb{Z}$.

Let $S$ be the set of odd primes dividing $n$. For each odd prime $p\in S$, the integer $p-1$ is even, so the denominator of the product above contributes at least one factor $2$. Therefore the denominator of $\prod_{p\mid n} \frac{p}{p-1}$ is divisible by $2^{|S|}$. The numerator of this product is $\prod_{p\mid n} p$, whose $2$-adic valuation is exactly $1$ if $2\mid n$ and $0$ if $2\nmid n$. Hence, for the whole product to be an integer, one must have $|S|\le 1$ (otherwise the denominator has a factor $2^2$ while the numerator has at most one factor $2$).

If $|S|=0$, then $n$ is a power of $2$ (or $n=1$), so $n=2^\alpha 3^\beta$ with $\beta=0$. If $|S|=1$, write $S=\{p\}$ with $p$ an odd prime. Then $2\mid n$, because if $2\nmid n$ then $\frac{n}{\varphi(n)}=\frac{p}{p-1}$ which is not an integer for $p>2$. So the set of primes dividing $n$ is exactly $\{2,p\}$ and \[ \frac{n}{\varphi(n)}=\frac{2}{1}\cdot \frac{p}{p-1} = \frac{2p}{p-1}. \] If this is an integer, then $p-1\mid 2p$. Since $\gcd(p-1,p)=1$, we have $p-1\mid 2$. Thus $p-1\in\{1,2\}$, giving $p\in\{2,3\}$. Because $p$ is odd, $p=3$. So the only possible odd prime divisor is $3$. Therefore $n$ has no prime divisors other than $2$ and $3$, i.e. $n=2^\alpha 3^\beta$.

Conversely, if $n=2^\alpha 3^\beta$, then $\varphi$ is multiplicative on coprime factors and \[ \varphi(2^\alpha)=\begin{cases}1,&\alpha=0,\\2^{\alpha-1},&\alpha\ge1,\end{cases} \qquad \varphi(3^\beta)=\begin{cases}1,&\beta=0,\\2\cdot 3^{\beta-1},&\beta\ge1.\end{cases} \] Hence $\varphi(2^\alpha 3^\beta)$ is a product of powers of $2$ and $3$ and divides $2^\alpha 3^\beta$. This proves the equivalence. $\square$

Lemma 2 (infinite family for many negative shifts). Let $k\in\mathbb{N}$ satisfy $\varphi(k)\mid k$ (equivalently $k=2^\alpha 3^\beta$ by Lemma 1), and let $a=-k$. Then there exist infinitely many $n\in\mathbb{N}$ such that $\varphi(n)\mid (n+a)$.

Proof. Let $k$ be fixed with $\varphi(k)\mid k$ and choose any prime $p\ge5$. Then $\gcd(k,p)=1$, so multiplicativity gives \[ \varphi(kp)=\varphi(k)\varphi(p)=\varphi(k)(p-1). \] Also \[ (kp)+a = kp-k = k(p-1). \] Because $\varphi(k)\mid k$, we may write $k=\varphi(k)\,t$ for some integer $t$. Then \[ kp-k = \varphi(k)\,t\,(p-1), \] which is divisible by $\varphi(k)(p-1)=\varphi(kp)$. Thus $\varphi(kp)\mid (kp-k)$. Since there are infinitely many primes $p\ge5$, this gives infinitely many $n=kp$ solving $\varphi(n)\mid (n-k)$. $\square$

Fast reality check (computation; exact search). Using a brute-force check of $\varphi(n)\mid (n+a)$ for $1\le n\le 200$ and $-10\le a\le 10$, we found the following counts of solutions (and the first few solutions in each case): \[ \begin{array}{r|l} a & \#\{n\le 200: \varphi(n)\mid n+a\}\ \text{ and sample solutions}\\\hline -10 & 6\ \ (1,2,4,6,10,50)\\ -9 & 8\ \ (1,2,3,5,9,21,27,105)\\ -8 & 16\ \ (1,2,4,6,8,12,14,16,24,40,\dots)\\ -7 & 6\ \ (1,2,3,7,15,49)\\ -6 & 15\ \ (1,2,4,6,10,18,30,42,\dots)\\ -5 & 6\ \ (1,2,3,5,25,165)\\ -4 & 19\ \ (1,2,4,6,8,12,20,28,\dots)\\ -3 & 5\ \ (1,2,3,9,195)\\ -2 & 27\ \ (1,2,4,6,10,14,22,26,\dots)\\ -1 & 47\ \ (1,2,3,5,7,11,13,17,\dots)\\ 0 & 21\ \ (1,2,4,6,8,12,16,18,\dots)\\ 1 & 4\ \ (1,2,3,15)\\ 2 & 7\ \ (1,2,4,6,10,30,70)\\ 3 & 7\ \ (1,2,3,5,9,21,45)\\ 4 & 10\ \ (1,2,4,6,8,12,14,20,\dots)\\ 5 & 5\ \ (1,2,3,7,75)\\ 6 & 8\ \ (1,2,4,6,10,18,42,90)\\ 7 & 5\ \ (1,2,3,5,33)\\ 8 & 12\ \ (1,2,4,6,8,12,16,22,\dots)\\ 9 & 10\ \ (1,2,3,9,11,15,27,\dots)\\ 10 & 11\ \ (1,2,4,6,10,14,26,\dots) \end{array} \] These data are only sanity checks (they do not address infinitude), but they confirm the explicit infinite families from Lemma 2 when $a=-k$ with $k=2^\alpha 3^\beta$ (e.g. $a=-6$ has many solutions $n=6p$).

VERIFICATION

$1$ Lemma 1 uses only the exact product formula $\varphi(n)=n\prod_{p\mid n}(1-1/p)$ and a 2-adic valuation argument. The key step is: if $n$ has at least two odd prime divisors, then the denominator contributes $2^2$ while the numerator contributes at most one factor of $2$. This is correct because the numerator is $\prod_{p\mid n} p$ (each prime once). $2$ Lemma 2 checks divisibility by explicit factorization and multiplicativity. The only external input is the infinitude of primes (Euclid), which is standard. $3$ Edge cases: $k=1$ gives $a=-1$ and $n=p$ prime yields $\varphi(p)=p-1\mid p-1$, consistent.

FINAL

UNRESOLVED

(i) Strongest proved partial result. We proved that $\varphi(n)\mid n$ iff $n=2^\alpha 3^\beta$ (Lemma 1), and consequently for every $a=-2^\alpha 3^\beta$ (including $a=0$ and $a=-1$) there are infinitely many solutions $n$ (Lemma 2, via $n=kp$ with $p$ prime and $k=-a$).

(ii) First gap (crisp statement). For a fixed integer $a$ not of the form $a=-2^\alpha 3^\beta$, prove or disprove: there exist infinitely many $n\in\mathbb{N}$ such that $\varphi(n)\mid (n+a)$.

(iii) Top 3 next moves. 1. Try to construct infinite families for positive $a$ (e.g. $a=1$) by forcing $n+a$ to factor as $\varphi(n)\,t$ with controlled prime factors of $n$. 2. Search systematically for parametric families $n=f(t)$ where $\varphi(n)$ has an explicit form and the congruence $n\equiv -a\pmod{\varphi(n)}$ becomes a manageable congruence in $t$. 3. Computation: for each fixed $a$ (say $|a|\le 20$), search for solutions with restricted prime patterns (e.g. $n=pq$, $n=2^e p$, $n=2^e 3^f p$) to guess candidate infinite families.

(iv) Minimal counterexample structure. A potential counterexample to Graham's conjecture would be an integer $a$ for which all solutions $n$ have bounded size or belong to a very sparse set; computationally, $a=1$ looks comparatively sparse for $n\le 200$ (only $n=1,2,3,15$), suggesting that a minimal counterexample might be a small positive $a$ with strong congruence obstructions.