# Is $72!/36! -1$ divisible by 73?

Is $\frac{72!}{36!}-1$ divisible by the number 73?

I am not getting a clue in which direction should I go, though I did small amount of work by converting the above expression in the below given form

$$(1.3.5.7.9...69.71).2^{36} - 1$$

and

$$36!\binom{72}{36} -1$$

I am unable to proceed further.

Let $p=73$. $p$ is a prime number. Thus by Wilson's theorem $$72! = (p-1)!\equiv -1 \mod p$$

Notice that $\forall 1\le n\le 36$, $73-n \equiv -n \mod p$, thus

$$\frac{72!}{36!}\equiv (37\cdot 38\cdots 72)\equiv (-1\cdot -2\cdots -36) \equiv (1\cdot 2\cdots 36)(-1)^{36} \equiv (1\cdot 2\cdots 36) \equiv 36! \mod p$$

Suppose for the sake of contradiction that $\frac{72!}{36!} \equiv 1 \mod p$, then $36! \equiv 1 \mod p$ and

$$72! \equiv (36!)^2 \equiv 1 \mod p$$

which is not true.

So we can conclude that $\frac{72!}{36!} \mod p$ is not $1$.

• The easiest way to prove Wilson's Theorem, that $(p-1)!\equiv -1 \pmod p$ when $p$ is prime is to ask what you get when you multiply together all the members of a finite commutative group. Members that are not their own inverses will all cancel out. – DanielWainfleet Oct 1 '15 at 7:36

$$\dfrac{(2m)!}{m!}=(2m)(2m-2)\cdots4\cdot2$$ $$\equiv(-1)(-3)\cdots(2m+1-4)(2m+1-2)\pmod{2m+1}$$ $$\equiv(-1)^m1\cdot3\cdots(2m-3)(2m-1)$$

Now if $2m+1$ is prime, $$(2m)!\equiv-1\pmod{2m+1}$$

$$-1\equiv(-1)^m\{(2m)(2m-2)\cdots4\cdot2\}^2$$

If $m=2n,$ $$\{(4n)(4n-2)\cdots4\cdot2\}^2\equiv-1\pmod{4n+1}$$

$$\implies(4n)(4n-2)\cdots4\cdot2\not\equiv\pm1\pmod{4n+1}$$

Not a very glorious method, but it can be verified by hand. The numbers on the right are the prefix products of those on the left, modulo $73$ (e.g. $37\cdot38\bmod73=19$).

\begin{align}37&\to37\\ 38&\to19\\ 39&\to11\\ 40&\to2\\ 41&\to9\\ 42&\to13\\ 43&\to48\\ 44&\to68\\ 45&\to67\\ 46&\to16\\ 47&\to22\\ 48&\to34\\ 49&\to60\\ 50&\to7\\ 51&\to65\\ 52&\to22\\ 53&\to71\\ 54&\to38\\ 55&\to46\\ 56&\to21\\ 57&\to29\\ 58&\to3\\ 59&\to31\\ 60&\to35\\ 61&\to18\\ 62&\to21\\ 63&\to9\\ 64&\to65\\ 65&\to64\\ 66&\to63\\ 67&\to60\\ 68&\to65\\ 69&\to32\\ 70&\to50\\ 71&\to46\\ 72&\to27\\ \end{align}

• As you mentioned, it is not elegant solution. Also , it doesn't explain why that works if the given number is any odd prime. – Akshay Hegde Jan 26 '17 at 10:00