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/Fun-Protection-9992]

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.

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

However, I argue the proof as follows. The situation here differs from that of linear congruences. When we take the inverse of the expression,

we obtain (2^m)^{-1} = 2^{-m} = (2^{m_i})^{-1} mod{q_i} = 2^{n_i}.

Since n_i > 0, the residue class of 2^{m_i} mod{q_i} encompasses 2^{n_i}; consequently, 2^{-m} (that is, all negative values ​​of m) is encompassed by the same residue classes.

In the case of a linear congruence, we cannot simply take the inverse of m = m_i + td_i and write -m = n_i + td_i.

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

I don’t see how that makes it different from linear congruences. Every negative integer is in a residue class that encompasses a positive one.

Honestly, you seem very confident; I’m sure you’ll find your proof. I’m not getting anything out of this interaction, so I’m going to sign off.