+0

# Evaluate30![mod 899]

0
688
2

Evaluate30![mod 899]

Nov 21, 2014

#2
+21869
+5

30! [mod 899] ?

$$30! \mod 899 \stackrel{?}{=}$$

$$\small{\text{  899 = 29 * 31 = p*q \quad | \quad  let  p = 29  and  q=31  so {p and q are relatively prim!} }}$$

I.  $$\small{\text{  {30! \mod p = 0} ,  because  p = 29  is divider of  30! \ (30! = 30*{29}*28*...3*2*1)  }}$$

$$\small{\text{  {30! \mod p = r} ,  if  p = 29  we have  r = 0  }}$$

II. $$\small{\text{  {30! \mod q = s } \quad q=31  is a prime number so  {(31-1)! \equiv -1 \mod 31}  [Wilson] }}$$

$$\small{\text{  (31-1)! \equiv -1 + 31 \mod 31  or  30! \equiv {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$$

.
Nov 21, 2014

#1
+27566
+5

Just use the on-site calculator:

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

.

Nov 21, 2014
#2
+21869
+5

30! [mod 899] ?

$$30! \mod 899 \stackrel{?}{=}$$

$$\small{\text{  899 = 29 * 31 = p*q \quad | \quad  let  p = 29  and  q=31  so {p and q are relatively prim!} }}$$

I.  $$\small{\text{  {30! \mod p = 0} ,  because  p = 29  is divider of  30! \ (30! = 30*{29}*28*...3*2*1)  }}$$

$$\small{\text{  {30! \mod p = r} ,  if  p = 29  we have  r = 0  }}$$

II. $$\small{\text{  {30! \mod q = s } \quad q=31  is a prime number so  {(31-1)! \equiv -1 \mod 31}  [Wilson] }}$$

$$\small{\text{  (31-1)! \equiv -1 + 31 \mod 31  or  30! \equiv {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$$

heureka Nov 21, 2014