4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$

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.