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.

• How does 30! relate to 15! mod 31?
– M.B.
May 3 '14 at 0:27

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?

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$