+0

# Evaluate30![mod 899]

0
310
2

Evaluate30![mod 899]

Guest Nov 21, 2014

#2
+18827
+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
Sort:

#1
+26397
+5

Just use the on-site calculator:

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

.

Alan  Nov 21, 2014
#2
+18827
+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

### 17 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details