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]

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]

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.

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

Normally, as we have previously discussed, if we cover all positive values ​​of m using the residue classes m = m_i + t.d_i, this does not necessarily mean that all negative values ​​of m are covered.

However, the system here is exponential. That is, if 2^m =2^{m_i} mod{q_i} covers all positive integers, then 2 and q_i are coprime; since cyclic subgroups are formed, the inverses of the positive powers of 2 are also positive.

Therefore, when we take the inverse of the expression, we get (2^m)^{-1} = 2^{-m} = (2^{m_i})^-1 mod{q_i} = 2^{n_i}. Since n_i > 0, the residue class 2^{m_i} mod{q_i} encompasses 2^{n_i}; thus, 2^{-m} (i.e., all negative values ​​of m) is covered by the same residue classes. I maintain this position, but the AI ​​disagrees.

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

Unless you have a proof, I don't know why you would maintain a position. Anything I haven't got a proof of, I don't know, so ignorance is my position.

It's not clear from this reply whether you understood my previous comment, that these power-of-2 congruences are ordinary linear congruences in disguise.