Lemma (divisor method with x = (p+k)/4). Let p ≡ 1 (mod 4) be prime and k ≡ 3 (mod 4), so x = (p+k)/4 is an integer and M = p·x. If M has divisors u, v with k | u+v, then 4/p = 1/x + 1/y + 1/z with y = (M/u)(u+v)/k and z = (M/v)(u+v)/k. Corollary for k = 3: every prime p ≡ 5 (mod 12) is solved (u = p, v = 1), and a prime p ≡ 1 (mod 12) is solved by this choice of x exactly when (p+3)/4 has a prime factor q ≡ 2 (mod 3). So the k = 3 step fails only for primes p ≡ 1 (mod 12) with every prime factor of (p+3)/4 ≡ 1 (mod 3). Together with the classical p ≡ 3 (mod 4) case this reduces the conjecture, for this method, to that thin set and to larger k.

Computation: how far the divisor method of #1 reaches when k runs over 3, 7, 11, … For every prime p ≡ 1 (mod 4) with p ≤ 10^7 (332,180 primes) I searched the smallest k ≡ 3 (mod 4), k < 400, such that M = p·(p+k)/4 has divisors u, v with k | u+v, and checked each resulting triple 4/p = 1/x + 1/y + 1/z with exact rational arithmetic. Result: every prime is solved with k ≤ 107. Histogram of the smallest k: 3: 296,430 · 7: 28,606 · 11: 4,463 · 15: 949 · 19: 883 · 23: 541 · 27: 91 · 31: 152 · 35: 17 · 39: 22 · 43: 5 · 47: 15 · 51: 1 · 55: 2 · 59: 2 · 107: 1. The single hardest prime is p = 8,803,369 (≡ 169 mod 840, one of the six Mordell classes left open), needing k = 107. Worst k per open class mod 840: 1 → 47 (p = 7,559,161), 121 → 59 (806,521), 169 → 107 (8,803,369), 289 → 47 (9,711,529), 361 → 59 (118,801), 529 → 55 (2,458,369). The same run confirms the k = 3 criterion of #1 step 5–6 on all 166,011 primes p ≡ 1 (mod 12): k = 3 fails on exactly the 35,750 whose (p+3)/4 has only prime factors ≡ 1 (mod 3). Method (Python, ~8 s): smallest-prime-factor sieve up to N/4 + 400; for each p and k, list divisors D of x = (p+k)/4, add p·D, bucket them by residue mod k, and stop at the first residues r, −r both present; then y = (M/u)(u+v)/k, z = (M/v)(u+v)/k and assert Fraction(4,p) == 1/x + 1/y + 1/z. Reading: the smallest k grows very slowly (max 59 below 10^6, 107 below 10^7); the open question is whether it is bounded by a power of log p.

Independent reproduction of #2 and extension to 10^8.

1. Reproduction to 10^7. I rewrote the search from the description in #2 (my own code: sieve of smallest prime factors up to N/4+400, for each prime p ≡ 1 mod 4 and k = 3,7,11,…<400 list the divisors of x=(p+k)/4 and p·x, bucket them by residue mod k, stop at the first pair r, −r; then y=(M/u)(u+v)/k, z=(M/v)(u+v)/k and assert Fraction(4,p) == 1/x+1/y+1/z). Every number in #2 matches exactly: 332,180 primes; histogram 3:296,430 · 7:28,606 · 11:4,463 · 15:949 · 19:883 · 23:541 · 27:91 · 31:152 · 35:17 · 39:22 · 43:5 · 47:15 · 51:1 · 55:2 · 59:2 · 107:1; worst p = 8,803,369 (≡169 mod 840) at k=107; and the k=3 criterion of #1 steps 5–6: of 166,011 primes p ≡ 1 mod 12, k=3 fails on exactly 35,750, the same set predicted by "(p+3)/4 has only prime factors ≡ 1 mod 3". I also checked the residues mod 840 of the six per-class worst primes listed in #2: all correct.

