The final result is `1Z101`.

Let us convert it back to the decimal system by adding the weighted positional values:

**Example 2:** Let us convert `237` to balanced ternary. At first we use normal ternary to rewrite the number:

The Chinese Remainder Theorem (which will be referred to as CRT in the rest of this article) was discovered by Chinese mathematician Sun Zi.

$$\begin{align}

where $a_i$ are some given constants. The original form of CRT then states that the given set of congruence equations always has *one and exactly one* solution modulo $p$.

A consequence of the CRT is that the equation

is equivalent to the system of equations

$$\begin{align}

(As above, assume that $p = p_1 p_2 \cdots p_k$ and $p_i$ are pairwise relatively prime).

Another consequence of the CRT is that we can represent big numbers using an array of small integers. For example, let $p$ be the product of the first $1000$ primes. From calculations we can see that $p$ has around $3000$ digits.

Any number $a$ less than $p$ can be represented as an array $a_1, \ldots, a_k$, where $a_i \equiv a \pmod{p_i}$. But to do this we obviously need to know how to get back the number $a$ from its representation. In this section, we discuss Garner's Algorithm, which can be used for this purpose. We seek a representation on the form

which is called the mixed radix representation of $a$.

Garner's algorithm computes the coefficients $x_1, \ldots, x_k$.

Let $r_{ij}$ denote the inverse of $p_i$ modulo $p_j$

which can be found using the algorithm described in [Modular Inverse](module-inverse.md). Substituting $a$ from the mixed radix representation into the first congruence equation we obtain

Substituting into the second equation yields

which can be rewritten by subtracting $x_1$ and dividing by $p_1$ to get

$$\begin{array}{rclr}

Similarly we get that

Now, we can clearly see an emerging pattern, which can be expressed by the following code:

So we learned how to calculate coefficients $x_i$ in $O(k^2)$ time. The number $a$ can now be calculated using the previously mentioned formula

It is worth noting that in practice, we almost always need to compute the answer using Big Integers, but the coefficients $x_i$ can usually be calculated using built-in types, and therefore Garner's algorithm is very efficient.

Problems often ask for the minimum $x$ which satisfies the solution.

It is possible to get all answers and take the minimum, or reduce the first found answer using [Euler's theorem](phi-function.md#toc-tgt-2), but we can be smart about the order in which we calculate values and ensure the first answer we find is the minimum.

int solve(int a, int b, int m) {

a %= m, b %= m;

In this article we discuss how to compute the number of divisors $d(n)$ and the sum of divisors $\sigma(n)$ of a given number $n$.

Which means we have $e+1$ choices.

Therefore if the prime factorization of $n$ is $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$, where $p_i$ are distinct prime numbers, then the number of divisors is:

A way of thinking about it is the following:

We can use the same argument of the previous section.

* If there is only one distinct prime divisor $n = p_1^{e_1}$, then the sum is:

* If there are two distinct prime divisors $n = p_1^{e_1} \cdot p_2^{e_2}$, then we can make the same table as before.

The only difference is that now we now want to compute the sum instead of counting the elements.

It is easy to see, that the sum of each combination can be expressed as:

* In general, for $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ we receive the formula:

A multiplicative function is a function $f(x)$ which satisfies

if $a$ and $b$ are coprime.

Both $d(n)$ and $\sigma(n)$ are multiplicative functions.

In some cases it is necessary to consider complex formulas modulo some prime $p$, containing factorials in both numerator and denominator, like such that you encounter in the formula for Binomial coefficients.

Thus, formally the task is: You want to calculate $n! \bmod p$, without taking all the multiple factors of $p$ into account that appear in the factorial.

Imaging you write down the prime factorization of $n!$, remove all factors $p$, and compute the product modulo $p$.

Learning how to effectively calculate this modified factorial allows us to quickly calculate the value of the various combinatorial formulas (for example, [Binomial coefficients](../combinatorics/binomial-coefficients.md)).

Let's write this modified factorial explicitly.

$$\begin{eqnarray}

It can be clearly seen that factorial is divided into several blocks of same length except for the last one.

$$\begin{eqnarray}

The main part of the blocks it is easy to count — it's just $(p-1)!\ \mathrm{mod}\ p$.