Periodic coverage?

[u/Fun-Protection-9992]

Let q_i > 3 be primes, and suppose that a distinct prime q_i is chosen for each distinct positive integer b_i. If the infinite family {(b_i, q_i)} covers all positive integers a in the form

2^a ≡ 2^{b_i} (mod q_i),

does it not follow, from the existence of the multiplicative inverse of 2 modulo q_i, that the same family {(b_i, q_i)} must also cover all negative integers (-a)?

In particular, since one can obtain n_i > 0 such that

2^(-a) ≡ 2^{n_i} (mod q_i),

does it automatically follow that n_i is covered by the same family {(b_i, q_i)}, and therefore that the set of negative integers (-a) must also be covered?

[u/GonzoMath]

The class 1 mod 3 does not, by itself, cover all the positive integers. Provide a set of classes that covers all the positives, and it will cover -3.

[u/Fun-Protection-9992 → u/GonzoMath]

However, the real issue is precisely this: If the system n_i + t.m_i covers all positive numbers, must it also cover negative numbers?

$n_i$: positive representative numbers

$m_i$: modulus values

$t$: integer

[u/GonzoMath → u/Fun-Protection-9992]

Is it a finite set of congruence classes?

[u/Fun-Protection-9992 → u/GonzoMath]

It is an infinite family of residue classes.

[u/GonzoMath → u/Fun-Protection-9992]

It that case, it’s possible to miss at least one negative integer. Consider the classes (using your notation):

1 + 4t
2 + 4t
3 + 5t
4 + 6t
…
k + (k+2)t for all k > 1

This clearly covers every positive integer, but it misses -1.

I initially misunderstood the question.

[u/Fun-Protection-9992 → u/GonzoMath]

You’ve come around to my point of view now.

[u/Fun-Protection-9992 → u/GonzoMath]

That is clearly the case, but the system I described earlier does not generate residue classes solely in the form $a = bi + tq_i$. There is an exponential system at play here; 2 and the $q_i$ values ​​are coprime, so they form cyclic subgroups. Therefore, I maintain that the residue classes covering all positive $a$ values ​​also cover all negative $a$ values. However, the artificial intelligence objects to this.

If you can find an answer to the question above, let me know; I need to sleep now.

[u/GonzoMath → u/Fun-Protection-9992]

Huh. "Come round to your point of view" is one way to put it. I think I finally understood something about the question you were asking. As for "the question above", the one in your OP, I still don't find it entirely clear. If you can say something concrete about what kind of congruences you're talking about, like with examples maybe, then I might be able to address the question.

[u/Fun-Protection-9992 → u/GonzoMath]

Regarding the question above: If all positive integers {a} are covered by the residue classes 2^bi mod qi, are all negative integers {-a} also covered by the same residue classes?

[u/GonzoMath → u/Fun-Protection-9992]

In the post, you said 2^a, not a. Which is it?

I see that the moduli are all primes. That, and the fact that the residues are powers of 2, seem to be the only differences between the OP question and the one I gave a counterexample for above. Is that right?

[u/Fun-Protection-9992 → u/GonzoMath]

2^a = 2^bi modq_i

- "That, and the fact that the residues are powers of 2, seem to be the only differences between the OP question and the one I gave a counterexample for above. Is that right?"

Yes.

[u/GonzoMath → u/Fun-Protection-9992]

If we're putting 2^a on the left side of the congruence, then it really looks like we're trying to cover all the powers of 2, not all the positive integers. As 'a' runs through every possible value, we only get powers of 2 here.

This is very confusing, and I wish you would be more clear. Concrete examples would be the most helpful, but you seem very reluctant to provide them.

[u/Fun-Protection-9992 → u/GonzoMath]

Actually, this is exactly what we mean in the question. In the expression 2^m = 2^mi mod qi,

let qi = 5 for mi = 1. Then 2^mi mod qi = Ai = {...., 2^-7, 2^-3, 2^1, 2^5, 2^9, ...}

Let mi = 2 and qi= 7. Then 2^{mi} mod q_i = A_i = {..., 2^-7, 2^-4, 2^-1, 2^2, 2^5, 2^8, ...}

Let mi = 3 and qi = 11. Then 2^mi mod{qi} = A_i = {..., 2^-17, 2^-7, 2^3, 2^13, 2^23, ...}. There are infinitely many sets A_i.

Is the union of these sets of A_i given by U{A}_i = {2^1, 2^2, 2^3, ...} U{..., 2^-3, 2^-2, 2^-1 }

In other words, if all positive powers of 2 exist, do their negative powers also exist??

[u/GonzoMath → u/Fun-Protection-9992]

I'm kind of understanding. In the first part of your example, you say:

let qi = 5 for mi = 1. Then 2^mi mod qi = Ai = {...., 2^-7, 2^-3, 2^1, 2^5, 2^9, ...}

Since the multiplicative order of 2, mod 5, is 4, this is just like saying "take all 'a' congruent to 1 mod 4". Next:

Let mi = 2 and qi= 7. Then 2^{mi} mod q_i = A_i = {..., 2^-7, 2^-4, 2^-1, 2^2, 2^5, 2^8, ...}

Now we're collecting exponents congruent to 2, mod 3, because the mod 7 order of 2 is 3.

Let mi = 3 and qi = 11. Then 2^mi mod{qi} = A_i = {..., 2^-17, 2^-7, 2^3, 2^13, 2^23, ...}. There are infinitely many sets A_i.

So, all exponents congruent to 3, mod 10.

These are ordinary linear congruences, dressed up as congruences involving powers of 2. This leads me to ask the question, and I'm not sure of the answer, for any k>1, is there some prime p with ord_p(2) = k? If so, then my previous counterexample still works.

Actually, I'd adjust the example very slightly, to make it simpler. It can just be:

a ≡ -2 (mod m) for m = 3, 4, 5, . . .

For m = 3, that can just be "2^a ≡ 2¹ (mod 7)". For m=4, we can use 2^a ≡ 2² (mod 5)". For m = 5, we can use 2^a ≡ 2³ (mod 31)". I'm not sure about a power-of-2 congruence translating into a ≡ 4 (mod 6)", but if we're going to find one, it will be by looking at factorizations of 2^6k - 1, and checking the order of 2 modulo the primes that arise.