Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2018 October 1

From Wikipedia, the free encyclopedia
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

[edit]

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

[edit]
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. TigraanClick 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: 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). TigraanClick here to contact me 08:59, 4 October 2018 (UTC)[reply]
      Ping fix: Jasper Deng. TigraanClick here to contact me 09:00, 4 October 2018 (UTC)[reply]