+26403 30! [mod 899] ?
$$30! \mod 899 \stackrel{?}{=}$$
$$\small{\text{
$ 899 = 29 * 31 = p*q \quad | \quad $ let $ p = 29 $ and $ q=31 $ so \textcolor[rgb]{1,0,0}{p and q are relatively prim!}
}}$$
I. $$\small{\text{
$ \textcolor[rgb]{0,0,1}{30! \mod p = 0} , $ because $ p = 29 $ is divider of $ 30! \ (30! = 30*\textcolor[rgb]{1,0,0}{29}*28*...3*2*1)
$
}}$$
$$\small{\text{
$ \textcolor[rgb]{0,0,1}{30! \mod p = r} , $ if $ p = 29 $ we have $ r = 0
$
}}$$
II. $$\small{\text{
$ \textcolor[rgb]{0,0,1}{30! \mod q = s } \quad q=31 $ is a prime number so $ \textcolor[rgb]{0,0,1}{(31-1)! \equiv -1 \mod 31} $ [Wilson]
}}$$
$$\small{\text{
$ (31-1)! \equiv -1 + 31 \mod 31 $ or $ 30! \equiv \textcolor[rgb]{0,0,1}{30} \mod 31 $ we have $ s=30 $
}}$$
III.
Since p and q are relatively prime, there are integers a and b such that ap+bq=1. You can find a and b using the Extended Euclidean algorithm.
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
So a=46 and b=-43, so 29*(46) + 31*(-43) = 1
IV.
Then
$$\small{\text{
$
\begin{array}{rcl}
30! \mod (p*q) &= &a*p*s + b*q*r \\
30! \mod (899) &= &46*29*30 + (-43)*31*0 = 46*29*30 = 40020
\end{array}
$
}}$$
V.
$$30! \mod 899 = 40020 \mod 899 = 464$$
