# Finding divisibility of a

Let $$a=\frac{72!}{(36!)^2}-1$$

Find whether

1. $a$ is odd.
2. $a$ is even.
3. $a$ is divisible by 71.
4. $a$ is divisible by 73.

Multiple answers can be correct.

I was able to find whether $a$ is even or odd in the following way:

There is a method of finding the power of a prime factor in the factorial of a number. If $p$ is a prime factor of any number $q\;!$, and the power of $p$ in $q\;!$ is $n$, then $$n=\left[\frac {q}{p}\right]+\left[\frac {q}{p^2}\right]+\left[\frac {q}{p^3}\right]+\cdots$$ where $\bf{[\;.]}$ denotes Greatest Integer Function. So, in the above expression, putting $q=72$ and $p=2$, we get $n=70$. Putting $q=36$ and $p=2$, we get $n=34$. So, the power of $2$ in the numerator is $70$, while in denominator, it is $68$. Thus, $a+1$ is an even number, making $a$ an odd number.

However, I am not able to check the divisibility of $a$ by $71$ or $73$. What is the method to do that for factorial numbers? I am to solve this by using concepts of binomial theorem.

## 2 Answers

Since $71$ is prime, $72!$ is divisible by $71$ whereas $36!^2$ is not. Hence $72!/(36!^2)$ is divisible by $71$ and $72!/(36!^2)-1$ is not.

For divisibility by $73$, notice that $$36!^2 = \prod_{k=1}^{36} k^2 \equiv \prod_{k=1}^{36} (-k(73-k)) = \prod_{k=1}^{36} k(73-k) = 72! \mod 73,$$ so the quotient $72!/(36!^2)$ is $1$ modulo $73$ (note that $73$ is prime, thus $72!$ is not divisible by $73$). Since $72!/(36!^2) \equiv 1 \mod 73$, we find that $72!/(36!^2)-1$ is divisible by $73$.

• I did not understand the step of congruence. – Tejas Mar 16 '14 at 16:26
• $k \equiv -(73-k) \mod 73$, therefore $k^2 \equiv -k(73-k) \mod 73$. – user133281 Mar 16 '14 at 16:28

$$\displaystyle \binom{72}{36}=$$ coefficient of $$x^{36}$$ in $$\displaystyle (1-x)^{72} = \frac{(1-x)^{73}}{1-x}$$

$$=(1-x)^{73}(1-x)^{-1}$$

$$=\bigg[\binom{73}{0}-\binom{73}{1}x+\binom{73}{2}x^2+\cdots \bigg](1+x+x^2+\cdots)$$

$$=\binom{73}{0}-\binom{73}{1}+\binom{73}{2}+\cdots +\binom{73}{36}$$

which is divisible by $$73$$

due to the fact that $$\displaystyle \binom{p}{r}$$ is divisible by $$p$$

$$p$$ is prime number and $$r\in \{1,2,3,4,\cdots,p-1\}$$