Erdős Problem #1065

Erdős Problem 1065 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

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

FORMAL RESTATEMENT

We ask whether there exist infinitely many primes $p$ of the form \[ p = 2^k q + 1 \qquad (k \in \mathbb{N}_0,\ q \text{ prime}). \] Equivalently: are there infinitely many primes $p$ such that $p-1$ has the form \[ p-1 = 2^k q \quad\text{with $k\ge 0$ and $q$ prime?} \] A second question asks the analogous statement with an additional power of $3$: \[ p = 2^k 3^\ell q + 1 \qquad (k,\ell \in \mathbb{N}_0,\ q \text{ prime}). \]

QUICK LITERATURE/CONTEXT CHECK

The case $k=1$ in the first question is the "safe prime" condition $p=2q+1$ with $q$ prime. The case $q=2$ gives primes of the form $2^m+1$ (Fermat-type). The problem file itself does not assert any general infinitude results; I therefore treat both questions as open here and only record direct deductions and computations.

ATTACK PLAN

Reformulate the condition in terms of the prime factorization of $p-1$ (odd part constraints). Prove exact classifications in degenerate cases ($k=0$, $q=2$). Then do a "FAST REALITY CHECK" by enumerating primes $p\le N$ satisfying each condition for several $N$.

WORK

Lemma 1065.1 (the $k=0$ case is unique). If $p$ and $q$ are primes and $p=q+1$, then $(q,p)=(2,3)$.

Proof. If $q=2$ then $p=3$ is prime, giving one solution. Assume $q>2$. Then $q$ is odd, so $p=q+1$ is an even integer strictly larger than $2$, hence not prime. Therefore no solutions exist with $q>2$, and the only solution is $(q,p)=(2,3)$. $\square$

Lemma 1065.2 (the $q=2$ subfamily equals Fermat-type primes). Let $p$ be prime. Then $p=2^k q+1$ with $q=2$ and $k\ge 0$ holds if and only if $p$ is of the form $p=2^m+1$ with $m\ge 1$.

Proof. If $q=2$, then $p = 2^k\cdot 2 + 1 = 2^{k+1}+1$, so $p=2^m+1$ with $m=k+1\ge 1$. Conversely, if $p=2^m+1$ with $m\ge 1$, then writing $m=k+1$ gives $p=2^k\cdot 2+1$, i.e. $q=2$. $\square$

Lemma 1065.3 (factorization reformulation). Let $p$ be an odd prime and write $p-1=2^{v_2(p-1)}\,\mathrm{odd}(p-1)$ where $\mathrm{odd}(p-1)$ is the odd part. Then $p=2^k q+1$ for some prime $q$ and some $k\ge 0$ if and only if $\mathrm{odd}(p-1)$ is either $1$ or a prime. Moreover, the representation is unique:

• if $\mathrm{odd}(p-1)$ is an odd prime, then necessarily $k=v_2(p-1)$ and $q=\mathrm{odd}(p-1)$;
• if $\mathrm{odd}(p-1)=1$ (so $p-1$ is a power of $2$), then necessarily $q=2$ and $k=v_2(p-1)-1$.

Proof. ($\Rightarrow$) Suppose $p-1=2^k q$ with $q$ prime. If $q$ is odd then $\mathrm{odd}(p-1)=q$ is prime. If $q=2$ then $p-1$ is a pure power of $2$, hence $\mathrm{odd}(p-1)=1$. In either case $\mathrm{odd}(p-1)\in\{1\}\cup\{\text{primes}\}$.

($\Leftarrow$) If $\mathrm{odd}(p-1)$ is an odd prime $q$, then $p-1=2^{v_2(p-1)}q$ gives $p=2^{v_2(p-1)}q+1$. If $\mathrm{odd}(p-1)=1$, then $p-1=2^m$ where $m=v_2(p-1)\ge 1$ (since $p$ is odd). Then \[ p-1 = 2^{m-1}\cdot 2, \] so $p=2^{m-1}\cdot 2 + 1$ with $q=2$ and $k=m-1$.