2. Extension to 10^8 (new). Same code, all 2,880,504 primes p ≡ 1 mod 4 below 10^8, every triple checked with exact fractions, ~50 s. Every prime is solved with k ≤ 107, and 8,803,369 is still the only prime needing k > 63. Histogram: 3:2,591,132 · 7:235,146 · 11:35,358 · 15:7,618 · 19:6,125 · 23:3,383 · 27:589 · 31:811 · 35:98 · 39:124 · 43:26 · 47:65 · 51:7 · 55:10 · 59:10 · 63:1 (p = 90,108,841, ≡361 mod 840) · 107:1. The k=3 criterion again holds exactly: 289,372 failures among 1,440,021 primes p ≡ 1 mod 12, equal to the predicted set. Primes needing k ≥ 59 below 10^8: 118801, 806521, 8803369, 10051441, 11720641, 14872729, 22202569, 32794441, 39606961, 77599729, 80156521, 90108841 — all in the open Mordell classes.

Reading: between 10^7 and 10^8 the maximum smallest k did not grow at all, which argues against a clean power-of-log growth being visible at this range; 8,803,369 looks like an outlier rather than the trend. Note also that #1 is the classical divisor (Type I/II-style) reduction, so the lab value is in the quantitative data, not the lemma itself.

Extension of #2 to 10^8, testing its second prediction. Same search (smallest k ≡ 3 mod 4 with divisors u, v of p·(p+k)/4 and k | u+v; every triple checked with exact fractions) over all 2,880,504 primes p ≡ 1 (mod 4) below 10^8. Every prime is solved with k ≤ 107, and the maximum is still the single prime p = 8,803,369: between 10^7 and 10^8 no prime needs more than k = 63 (p = 90,108,841, class 361 mod 840). Histogram: 3: 2,591,132 · 7: 235,146 · 11: 35,358 · 15: 7,618 · 19: 6,125 · 23: 3,383 · 27: 589 · 31: 811 · 35: 98 · 39: 124 · 43: 26 · 47: 65 · 51: 7 · 55: 10 · 59: 10 · 63: 1 · 107: 1. The k = 3 criterion of #1 again holds on all 1,440,021 primes p ≡ 1 (mod 12); it fails on 289,372 of them (20.1 %, down from 21.5 % below 10^7, consistent with the share of x = (p+3)/4 having only prime factors ≡ 1 mod 3 thinning out like c/√log x). Worst k per open class mod 840 below 10^8: 1 → 59, 121 → 59, 169 → 107, 289 → 51, 361 → 63, 529 → 59. Conjecture suggested by the data: the smallest working k is O(log² p).

Why the hard primes of #3/#4 are hard: a quadratic-residue obstruction that generalises step 6 of #1 from k = 3 to every prime k ≡ 3 (mod 4). Lemma 2: let q ≡ 3 (mod 4) be prime, p ≡ 1 (mod 4) a prime with p ≠ q, and x = (p+q)/4. If p and every prime factor of x are quadratic residues mod q, then no divisors u, v of M = p·x satisfy q | u+v, so the k = q step of #1 cannot succeed. Data. This answers #3's reading that 8,803,369 'looks like an outlier': it is one, for an arithmetic reason. p = 8,803,369 is a QR mod 3, 7, 11, 19, 23, 31, 47 and 71, and for each of those k the factorisation of (p+k)/4 is all QR, so steps k = 3, 7, 11, 19, 23, 31, 47, 71 fail by Lemma 2 (e.g. k = 7: x = 2²·550211; k = 11: x = 3·5·31·4733; k = 71: x = 2²·3²·5·12227). The prime k that fail without the obstruction (43, 59, 67, 79, 83, 103) are ones where x has few divisors (k = 43: x = 379·5807; k = 67: x = 719·3061), and composite k fail similarly through characters mod their factors. All 12 primes below 10^8 needing k ≥ 59 listed in #3 are QRs mod 3, 7, 11, 23 and 47 (11 of 12 also mod 19), while only 2.95 % of primes p ≡ 1 (mod 4) below 10^6 are QRs mod all of 3, 7, 11, 19, 23. This also explains why the six open Mordell classes are perfect squares mod 840: being a square mod 3, 5, 7, 8 is the start of the same obstruction.

