KiAsaGibona's blog

Seeking help in Chinese Remainder Theorem
By KiAsaGibona, 12 years ago, In English

Hi,

I read these articles about Chinese Remainder Theorem on Wolfarm and Wiki but I cannot understand it properly :/ ..

So, I am wondering can any one here help me figuring out what Chinese Remainder Theorem is.. How does it work.. How to use this theorem.. You can also help by giving links of articles and blog posts about this topics ..

Thank You All... Have a Nice Day :)

(P.S. I searched in CodeForces .. But maybe my search id was not good enough to find what I am seeking )

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

An excellent example problem which uses CRT (source: Slovak ACM trainings):

We generate a sequence of integers. Its first 6 elements are given in the input; any next element is the sum of 6 elements before it, modulo 39270. What is the period of this sequence?

The key to the solution lies in realizing that 39270 factors out into 2*3*5*7*11*17. You're able to bruteforce the period modulo any of these primes (there are at most 17**6=2.4e+6 possible states for the sequence, so you just generate it and check for the first 6-tuple of consecutive elements to repeat). The resulting period is the lowest common multiple of the 6 periods so discovered.

Now, we get to the practical meaning of CRT: If some property is periodic with periods s_i modulo number a_i, and all a_i are pairwise coprime, then the period of that property modulo a_1*a_2*..*a_n is LCM(s_1,s_2,...,s_n).

The only things from number theory you need to learn about from this point are computing GCD (and LCM) of 2 or more numbers. Tada! :D

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What happens if the sequence besides having a period has a pre-period? What I mean by pre-period is this: 1, 2, 3, 4, 5, 4, 5, 4, 5 has period = 2 and pre-period = 3.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Well, it has been 4 years since you posted this. Are you still looking for resources? If so, I recently wrote a blog post on it, which you can find here.

I am working on the generalized version of CRT, where moduli are not co-prime. It was hard finding resources on this topic. For some reason, everyone is just fascinated with co-prime moduli. I even found a book that just discussed co-prime moduli CRT and left the generalized CRT as homework for readers :p

EDIT: Done with the generalized version. You can find the tutorial here.

→ Reply