hexor's blog

My Remainder Theorem
By hexor, 10 years ago, In English

I found a new theorem and I called it "My Remainder Theorem". My theorem finds similar thing with "Chinese Remainder Theorem". Maybe it has been founded before. If you heard this theorem before, please tell me.

Problem :

We have N equation.

x = equation_1.a ( mod equation_1.b )
x = equation_2.a ( mod equation_2.b )
.
.
.
x = equation_n.a ( mod equation_n.b )

(1<=i<=n) equation_i.b can be not a prime number. ( difference between my M.R.T. and C.R.T. )

We use a function which can do merge two equation and create a new equation. ( Let's call this function "merge" )

For example we have 3 equations. We'll solve this problem.

ans1 = merge( equation_1,equation_2 ); ans2 = merge( a,equation_3 );

Our answer is ans2.a.

Let's look at to "merge" function.

  • We assume equation_1.b > equation_2.b
  • lcm -> least common multiplier
merge( equation_1,equation_2 ){
	LCM = lcm(equation_1.b,equation_2.b)
	KKK = LCM/equation_1.b
	for i=0 to KKK-1
		if( ( i*equation_1.b + equation_1.a ) mod equation_2.b == equation_2.a )
			return answer = make_equation( LCM , i*equation_1.b+equation_1.a )	//	x = i*equation_1.b+equation_1.a(mod LCM)
	return "NO SOLUTION"
}
  • If there is any solution for equation_1 and equation_2, also there is a solution for i<=KKK-1.
  • We try all possible i values and we get a x value for equation_1. Then we check if x equals to equation_2.b+equation_2.a .
  • If this condition is true, we find a x value. // x = i*equation_1.b+equation_1.a(mod LCM)

  • If there is no x value, that means solution doesn't exist.

This algorithm's complexity is O( max( equation_i.b )*n )

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

Comments Comments (11)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +60 Vote: I do not like it

It's nice that you do your own investigations, but I'm sorry to disappoint you — this is not something new, rather easy modifications of CTR (in classical CTR b values need to be coprime, not necessarily prime) and each merge can be done in O(log b) using extended Euclid's algorithm. In order to name a theorem with your name, you have to try harder :).

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

    Where can I find this algorithm? I want to learn more.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Frankly saying, I don't know better than you, where you can learn something about it, so I will simply tell you to try googling this. What I can say is that this exgcd thing is useful even in standard CRT version and in that slightly generalized version when merging two equations we need to do some "gcding" of "b" values, adjusting "a" values and either we got a simple contradiction or treat this as in usual version. I think that will be pretty much everything here, you can work out details on your own.

      What I can recommend to you is to try solving this problem: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=867486&sid=e7308c474d0856b6d815ea9bfa7e8c28#p867486 There is a solution using mainly CRT stuff in a very nice way (and some little Fermat for start), which I was very proud of when I came up with it, though I won't be willing to write it here, because it was pretty long and complicated (but in my opinion beatiful!).

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      I was also looking for the concept of "Generalized Chinese Remainder Theorem". Google search didn't help out much until I stumbled upon a comment in "Wiki-talk" where a person was suggesting adding "non-coprime moduli CRT" to the wiki page. After decrypting his comment, I managed to get some insight.

      Wrote down a blog post since resource on "Generalized CRT" is scarce, or at least I couldn't readily find any. You can find it on here

      Hope it helps.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Cool stuff, thanks for writing I appreciate the effort. Didn't know that CRT could be generalized :)

        → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    I've always thought it's CRT, not CTR.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Uh, I'm sorry, you're right :D. The reason of my mistake was that in my language (Polish) it is called "Chińskie Twierdzenie o Resztach", so its polish abbreviation is CTR :P.

      → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Your problem is basically this one: https://open.kattis.com/problems/generalchineseremainder (If you can solve it for two numbers, you can easily solve it for N numbers by iteratively applying the algorithm.) The URL seems to suggest that we should call it "General Chinese Remainder Theorem". ^^

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's very informative. Thank you.

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

Another question on CRT: Chinese and random toppings

Edit: I suggested one question on Chinese Remainder Theorem. Why downvotes?

→ Reply