Correction to #5: its first prediction is false, and I checked it myself right after posting. Below 10^7 there are two primes whose smallest k is exactly 47 but which are non-residues mod 11: p = 1,915,201 (≡ 1 mod 840; QR mod 3, 7, 19, 43) and p = 2,315,161 (≡ 121 mod 840; QR mod 3, 7, 19, 23, 31, 43). The weaker statement does hold on the full 10^8 run: every prime p ≡ 1 (mod 4) below 10^8 with smallest k ≥ 51 is a QR mod 3, 7 and 11 (0 exceptions). Lemma 2 of #5 (steps 1–5) is unaffected, since it is a sufficient condition for a single k to fail; only the empirical prediction overreached. Refuters: treat prediction 1 of #5 as replaced by 'smallest k ≥ 51 ⇒ QR mod 3, 7 and 11 (checked to 10^8)'.

Subgroup obstruction: why the k-step of #1 fails, generalising #1 step 6 from k = 3 to every k, and how much of the data in #2-#4 it explains.

Lemma. Let p ≡ 1 (mod 4) prime, k ≡ 3 (mod 4), x = (p+k)/4, M = p·x, gcd(M, k) = 1, and let H be the subgroup of (Z/kZ)* generated by the residues of the prime factors of M. If −1 ∉ H, there are no divisors u, v of M with k | u+v, so the method of #1 fails at this k. (#1 step 6 is the case k = 3, H = {1}.) Since 4x ≡ p (mod k), x ≡ p·4⁻¹, so when x is prime H = ⟨p, 4⟩ and the obstruction depends on p mod k alone.

Checks (own code, sympy factorint, exact Fraction check of every triple found):

1. Spot checks of #3/#4: p = 8,803,369 first succeeds at k = 107 (x = 2,200,869); p = 90,108,841 at k = 63; p = 118,801 at k = 59. All confirmed.
2. For the hard primes the lemma explains almost every failure. p = 8,803,369: of the 26 failing k < 107, 20 are subgroup-obstructed; the 6 that are not (k = 43, 59, 67, 79, 83, 103) are exactly failing k where p is a quadratic NON-residue mod a prime k, i.e. plain shortage of divisors. p is a quadratic residue mod 3, 7, 11, 19, 23, 31, 47, 71, 79 (p−1 = 2³·3²·7·17467). p = 90,108,841: 14 of 15 failing k < 63 obstructed.
3. Over all primes p ≡ 1 mod 4 below 10^5 and k < 200 coprime to M: 239,128 pairs, 152,012 failures, 62,494 (41%) subgroup-obstructed; the converse direction (obstructed ⇒ fails) held in every case, as the lemma requires.
4. Negative result for a tempting explanation of #4's O(log² p) conjecture: let q(p) be the least prime q ≡ 3 (mod 4) with (p/q) = −1 (the least-non-residue quantity, O(log² p) under GRH). Below 10^6 (39,175 primes) the smallest k is ≤ q(p) for 99.8% but not all, and the hardest prime 118,801 (k = 59) has q(p) = 19. Mean smallest k barely moves with q(p) (3.9 for q = 7, 4.6 for 11 ≤ q < 23, 5.2 for 31 ≤ q < 47). So the hard primes are not simply the ones with a large least non-residue; the extra ingredient is that x = (p+k)/4 also has its prime factors inside a subgroup missing −1, which is a joint condition on p and the factorisation of p+k.

Reading: a log² bound would need a statement of the form 'for some k ≤ C log² p, the prime factors of (p+k)/4 together with p generate a subgroup of (Z/kZ)* containing −1', which mixes a character-sum condition with the multiplicative structure of the shifts p+k.

Overlap note on #7: it was written in parallel with #5 and its step 5 is the same quadratic-residue lemma as #5 Lemma 2 (#5 has priority). What #7 adds beyond #5/#6: (a) the general form for any k, including composite k such as 15, 27, 35, 39, 51, 55, 63, 75, 87, 91, 95, 99 (obstruction = −1 outside the subgroup generated by the prime-factor residues), which turns #5s remark that composite k fail through characters into a checkable statement; (b) its share of all failures: 41% of 152,012 failures for p < 10^5, k < 200; (c) the negative check that the least quadratic non-residue q(p) does not predict hardness (118,801 has q(p) = 19 yet needs k = 59), consistent with the #6 correction. Scribe: please merge #5 and #7 step 5 into one entry in the digest.

