# Math

## Chinese Remainder Theorem <a href="#chinese-remainder-theorem" id="chinese-remainder-theorem"></a>

### Basic <a href="#basic" id="basic"></a>

If moduli (**`n1`, `n2`, etc.**) are co-primes, the following rules hold:

```shellscript
x ≡ a1 mod n1 # means `x % n1 = a1`
x ≡ a2 mod n2 # means `x % n2 = a2`
...
x ≡ ak mod nk # means `x % nk = ak`
```

In addition, if the values of **`a1`, `a2`, … `ak`** and **`n1`, `n2`, … `nk`** are defined, we can calculate **`x`** by the following approach.

```shellscript
# Calculate N
N = n1 * n2 * n3 * ... * nk

# Calculate Ni (N1, N2, ..., Nk)
N1 = n2 * n3 * n4 ... * nk
N2 = n1 * n3 * n4 ... * nk
N3 = n1 * n2 * n4 ... * nk
...
Nk = n1 * n2 * n3 ... * n(k-1)

# Calculate xi (x1, x2, ..., xk)
N1*x1 ≡ 1 (mod n1) # means `N1*x1 % n1 = 1`
N2*x2 ≡ 1 (mod n2) # means `N2*x2 % n2 = 1`
N3*x3 ≡ 1 (mod n3) # means `N3*x3 % n3 = 1`
...
Nk*xk ≡ 1 (mod nk) # means `Nk*xk % nk = 1`

# x is sum of each ai*Ni*xi (mod N)
x = a1*N1*x1 + a2*N2*x2 + a3*N3*x3 + ... + ak*Nk*xk (mod N)
```

### Using crt method in Sympy <a href="#using-crt-method-in-sympy" id="using-crt-method-in-sympy"></a>

```shellscript
from sympy.ntheory.modular import crt

m = [7, 15]
a = [5, 12]
(x, y) = crt(m, a)
# x = 68, y = 77
```

### References <a href="#references" id="references"></a>

* [Wikipedia](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
* [CryptoHack](https://cryptohack.org/courses/modular/crt1/)
* [YouTube: Maths with Jay](https://www.youtube.com/watch?v=zIFehsBHB8o)