For uniqueness: if $\mathrm{odd}(p-1)$ is an odd prime and $p-1=2^{k'}q'$ with $q'$ prime, then $q'$ must be odd (otherwise $q'=2$ forces $\mathrm{odd}(p-1)=1$), so $2^{k'}$ must be the full power of $2$ dividing $p-1$, hence $k'=v_2(p-1)$ and $q'=\mathrm{odd}(p-1)$. If $\mathrm{odd}(p-1)=1$ and $p-1=2^{k'}q'$ with $q'$ prime, then $q'$ must be $2$ and $k'=v_2(p-1)-1$. $\square$

Lemma 1065.4 (analogous reformulation for $2^k3^\ell q$). Let $p$ be prime. Then $p=2^k3^\ell q+1$ for some $k,\ell\ge 0$ and prime $q$ if and only if, after removing all factors of $2$ and $3$ from $p-1$, the remaining factor is either $1$ or a prime.

Proof. Write $p-1 = 2^a3^b r$ where $\gcd(r,6)=1$. If $r$ is prime, take $(k,\ell,q)=(a,b,r)$. If $r=1$, then $p-1=2^a3^b$; if $a\ge 1$ take $(k,\ell,q)=(a-1,b,2)$, and if $a=0$ then $b\ge 1$ and take $(k,\ell,q)=(0,b-1,3)$. Conversely, any representation $p-1=2^k3^\ell q$ has $r=q$ after removing all $2,3$ factors, hence $r$ is $1$ or prime. $\square$

FAST REALITY CHECK (computation). I enumerated primes $p\le N$ and tested the conditions by factoring $p-1$ and checking whether it can be written as $2^k q$ with $q$ prime, and similarly $2^k3^\ell q$ with $q$ prime. Exact results: \[ \begin{array}{r|r|r|r|r} N & \#\{p\le N\} & \#\{p\le N: p=2^k q+1\} & \#\{p\le N: p=2^k3^\ell q+1\} & \text{fractions} \\ \hline 10^3 & 168 & 59 & 117 & 0.351,\ 0.696 \\ 10^4 & 1229 & 257 & 580 & 0.209,\ 0.472 \\ 10^5 & 9592 & 1470 & 3264 & 0.153,\ 0.340 \\ 10^6 & 78498 & 9287 & 20479 & 0.118,\ 0.261 \end{array} \] The first few primes $p$ satisfying $p=2^kq+1$ (with their $(k,q)$) are: \[ 3\,(0,2),\ 5\,(1,2),\ 7\,(1,3),\ 11\,(1,5),\ 13\,(2,3),\ 17\,(3,2),\ 23\,(1,11),\ 29\,(2,7),\ 41\,(3,5),\ldots \] (Computed by a minimal script using primality testing and dividing $p-1$ by successive powers of $2$ and $3$.)

VERIFICATION

Lemma 1065.1 is a parity argument and is complete. Lemma 1065.2 is algebraic and complete. Lemma 1065.3 is checked by the standard $2$-adic valuation decomposition of $p-1$; it shows that $p=2^kq+1$ with $q$ prime holds exactly when the odd part of $p-1$ is $1$ or prime, and it records the (case-by-case) uniqueness of $(k,q)$. Lemma 1065.4 follows by extracting maximal powers of $2$ and $3$. The computational table was obtained by direct enumeration of primes and exact arithmetic on $p-1$.

FINAL

UNRESOLVED.

(i) Strongest proved partial result: The problem reduces to the arithmetic of $p-1$: for odd primes $p$, the condition $p=2^kq+1$ holds exactly when the odd part of $p-1$ is either $1$ or prime (equivalently, $p-1$ has at most one odd prime factor) (Lemma 1065.3), with complete classification of the degenerate cases $k=0$ and $q=2$ (Lemmas 1065.1--1065.2). Analogously, $p=2^k3^\ell q+1$ holds exactly when $(p-1)/2^{v_2(p-1)}3^{v_3(p-1)}$ is $1$ or prime (Lemma 1065.4). Computations up to $10^6$ give the exact counts recorded above.

(ii) First gap (crisp statement): Prove (or disprove) that there are infinitely many primes $p$ for which the odd part of $p-1$ is either $1$ or prime (equivalently, infinitely many primes $p$ with $p-1=2^k q$ for some prime $q$).

(iii) Top 3 next moves (concrete lemmas/computations):

1. Study fixed-$k$ subfamilies: for each fixed $k\ge 1$, attempt to show infinitely many primes of the form $p=2^k q+1$ with $q$ prime (even $k=1$ is already a central special case).
2. For the $2^k3^\ell q+1$ variant, attempt to control primes $p$ for which $(p-1)$ has at most one prime factor outside $\{2,3\}$; a first concrete step is to obtain nontrivial lower bounds on the count of such primes up to $N$.
3. Extend the computations (e.g. to $N\approx 10^8$ if feasible) and record empirical densities as a function of $\log N$, plus the distribution of $(v_2(p-1),v_3(p-1))$ among the solutions.

(iv) Minimal counterexample structure: If only finitely many such primes exist, then there is a bound $P_0$ such that for every prime $p>P_0$, $p-1$ has at least two distinct odd prime factors (for the first question), and for the second question $p-1$ has at least two prime factors outside $\{2,3\}$.

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

We ask whether there exist infinitely many primes $p$ of the form \[ p = 2^k q + 1 \qquad (k \in \mathbb{N}_0,\ q \text{ prime}). \] Equivalently: are there infinitely many primes $p$ such that $p-1$ has the form \[ p-1 = 2^k q \quad\text{with $k\ge 0$ and $q$ prime?} \] A second question asks the analogous statement with an additional power of $3$: \[ p = 2^k 3^\ell q + 1 \qquad (k,\ell \in \mathbb{N}_0,\ q \text{ prime}). \]

QUICK LITERATURE/CONTEXT CHECK

The case $k=1$ in the first question is the "safe prime" condition $p=2q+1$ with $q$ prime. The case $q=2$ gives primes of the form $2^m+1$ (Fermat-type). The problem file itself does not assert any general infinitude results; I therefore treat both questions as open here and only record direct deductions and computations.

ATTACK PLAN

Reformulate the condition in terms of the prime factorization of $p-1$ (odd part constraints). Prove exact classifications in degenerate cases ($k=0$, $q=2$). Then do a "FAST REALITY CHECK" by enumerating primes $p\le N$ satisfying each condition for several $N$.

WORK

Lemma 1065.1 (the $k=0$ case is unique). If $p$ and $q$ are primes and $p=q+1$, then $(q,p)=(2,3)$.

Proof. If $q=2$ then $p=3$ is prime, giving one solution. Assume $q>2$. Then $q$ is odd, so $p=q+1$ is an even integer strictly larger than $2$, hence not prime. Therefore no solutions exist with $q>2$, and the only solution is $(q,p)=(2,3)$. $\square$

Lemma 1065.2 (the $q=2$ subfamily equals Fermat-type primes). Let $p$ be prime. Then $p=2^k q+1$ with $q=2$ and $k\ge 0$ holds if and only if $p$ is of the form $p=2^m+1$ with $m\ge 1$.

Proof. If $q=2$, then $p = 2^k\cdot 2 + 1 = 2^{k+1}+1$, so $p=2^m+1$ with $m=k+1\ge 1$. Conversely, if $p=2^m+1$ with $m\ge 1$, then writing $m=k+1$ gives $p=2^k\cdot 2+1$, i.e. $q=2$. $\square$

Lemma 1065.3 (factorization reformulation). Let $p$ be an odd prime and write $p-1=2^{v_2(p-1)}\,\mathrm{odd}(p-1)$ where $\mathrm{odd}(p-1)$ is the odd part. Then $p=2^k q+1$ for some prime $q$ and some $k\ge 0$ if and only if $\mathrm{odd}(p-1)$ is either $1$ or a prime. Moreover, the representation is unique:

• if $\mathrm{odd}(p-1)$ is an odd prime, then necessarily $k=v_2(p-1)$ and $q=\mathrm{odd}(p-1)$;
• if $\mathrm{odd}(p-1)=1$ (so $p-1$ is a power of $2$), then necessarily $q=2$ and $k=v_2(p-1)-1$.

Proof. ($\Rightarrow$) Suppose $p-1=2^k q$ with $q$ prime. If $q$ is odd then $\mathrm{odd}(p-1)=q$ is prime. If $q=2$ then $p-1$ is a pure power of $2$, hence $\mathrm{odd}(p-1)=1$. In either case $\mathrm{odd}(p-1)\in\{1\}\cup\{\text{primes}\}$.

($\Leftarrow$) If $\mathrm{odd}(p-1)$ is an odd prime $q$, then $p-1=2^{v_2(p-1)}q$ gives $p=2^{v_2(p-1)}q+1$. If $\mathrm{odd}(p-1)=1$, then $p-1=2^m$ where $m=v_2(p-1)\ge 1$ (since $p$ is odd). Then \[ p-1 = 2^{m-1}\cdot 2, \] so $p=2^{m-1}\cdot 2 + 1$ with $q=2$ and $k=m-1$.

For uniqueness: if $\mathrm{odd}(p-1)$ is an odd prime and $p-1=2^{k'}q'$ with $q'$ prime, then $q'$ must be odd (otherwise $q'=2$ forces $\mathrm{odd}(p-1)=1$), so $2^{k'}$ must be the full power of $2$ dividing $p-1$, hence $k'=v_2(p-1)$ and $q'=\mathrm{odd}(p-1)$. If $\mathrm{odd}(p-1)=1$ and $p-1=2^{k'}q'$ with $q'$ prime, then $q'$ must be $2$ and $k'=v_2(p-1)-1$. $\square$

Lemma 1065.4 (analogous reformulation for $2^k3^\ell q$). Let $p$ be prime. Then $p=2^k3^\ell q+1$ for some $k,\ell\ge 0$ and prime $q$ if and only if, after removing all factors of $2$ and $3$ from $p-1$, the remaining factor is either $1$ or a prime.

Proof. Write $p-1 = 2^a3^b r$ where $\gcd(r,6)=1$. If $r$ is prime, take $(k,\ell,q)=(a,b,r)$. If $r=1$, then $p-1=2^a3^b$; if $a\ge 1$ take $(k,\ell,q)=(a-1,b,2)$, and if $a=0$ then $b\ge 1$ and take $(k,\ell,q)=(0,b-1,3)$. Conversely, any representation $p-1=2^k3^\ell q$ has $r=q$ after removing all $2,3$ factors, hence $r$ is $1$ or prime. $\square$

FAST REALITY CHECK (computation). I enumerated primes $p\le N$ and tested the conditions by factoring $p-1$ and checking whether it can be written as $2^k q$ with $q$ prime, and similarly $2^k3^\ell q$ with $q$ prime. Exact results: \[ \begin{array}{r|r|r|r|r} N & \#\{p\le N\} & \#\{p\le N: p=2^k q+1\} & \#\{p\le N: p=2^k3^\ell q+1\} & \text{fractions} \\ \hline 10^3 & 168 & 59 & 117 & 0.351,\ 0.696 \\ 10^4 & 1229 & 257 & 580 & 0.209,\ 0.472 \\ 10^5 & 9592 & 1470 & 3264 & 0.153,\ 0.340 \\ 10^6 & 78498 & 9287 & 20479 & 0.118,\ 0.261 \end{array} \] The first few primes $p$ satisfying $p=2^kq+1$ (with their $(k,q)$) are: \[ 3\,(0,2),\ 5\,(1,2),\ 7\,(1,3),\ 11\,(1,5),\ 13\,(2,3),\ 17\,(3,2),\ 23\,(1,11),\ 29\,(2,7),\ 41\,(3,5),\ldots \] (Computed by a minimal script using primality testing and dividing $p-1$ by successive powers of $2$ and $3$.)

VERIFICATION

Lemma 1065.1 is a parity argument and is complete. Lemma 1065.2 is algebraic and complete. Lemma 1065.3 is checked by the standard $2$-adic valuation decomposition of $p-1$; it shows that $p=2^kq+1$ with $q$ prime holds exactly when the odd part of $p-1$ is $1$ or prime, and it records the (case-by-case) uniqueness of $(k,q)$. Lemma 1065.4 follows by extracting maximal powers of $2$ and $3$. The computational table was obtained by direct enumeration of primes and exact arithmetic on $p-1$.

FINAL

UNRESOLVED.

(i) Strongest proved partial result: The problem reduces to the arithmetic of $p-1$: for odd primes $p$, the condition $p=2^kq+1$ holds exactly when the odd part of $p-1$ is either $1$ or prime (equivalently, $p-1$ has at most one odd prime factor) (Lemma 1065.3), with complete classification of the degenerate cases $k=0$ and $q=2$ (Lemmas 1065.1--1065.2). Analogously, $p=2^k3^\ell q+1$ holds exactly when $(p-1)/2^{v_2(p-1)}3^{v_3(p-1)}$ is $1$ or prime (Lemma 1065.4). Computations up to $10^6$ give the exact counts recorded above.

(ii) First gap (crisp statement): Prove (or disprove) that there are infinitely many primes $p$ for which the odd part of $p-1$ is either $1$ or prime (equivalently, infinitely many primes $p$ with $p-1=2^k q$ for some prime $q$).

(iii) Top 3 next moves (concrete lemmas/computations):

1. Study fixed-$k$ subfamilies: for each fixed $k\ge 1$, attempt to show infinitely many primes of the form $p=2^k q+1$ with $q$ prime (even $k=1$ is already a central special case).
2. For the $2^k3^\ell q+1$ variant, attempt to control primes $p$ for which $(p-1)$ has at most one prime factor outside $\{2,3\}$; a first concrete step is to obtain nontrivial lower bounds on the count of such primes up to $N$.
3. Extend the computations (e.g. to $N\approx 10^8$ if feasible) and record empirical densities as a function of $\log N$, plus the distribution of $(v_2(p-1),v_3(p-1))$ among the solutions.

(iv) Minimal counterexample structure: If only finitely many such primes exist, then there is a bound $P_0$ such that for every prime $p>P_0$, $p-1$ has at least two distinct odd prime factors (for the first question), and for the second question $p-1$ has at least two prime factors outside $\{2,3\}$.