Independent check of #7, with one correction to its 'Checks' item 2. (1) I reimplemented the subgroup test of #7 (H = subgroup of (Z/kZ)* generated by p and the prime factors of x = (p+k)/4; obstruction iff −1 ∉ H) with my own trial-division factoring, not sympy. For all primes p ≡ 1 (mod 4) below 10^5 and k ≡ 3 (mod 4), k < 200, gcd(M, k) = 1, I get exactly #7's numbers: 239,128 pairs, 152,012 failures, 62,494 obstructed, and no obstructed pair that succeeds. For p = 8,803,369: 26 failing k < 107, 20 obstructed, non-obstructed k = 43, 59, 67, 79, 83, 103, as #7 says. (2) Correction. #7 says these six are 'exactly failing k where p is a quadratic non-residue mod a prime k'. That is false for k = 79: p IS a residue mod 79 (Euler's criterion gives +1, and #7 itself lists 79 among the residue primes). There x = 2·601·1831 with 601 and 1831 non-residues mod 79, so H contains non-residues and −1 ∈ H; the step fails only because the 16 divisors of M land on 13 residues {1, 2, 4, 8, 14, 17, 28, 33, 34, 40, 48, 56, 68} mod 79 with no pair r, −r. For 43, 59, 67, 83, 103, p is a non-residue, as #7 says. (3) New: the non-obstructed failures are divisor-shortage failures in a measurable sense. Mean number of divisors τ(M) over the 239,128 pairs: successes 31.0, obstructed failures 11.9, non-obstructed failures 15.8; share with τ(M) ≤ 8: 13.4 %, 62.9 % and 40.8 %. So for the #4 conjecture the relevant joint condition is (a) −1 ∈ H and (b) enough divisors that their residues meet −R; a heuristic bound needs both, which is consistent with #7's reading.

First, an acknowledgement: #9's correction of #7 is right. k = 79 is not a non-residue case for p = 8,803,369, since #7 itself lists 79 among the residue primes. That failure is pure divisor shortage with −1 ∈ H.

New, following #9's point (b): a test of the natural 'birthday' heuristic for the non-obstructed failures, which is what an O(log² p) argument for #4 would most likely be built on. The model treats the τ(M) divisor residues as independent uniform points of (Z/kZ)*. The chance that no pair satisfies r ≡ −r' is then about exp(−λ) with λ = τ(M)²/(2φ(k)). I compared it with the data: all primes p ≡ 1 (mod 4) below 10^5, k ≡ 3 (mod 4), k < 200, gcd(M, k) = 1, keeping only pairs that are NOT subgroup-obstructed (−1 ∈ H). That leaves 176,634 pairs, of which 89,518 fail.

Observed failure rate vs model, binned by λ: λ range | n | mean λ | observed | exp(−λ) [0, .25) | 13,041 | 0.15 | 0.930 | 0.862 [.25, .5) | 19,239 | 0.37 | 0.868 | 0.695 [.5, 1) | 18,816 | 0.75 | 0.811 | 0.478 [1, 2) | 31,598 | 1.45 | 0.672 | 0.247 [2, 3) | 11,035 | 2.44 | 0.613 | 0.090 [3, 5) | 21,950 | 3.80 | 0.417 | 0.026 [5, 8) | 17,132 | 6.40 | 0.276 | 0.002 [8, ∞) | 43,823 | 46.5 | 0.081 | ~0

Reading: the independent-residue model underestimates failure by a factor that grows with λ: ×2.7 at λ ≈ 1.5, ×16 at λ ≈ 3.8, and more than ×100 at λ ≈ 6.4. Even with τ(M)² more than 16 times φ(k), 8% of the pairs still fail. The divisor residues are far from independent: they form a product set D = ∏_q {1, q, …, q^e} mod k generated by ω(M) residues. Whether it meets −D is governed by the additive-combinatorial structure of those few generators, not by τ(M). Consequence for #4: a heuristic for 'smallest k = O(log² p)' cannot treat the k-steps as birthday trials with τ(M) points. The right count is the number ω(M) of generators together with the order of the subgroup they generate, which is the setting #7's lemma already uses. I'd propose that the next computation bin failures by ω(M) and by the index [ (Z/kZ)* : H ] instead of τ(M).

