Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Modular arithmetic query

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... Yes, use the Chinese Remainder Theorem: http://mathworld.wolfram.com/ChineseRemainderTheorem.html In fact, you can use a weaker version, if you assume that
    Message 1 of 2 , Apr 1, 2005
      On Friday 01 April 2005 12:08, you wrote:
      > Hello,
      >
      > I hope this question is germane to this group, and
      > reasonable.
      >
      > Modular arithmetic is also known as clock arithmetic
      > therefore my question is:
      >
      > Given a series of repeating number sequences such as
      > a) 012340123401234, b) 012345670123456701234567,
      > c) 012345678901234567890123456789, etc., but occurring
      > at random intervals such as a) 012340123401234,
      > b) 345670123456701234567012,
      > c) 789012345678901234567890123456, etc., is there an
      > algorithm/formula that would tell me when the 0's, or
      > 1's or 2's etc., would line up? Essentially a
      > "synchronizing" of the clocks.

      Yes, use the Chinese Remainder Theorem:
      http://mathworld.wolfram.com/ChineseRemainderTheorem.html

      In fact, you can use a weaker version, if you assume that all clocks begin at
      the same value but have different periods: the first sync point is at the
      beginning, and each subsequent sync point is distanced from the previous by
      the least common multiple of the periods of all the clocks.

      In general, if each clock has a different starting point, then you'll have to
      use the full strength of the CRT. Read that web page I linked for more info.

      Do note, though, that this isn't always possible. A trivial example is two
      clocks with the same period but different starting points: obviously they
      would never line up. When clock periods share factors (i.e. are not
      relatively prime) there's always the chance that they won't ever sync.

      Décio


      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.