# Remainder question with $6!$ and 7

Find the remainder when $6!$ is divided by 7.

I know that you can answer this question by computing $6! = 720$ and then using short division, but is there a way to find the remainder without using short division?

As $7$ is prime, use Wilson's Theorem $$(p-1)!\equiv-1\pmod p$$ for prime $p$

Now, $\displaystyle -1\equiv p-1\pmod p$

• clean, concise, and uses a nice theorem +1 May 6, 2014 at 19:19
• What does this exactly mean? Sorry I am not an expert in maths. May 6, 2014 at 19:30
• @user108104 In my answer, I have specialized a proof of Wilson's Theorem to your specific case. I think you will find it quite intuitive in this concrete instance. May 6, 2014 at 20:50

Hint $\$ In analogy with Gauss's trick (see below), to simplify the product we pair up each number with its (multiplicative) inverse mod $7.\,$ Thus $$6! = 1\cdot (\overbrace{2\cdot 4}^{\equiv \,1})(\overbrace{3\cdot5}^{\equiv\, 1})\cdot 6 \equiv 1\cdot 1\cdot 1\cdot 6\equiv6\pmod{7}$$

Remark $\$ This method of pairing up inverses works for any prime - see Wilson's Theorem.

Below is Gauss's trick, imported from a deleted question

$\qquad\qquad \begin{array}{rcl}\rm{\bf Hint}\quad\quad\ \ S &=&\rm 1 \ \ \ +\ \ \: 2\ \ \ \ +\ \:\cdots\ +\ n\!-\!1\ +\ n \\ \rm S &=&\rm n \ \ +\ n\!-\!1\ +\,\ \cdots\ +\,\quad 2\ \ \ +\ \ 1\\ \hline \\ \rm Adding\ \ \ \ 2\: S &=&\rm n\ (n\!+\!1)\end{array}$

A famous legend says Gauss used this trick to quickly compute $1+2+\:\cdots\:+100\$ in grade school.

This trick of pairing up reflections around the average value is a special case of exploiting innate symmetry - here a reflection or involution. It's a ubiquitous powerful technique, e.g. see my post on Wilson's Theorem and it's group theoretic generalization.