### hexor's blog

By hexor, 4 years ago, ,

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 )

•
• +35
•

 » 4 years ago, # | ← Rev. 2 →   +60 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 :).
•  » » 4 years ago, # ^ |   0 Where can I find this algorithm? I want to learn more.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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!).
•  » » » » 4 years ago, # ^ |   +5 Thank you very much.
•  » » » 9 months ago, # ^ |   +12 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 hereHope it helps.
•  » » » » 9 months ago, # ^ |   +3 Cool stuff, thanks for writing I appreciate the effort. Didn't know that CRT could be generalized :)
•  » » 4 years ago, # ^ | ← Rev. 3 →   +5 I've always thought it's CRT, not CTR.
•  » » » 4 years ago, # ^ |   +16 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.
 » 4 years ago, # |   +8 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". ^^
•  » » 4 years ago, # ^ |   +5 It's very informative. Thank you.
 » 3 years ago, # | ← Rev. 2 →   -16 Another question on CRT: Chinese and random toppingsEdit: I suggested one question on Chinese Remainder Theorem. Why downvotes?