Mathematics desk
< September 30	<< Sep \| October \| Nov >>	October 2 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 1

What's the approximate natural density of even natural numbers where all these are true?

x modulo 3 is 2

x modulo 4 is 2

x modulo 5 is 2

x modulo 6 is 2

x modulo 7 is 2

x modulo 8 is 2

x modulo 9 is 2

What about passing 6 out of 7? Sagittarian Milky Way (talk) 02:42, 1 October 2018 (UTC)[reply]

It should be 1/LCM(3,4,5,6,7,8,9), or 1/2520. Bubba73 ^{You talkin' to me?} 02:57, 1 October 2018 (UTC)[reply]

If you're asking about only the even numbers, then it is a little different. Bubba73 ^{You talkin' to me?} 02:59, 1 October 2018 (UTC)[reply]

Shouldn't be exactly the same since 2520 is even? Assuming were talking about out of some sort limit towards and even distribution of the numbers. For 6 out of seven that would mean one could remove one of 5,7,8 or 9 but not 3 or 4 or 6 as they divide an LCM of the others. The LCM would always be an even divisor of 2520 so one just needs to know how many numbers besides 2 mod 2520 would be allowed within 2520, which I think should be an exercise for the reader ;-) Dmcq (talk) 11:32, 1 October 2018 (UTC)[reply]

And a quick check myself shows one has to be careful :) taking out 8 for instance produces an LCM of 1260 so only pproduce 1262 modulo 2520 as well as 2. Dmcq (talk) 11:44, 1 October 2018 (UTC)[reply]

Bubba73 gave the fish. The fishing rod is Chinese remainder theorem. It does not include the footwork for when some moduli are not pairwise coprime, but essentially, either the non-coprime congruences are incompatible (e.g. modulo 2 is 1 and modulo 4 is 2), in which case there is no solution, or they are, in which case you can transform the requirements to have coprime moduli. Tigraan^{Click here to contact me} 14:58, 1 October 2018 (UTC)[reply]
- @Tigraan: I believe the system requiring congruences to 4 mod 8 and 4 mod 12 with solutions given by all the integers congruent to 4 mod 24 is a counterexample, depending on what is precisely meant by "transform". 8 and 12 are not coprime, and this system has solutions, but I believe there is no equivalent system with coprime moduli (except maybe the solution itself).--Jasper Deng (talk) 05:15, 4 October 2018 (UTC)[reply]
  - @Jasper Deng: $x\equiv 4[mod\ 8]\land x\equiv 4[mod\ 3]$ has the same set of solutions (checked by a quick python loop).
  The general way to "transform" is to convert the set of equations into a single equation modulo the LCM if possible (there is always zero or one solution modulo the LCM), then split it back up into powers of prime (which if I am not mistaken is the only possible decomposition of a number into a set where any pair is coprime). The splitting up part works thanks to the "reverse" of the theorem (see the ring isomorphism stuff in Chinese_remainder_theorem#Theorem_statement). Tigraan^{Click here to contact me} 08:59, 4 October 2018 (UTC)[reply]
  Ping fix: Jasper Deng. Tigraan^{Click here to contact me} 09:00, 4 October 2018 (UTC)[reply]