Evaluate30![mod 899]

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$$

Just use the on-site calculator:

$$\left({\mathtt{30}}{!}\right) {mod} \left({\mathtt{899}}\right) = {\mathtt{464}}$$

.