4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – DanielWainfleet Oct 1 '15 at 7:36
1
$\begingroup$

$$\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}$$

$\endgroup$
-1
$\begingroup$

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}$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.