elementary-number-theorymodular arithmeticsolution-verification
If we multiply 2 number and take the mod with prime this is equivalent to first taking mod with the prime of individual number and then multiplying the result and again taking mod.
$$ ab\bmod p = ((a\bmod p)(b\bmod p))\bmod p$$
does there exist any proof for this? Does it work for composite moduli too? Then I can use the Chinese remainder Theorem to calculate the result does there any other way apart from Chinese remainder Theorem to solve the problem?
Andrew Granville's paper Binomial coefficients modulo a prime power (you can find a copy here) has the following generalization of Lucas' Theorem:
Theorem. Let $p^q$ be a prime power, and let $n=k+r$ be given. Write $$k = k_0 + k_1p + \cdots + k_dp^d$$ in base $p$, and let $K_j$ be the least positive positive residue of $\left\lfloor \frac{k}{p^j}\right\rfloor\pmod{p^q}$ for each $j\geq 0$, so that $$K_j = k_j + k_{j+1}p + \cdots + k_{j+q-1}p^{q-1};$$ make the same definitions for $n_j$, $N_j$, $r_j$, and $R_j$. Let $e_j$ be the number of indices $i\geq j$ for which $n_i\leq k_i$ (the number of "carries" when adding $k$ and $r$ in base $p$ at or beyond the $j$th digit). Then $$\frac{1}{p^{e_0}}\binom{n}{k} \equiv (\pm 1)^{e_{q-1}}\left(\frac{(N_0!)_p}{(K_0!)_p(R_0!)_p}\right)\left(\frac{(N_1!)_p}{(K_1!)_p(R_1!)_p}\right)\cdots\left(\frac{(N_d!)_p}{(K_d!)_p(R_d!)_p}\right)\pmod{p^q},$$ where $(\pm 1)$ is $-1$ except when $p=2$ and $q\geq 3$, and $(s!)_p$ is the product of the positive integers less than or equal to $s$ that are not divisible by $p$.
Granville then writes:
[This] Theorem[] provides a quick way to compute the value of the binomial coefficients modulo arbitrary prime powers, as it is straightforward to determine each of the $n_j$, $N_j$, $e_j$, etc. and then one need only determine the value of $(s!)_p\pmod{p^q}$ with $k\lt p^q$[.]
Once you have the value modulo prime powers, the Chinese Remainder Theorem (whose proof is almost invariably given constructively in textbooks) tells you how to find the value modulo $m$.
In the special case where $q=1$, the Theorem yields Lucas' Theorem: if $n_0$ and $m_0$ are the least nonnegative remainders of $n$ and $m$ modulo $p$, then $$\binom{n}{m} \equiv \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n_0}{m_0}\pmod{p},$$ if we interpret $\binom{r}{s}=0$ when $r\lt s$.
How does the CRT put the information together? This is found in pretty much all textbooks of Elementary Number Theory that I am familiar with:
Suppose you know that $x=\binom{n}{k}$ satisfies congruences $$\begin{align*} x&\equiv a_1\pmod{m_1}\\ x&\equiv a_2\pmod{m_2}\\ &\vdots\\ x&\equiv a_r\pmod{m_r} \end{align*}$$ where $m_1,\ldots,m_r$ are pairwise coprime (e.g., pairwise distinct primes, or prime powers of pairwise distinct primes, or any other collection of integers that are pairwise coprime), and $a_1,\ldots,a_r$ are arbitrary integers.
The Chinese Remainder Theorem says that there is a unique value of $x\bmod {m_1\times\cdots\times m_r}$ that satisfies all these congruences simultaneously.
The algorithmic method that appears in most textbooks is the following: for each $i=1,\ldots,r$, let $$M_i = \frac{m_1\times\cdots\times m_r}{m_i}.$$ That is, the product of all moduli except for the $i$th one. Then $\gcd(m_i,M_i)=1$, so we can find (e.g., by the Extended Euclidean Algorithm) integers $s_i$ and $t_i$ such that $$1 = s_iM_i + t_im_i.$$ Do this for each $i$. Then let $x$ be the remainder modulo $m_1\times\cdots\times m_r$ of $$a_1s_1M_1 + a_2s_2M_2 + \cdots +a_rs_rM_r.$$ Then $x$ satisfies all the original congruences and is the unique integer modulo $m_1\times\cdots\times m_r$ that satisfies the original congruences: since $M_i\equiv 0\pmod{m_j}$ if $i\neq j$ and $s_iM_i\equiv 1\pmod{m_i}$, we have that $$a_1s_1M_1+\cdots + a_rs_rM_r \equiv a_is_iM_i \equiv a_i\pmod{m_i}\quad\text{for each }i=1,2,\ldots,r.$$
For example: take $B=\binom{456}{51}$, $m=30 = 2\times 3\times 5$.
We find $B\bmod 2$, $B\bmod 3$, and $B\bmod 5$, e.g. using Lucas' Theorem. $$\begin{align*} 456 &= 0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3 + 0\times 2^4 + 0\times 2^5 + 1\times 2^6 + 1\times 2^7 + 1\times 2^8\\ &= 0 + 2\times 3^1 + 2\times 3^2 + 1\times 3^3 + 2\times 3^4 + 1\times 3^5\\ &= 1 + 1\times 5 + 3\times 5^2 + 3\times 5^3\\ 51 &= 1 + 1\times 2 + 0\times 2^2 + 0\times 2^3 + 1\times 2^4 + 1\times 2^5\\ &= 0 + 2\times 3 + 2\times 3^2 + 1\times 3^3\\ &= 1 + 0\times 5 + 2\times 5^2 \end{align*}$$ So $$\begin{align*} \binom{456}{51} &\equiv \binom{0}{1}\binom{0}{1}\binom{0}{0}\binom{1}{0}\binom{0}{1}\binom{0}{1}\binom{1}{0}\binom{1}{0}\binom{1}{0}\pmod{2}\\ &\equiv 0\pmod{2}\\ \binom{456}{51}&\equiv \binom{0}{0}\binom{2}{2}\binom{2}{2}\binom{1}{1}\binom{2}{0}\binom{1}{0}\pmod{3}\\ &= 1\pmod{3}\\ \binom{456}{51} &\equiv \binom{1}{1}\binom{1}{0}\binom{3}{2}\binom{3}{0}\pmod{5}\\ &=3\pmod{3}. \end{align*}$$ So we are trying to find the value of $x$ modulo $30$ such that $$\begin{align*} x&\equiv 0\pmod{2}\\ x&\equiv 1\pmod{3}\\ x&\equiv 3\pmod{5}. \end{align*}$$ We have $M_1 = 15$, $M_2 = 10$, $M_3 = 6$. We can write $$1=M_1 -7m_1,\quad 1 = M_2-3m_2,\quad 1=M_3-m_3.$$ So the number we want is $x=0M_1 + 1M_2 + 3M_3 = 10+18 = 28\bmod{30}$.
Hence $\binom{456}{31}\equiv 28\pmod{30}$.
Note. There are nicer ways of solving the problem of combining the congruences into a single congruence modulo $m_1\cdots m_r$ if you are working with pencil-and-paper; they can probably be programmed into a computer as well. Suppose we are trying to find the unique $x$ modulo $30$ such that $x\equiv 0\pmod{2}$, $x\equiv 1\pmod{3}$, and $x\equiv 3\pmod{5}$. From the first congruence, we know that $x=2a$ for some $a$. Plugging into the second congruence, we have $2a\equiv 1\pmod{3}$. Since $2\equiv -1\pmod{3}$, we have $-a\equiv 1\pmod{3}$, or $a\equiv 2\pmod{3}$; hence, $a=2+3b$. Plugging into $x=2a$ we have $x=4+6b$. Plugging this into the third congruence we have $4+6b\equiv 3\pmod{5}$, or $b\equiv -1\equiv 4\pmod{5}$. So $b=4+5c$. Plugging into the formula for $x$ we get $$x = 2a = 2(2+3b) = 4+6b = 4+6(4+5c) = 4+24+30c = 28+30c,$$ that is, $x\equiv 28\pmod{30}$, same answer as before.
Note 2. In particular, Lucas' Theorem tells you how to compute $\binom{n}{k}\bmod p$ for primes $p$. With Lucas' Theorem and the Chinese Remainder Theorem, you can compute $\binom{n}{k}\bmod m$ for any squarefree integer $m$ (exactly what Qiaochu said in his comment way back when). In order to compute $\binom{n}{k}\bmod m$ for arbitrary integers $m$, first you need to factor $m$ into prime powers, $$m = p_1^{\alpha_1}\cdots p_r^{\alpha_r},$$ where $p_1,\ldots,p_r$ are pairwise distinct primes and $a_i\gt 0$ for each $i$; then solve $\binom{n}{k}\bmod{p_i^{\alpha_i}}$ for each $i$ (that is, compute the remainder modulo the prime powers; this can be done using Granville's generalization of Lucas' theorem given above); and then using the Chinese Remainder Theorem to combine all the congruences $\binom{n}{k}\equiv a_i\pmod{p_i^{\alpha_i}}$ into a single congruence modulo $p_1^{\alpha_1}\cdots p_r^{\alpha_r}= m$ (exactly what André Nicolas said in his comment).
You solve the first two, then take that result and the remaining equation and you solve those two.
Best Answer
It has nothing to do with prime moduli or CRT. Rather, it is true for all moduli $\,n\,$ as we can easily prove as follows, using notation $\ \bar x := x\bmod n\, $ for the remainder left after dividing $\,x\,$ by $\,n.$
Applying the equivalence $\ x\equiv y\pmod{\! n}\!\color{#c00}\iff \bar x = \bar y,\, $ and $\,\small \rm\color{#0a0}{CPR} =$ Congruence Product Rule
$$\begin{align} {\rm mod}\ n\!:\,\ a \,&\color{#c00}\equiv\, \bar a\\ b\,&\color{#c00}\equiv\, \bar b\\ \smash{\overset{\rm\color{#0a0}{CPR}}\Longrightarrow}\,\ \ a\:\!b \,&\equiv\, \bar a\:\!\bar b\\ \color{#c00}\Longrightarrow\ a\:\!b\bmod n \,&=\, \bar a\:\! \bar b\bmod n,\ \ {\rm i.e.}\ \ \overline{ab} = \overline{\bar a \bar b} \end{align}\!\!$$
Remark $ $ Generally, as above, to prove an identity about mod as an operator it is usually easiest to first convert it into the more flexible congruence form, using $\color{#c00}\Longleftarrow$ in the equivalence, then prove it using congruences, then at the end, convert it back to operator form, using $\color{#c00}\Longrightarrow$ in the equivalence.
For a similar example consider equivalence of fractions, $\,\frac{a}b \equiv \frac{c}d\iff ad = bc.\,$ It would be quite cumbersome to do fraction arithmetic if we required that all fractions always be in normal (reduced) form, i.e. in least terms. Instead, it proves more convenient to have the flexibility to work with arbitrary equivalent fractions. For example, this allows us to state the fraction addition rule in very simple form by first choosing convenient reps having a common denominator.
See here for further discussion on $\!\bmod\!$ as a binary operator vs. equivalence relation.
See here for how to interpret the above as transporting the ring operations on cosets in the quotient ring $\,\Bbb Z/n\,$ to corresponding operations on their normal-form (remainder) reps in $\,\Bbb Z_n$.