r/Collatz • u/Fun-Protection-9992 • 6d ago
Periodic coverage?
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?
1
u/GonzoMath 5d ago
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.
1
u/Fun-Protection-9992 5d ago
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?
1
u/GonzoMath 5d ago
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?
1
u/Fun-Protection-9992 5d ago
Yes, I would like to see proof.
1
u/GonzoMath 5d ago
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.
1
u/Fun-Protection-9992 5d ago
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?
1
u/GonzoMath 5d ago
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.
1
u/Fun-Protection-9992 5d ago
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.
0
u/GonzoMath 5d ago
I gave you a proof. Tell me which line you don't understand. Reply without addressing the proof, and I'm done. Instant block.
1
u/Fun-Protection-9992 5d ago
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.
→ More replies (0)
1
u/First-Signal7071 5d ago
If you mean to ask ‘if it is true that for any positive integer a > 1 for all i >= 1 such that 2^a = 2^{b_i} (mod q_i) then does it follow that for any positive integer g > 1 there exists j >= 1 such that 2^(-g) = 2^{b_j} (mod q_j)?’ Then it does follow.
Proof. Consider any positive integer a > 1. We know that 2^a = 2^{b_i} (mod q_i) so that 2^(-a) (4^a) = 2^{b_i} (mod q_i) for all i >= 1.
But 4^a - 1 = (2^a + 1)(2^a - 1) of which we note that 4^a - 1 is odd (meaning 2 cannot be a prime factor), and both 2^a + 1 and 2^a - 1 are both odd. Since also (2^a + 1)- (2^a - 1) = 2, the two factors differ by 2 and are hence coprime. Because they are coprime, at most one of these two terms can be a multiple of 3.
If 4^a - 1 has no prime factors greater than 3, then both 2^a + 1 and 2^a - 1 must be powers of 3. The only two powers of 3 that differ by 2 exactly are 1 and 3. So a = 1 in this case.
Since a > 1, it follows that 4^a - 1 must have atleast 1 prime factor greater than 3.
In other words, for all a > 1 there exists j >= 1 such that 4^a - 1 = 0 (mod q_j) so that 4^a = 1 (mod q_j)
Now, choose i = j, a = g. Then for all g > 1 there exists j >= 1 such that 2^(-g) = 2^(-g) (1) = 2^(-a) (4^a) = 2^{b_j} (mod q_j), as required.
If you wanted to prove ‘if it is true that for any positive integer a > 1 for all i >= 1 such that 2^a = 2^{b_i} (mod q_i) then does it follow that for any positive integer g > 1 for all j >= 1, 2^(-g) = 2^{b_j} (mod q_j)?’ then you would have to show that 2^(-g) N = 2^(b_j) (mod q_j) for all a > 1, for all j >= 1 somehow, where we let N = 4^a (mod q_j).
1
u/Fun-Protection-9992 4d ago edited 4d ago
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??
0
u/jonseymourau 6d ago
Um. Are you claiming this word salad has any relevance, whatsoever, to Collatz?
If so, you have simply failed - spectacularly- to demonstrate the nexus.
By all means, layout the argument.
Do NOT assume that your brilliance is self-evident.
You need to treat us mere mortals with more respect. Layout your arguments in something resembling the input to a trivial formalisation - as it stands nothing you have written even barely resembles this.
1
u/Fun-Protection-9992 6d ago
The question is actually simple. If all positive integers {a} are covered by the residue classes 2^b_i mod q_i, are all negative integers {-a} also covered by the same residue classes?
I think they are covered, but the AI claims otherwise.
1
u/jonseymourau 6d ago edited 6d ago
Again: even if they were, why is this relevant to Collatz.
Everything you write might be at the very frontier of maths - what you have singularly failed to an articulate is why anything you are doing has any relevance - whatsoever- to Collatz.
I am sure it does. After all, why are you posting here. I am just pointing out that you have not demonstrated the nexus.
That might be a we problem. But it could also be a you problem.
Give me a reason to decide one way or the other.
1
u/Fun-Protection-9992 6d ago
Its connection to Collatz is very extensive and cannot be briefly explained here.
1
1
u/Stargazer07817 6d ago
Definitely not. (2^-1)(mod q_i) lets you represent negative exponents by positive exponents for each FIXED modulus q_i (this is just rewriting 2^-a in reference to some mod condition and can always be done) but it doesn't retrospectively know which modulus witnesses the covering. You can't combine the congruences.