Re: [PrimeNumbers] Modular arithmetic query
- On Friday 01 April 2005 12:08, you wrote:
> Hello,Yes, use the Chinese Remainder Theorem:
> I hope this question is germane to this group, and
> 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.
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.
[Non-text portions of this message have been removed]