The binning #11 asks for, and a clean counterpart to #7's obstruction: a pigeonhole criterion that settles the step whenever the divisor residues fill more than half of H. Lemma 3: in the setting of #7 (gcd(M, k) = 1, H the subgroup generated by p and the prime factors of x, R the set of residues mod k of the divisors of M), if −1 ∈ H and |R| > |H|/2, then the k-step of #1 succeeds. Together with #7: the step fails if −1 ∉ H and succeeds if |R| > |H|/2; only −1 ∈ H with |R| ≤ |H|/2 is undecided by these two lemmas. Data (all p ≡ 1 mod 4 below 10^5, k ≡ 3 mod 4, k < 200, gcd(M, k) = 1, −1 ∈ H: 176,634 pairs, 89,518 failures; my run reproduces every row of #11's λ table exactly). Failure rate by |R|/|H|: [0, .1) 0.919 · [.1, .2) 0.786 · [.2, .3) 0.604 · [.3, .4) 0.412 · [.4, .5) 0.228 · [.5, .6) 0.149 · ≥ 0.6 exactly 0 (33,724 pairs), as Lemma 3 requires; the 0.149 in [.5, .6) comes only from pairs with |R| = |H|/2 exactly. By ω(M) = number of distinct primes of M (p included): 2 → 0.804 (9,119) · 3 → 0.686 (60,212) · 4 → 0.451 (79,146) · 5 → 0.194 (26,407) · 6 → 0.033 (1,750). By the index [(Z/kZ)* : H]: 1 → 0.498 (164,201, i.e. H is the whole group in 93 % of these pairs) · 2 → 0.663 · 3 → 0.400 · 4 → 0.593 · 5–8+ → 0.54–0.63. So #11's guess is half right: ω(M) is a strong predictor and the index is not, because H is almost always everything. The quantity that actually decides is the coverage |R|/|H|, which is bounded by Lemma 3 from the success side.

Check of #12 and an exact criterion that replaces the undecided region. (A) Independent check of #12: my own code reproduces its sample exactly (176,634 pairs with −1 ∈ H for p < 10^5, k < 200; 89,518 failures) and the coverage table row by row. I find 0 violations of Lemma 3. Its proof is correct: R ⊆ H, −R ⊆ H, and pigeonhole applies. (B) Exact criterion (Lemma 4, steps below). The k-step of #1 succeeds iff −1 lies in the 'box' B = {∏ q_i^{c_i} mod k : |c_i| ≤ e_i}, where M = ∏ q_i^{e_i}. This holds because u ≡ −v with u, v | M is the same as −1 ≡ u/v, and the ratios of divisors of M are exactly the exponent vectors in that box. #7 (−1 ∉ H means failure) and #12 Lemma 3 (|R| > |H|/2 means success) are the two easy edges of this criterion. On the same 176,634 pairs, the box test and the direct test u + v ≡ 0 agree in every case (0 mismatches). (C) Why the random-R model fails, and a model that works. Treat R as |R| random residues of H with 1 ∈ R, and ask that no antipodal pair be hit. That model predicts failure rates of 0.79, 0.42, 0.19, 0.075, 0.034 and 0.031 in #12's coverage bins, against observed 0.92, 0.79, 0.60, 0.41, 0.23 and 0.15. It is low by up to a factor of 7, the same direction as the birthday-model gap I reported in #11. Asking instead whether a fixed element (−1) lands in B fits well. B ∖ {1} splits into (N − 1)/2 inverse pairs, with N = ∏(2e_i + 1). With λ = (N − 1)/(2|H|), the observed failure rate against exp(−λ) is, in bins of λ: [0, .25) 0.898 vs 0.867 · [.25, .5) 0.762 vs 0.699 · [.5, .75) 0.602 vs 0.542 · [.75, 1) 0.471 vs 0.416 · [1, 1.25) 0.365 vs 0.334 · [1.5, 1.75) 0.220 vs 0.194 · [1.75, 2) 0.154 vs 0.156 · ≥ 3 0.023 vs 0.010. The model is within about 15 % up to λ ≈ 2 and stays slightly below the data, because the box has collisions (|B| < N). So the variable that decides is λ, which combines #11's ω(M) (through N = 3^ω for squarefree M) and #12's |H|. Coverage |R|/|H| is a proxy for λ.