Find the remainder when $15!$ is divided by $31$. Find the remainder when $15!$ is divided by $31$. I know I have to apply Wilsons theorem but i am a little confused how. 
 A: By Wilson's Theorem, we know that $30!\equiv-1$ (mod 31). Now lets look at the extra factors that are multiplied to turn $15!$ into $30!$.
$16\equiv -15$ (mod 31), $17\equiv -14$ (mod 31), $\ldots, 30\equiv -1$ (mod 31)
Thus $\frac{30!}{15!}\equiv (-1)^{30-15}\cdot 15!=-15!$ (mod 31)
Thus we get
$$-1\equiv 30!=15!\frac{30!}{15!}\equiv -1\cdot (15!)^2\Rightarrow 15!=\pm1\text{ (mod 31)}$$
Which one do you think it is?
A: This might be hitting a fly with a brick but.....
Primes less than or equal to 15:  2,3,5,7,11,13.
How many multiples of 2,4,8 are less than or equal to 15:7,3,1
How many multiples of 3,9:5,1
How many multiples of 5: 3
How many multiples of 7: 2.
11,13 > 15/2.
So $15! = 2^{7+3+1}3^{5+1}5^37^211\cdot13=2^{11}3^65^27^211\cdot13$
$2^{11} = (2^5)^2*2 = 32^2*2 \equiv 2 \mod 31$
$3^6 = (3^3)^2 = 27^2 \equiv (-4)^2 \equiv 16 \equiv -15 \mod 31$
$5^3 = 25*5 \equiv -6*5 \equiv -30 \equiv 1 \mod 31$
So $2^{11}3^65^3 \equiv -30 \equiv 1 \mod 31$
So $15! \equiv 7^2*11*13 \mod 31$.
$7^2 = 49 \equiv 18 \equiv 36/2 \equiv 5/2 \mod 31$
$11 \equiv -20 \mod 31$
$13 \equiv 26/2 \equiv -5/2 \mod 31$
So $15! \equiv 5/2*-5/2*-20 \equiv 25*5 \equiv -6*5 \equiv -30 \equiv 1 \mod 31$
