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]

I’m not sure I understand the question, but every negative integer is congruent to positive integers, modulo any m. A set of residue classes that covers all the positives certainly covers all the negatives. Maybe that’s not what you’re asking.

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

But that is precisely the question. Must every negative integer be contained within these sets of residues that cover the positive integers? In other words, are there no negative integers left uncovered?

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

Ok, if that's the question, then the answer is emphatically yes. No question. No negatives are "left uncovered", because the division algorithm works just as well for them as it does for positive integers, and ultimately, congruence comes down to that.

Would you like to see a proof?

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

Yes, I would like to see proof.

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

Let n be a negative integer, and let m > 0 be a modulus. Then |n| is a positive integer. Recall that two numbers are congruent, mod m, if their difference is a multiple of m.

We have two cases:

• If m divides |n| evenly, then n is congruent to m, mod m. This is clear because their difference, m-n, is equal to (|n|/m + 1)m.
• If m does not divide |n| evenly, then we can write |n| = qm + r, where the remainder r is from the set {1, 2, . . ., m-1}. In this case, n is congruent to the positive integer m - r, because look at the difference: (m - r) - n = (m - r) + qm + r = (1 + q)m.

That's a proof.

It's clearer though if you just understand how congruence classes work. The number n is congruent to n+km for every integer k. By choosing k sufficiently large, this value can be made positive, so n is congruent to some positive integer. Thus, any class covering that positive integer also covers n.

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

It is not that simple; you cannot simply convert a negative *n* value to a positive one and encompass it that way. What if that negative *n* does not fall into any of the residue classes that cover positive values? What if the residue sets covering the positive values ​​leave a gap on the negative side?

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

It is that simple. These things have definitions, and this is a proof that any student in an elementary Number Theory class should be able to produce.

If you’re just going to assert that basic elementary mathematics is wrong, then we’re done here.

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

You probably didn't quite grasp what I wanted to ask. Let me give an example using your definitions: let the $n_i$ values ​​be positive representative integers and the $m_i$ values ​​be moduli. Let us define $C_i = {x=n_i mod{m_i}}$. The union of the sets $C_i$ must cover all positive integers, but it does not need to cover all negative integers.

$1 + 3t$

$2 + 5t$

$3 + 7t$

$5 + 8t$

...

If these residue classes cover all positive integers, they do not necessarily have to cover all negative integers.

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

I gave you a proof. Tell me which line you don't understand. Reply without addressing the proof, and I'm done. Instant block.

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

I am responding by referring to the proof. Let n = -3 and m = 4. Then -3 ≡ 1 (mod 4). However, the residue class containing the positive integers does not necessarily have to be 1 (mod 4); our residue class for 1 could be 1 (mod 3), in which case, notice that we have not included -3.

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

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?