Chinese Remainder Theorem
solution to a set of simultaneous linear congruences.
A coding enthusiast on the exciting journey of becoming a skilled developer.
The Chinese Remainder Theorem, also known as CRT is a mathematical theorem useful in number theory and modular arithmetic. It offers a solution to a set of simultaneous linear congruences. In simple words, congruences refer to a relationship between integers that share the same remainder when divided by a specified integer.
We are given two arrays as num[0,...n-1] and rem[0,...n-1]. The arrays can be of any size. However, every pair in num[] is coprime.(Coprime means two integers having Greatest Common Divisor or Highest Common Factor as 1). We are given k numbers which when divided by an unknown number x gives remainders of these numbers. The main point to note is that "n" numbers are pairwise coprime. Mathematically, it can be shown as:
x % num[0] = rem[0],
x % num[1] = rem[1],
...
x % num[n-1] = rem[n-1]
/
