8
$\begingroup$

How to prove that $$\frac{1000!}{(500!)^2}$$ is not divisible by 7?

I reduced the above fraction to: $$\frac{\prod_{k=501}^{1000}k}{500!} $$

But I don't know how to proceed. Please help.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hint: consider prime factorisations. Focus on $7$'s. $\endgroup$ – Arthur Jan 24 '17 at 15:29
6
$\begingroup$

It is a general formula that the number of times a prime $p$ occurs in the prime factorisation of $n!$ is given by

$$ \left[\frac{n}{p}\right] + \left[\frac{n}{p^2}\right] + \left[\frac{n}{p^3}\right] + \cdots $$

where $[x]$ denotes the greatest integer $≤x$.

In $1000!$ you'd have

$$ \left[\frac{1000}{7}\right] + \left[\frac{1000}{7^2}\right] + \left[\frac{1000}{7^3}\right] + \cdots = 164 $$

$7$'s, and in $500!$ you have

$$ \left[\frac{500}{7}\right] + \left[\frac{500}{7^2}\right] + \left[\frac{500}{7^3}\right] + \cdots = 82 $$

$7$'s. So you'll have a total of $164$ 7's in $(500!)^2$.

The rest follows.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am sorry but would you kindly help in the conclusion? I scratched my head for a while but did not understand how that proves that it is not divisible by 7. $\endgroup$ – Macindows Nov 14 '18 at 14:59
24
$\begingroup$

This is overkill, but by Lucas's Theorem$$\frac{1000!}{(500!)^2}=\binom{1000}{500} \equiv \binom{2}{1}\binom{6}{3}\binom{2}{1}\binom{6}{3} \equiv 4 \pmod{7}$$ As $1000=2626_{7}$ and $500=1313_{7}$.

Here is another , more elementary argument, from Legendre's formula, $$\nu_7(n!) = \frac{n - s_7(n)}{6}$$ So $\nu_7(100!)=164, \nu_7 (50!)=82$. So the $7$ s in the denominator and the numerator cancel out. So we have the desired result.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Got it! But you told that applying Lucas's Theorem is overkill, so, is there any other solution? $\endgroup$ – ami_ba Jan 24 '17 at 15:37
  • $\begingroup$ @AmitayasBanerjee I added one right now. This one is a more elementary result. $\endgroup$ – S.C.B. Jan 24 '17 at 15:38
  • 3
    $\begingroup$ (+1) Two beautiful proofs in a single answer make a well-deserved upvote. $\endgroup$ – Jack D'Aurizio Jan 24 '17 at 15:43
  • $\begingroup$ [+1] I love Lucas' theorem, and a good application of it. $\endgroup$ – Andreas Caranti Jan 24 '17 at 16:14
  • $\begingroup$ @AmitayasBanerjee Could you tell me why you unaccepted my answer? $\endgroup$ – S.C.B. Apr 29 '17 at 4:01
5
$\begingroup$

You can also overkill it by Kummer's theorem:

Notice that $500$ is $1313$ in base $7$. Since every digit is smaller than $\frac{7}{2}$ there are no carries when adding $1313+1313$ in base $7$.

Therefore $\binom{1000}{500}$ is not a multiple of $7$.

In general we have that a prime $p$ divides $\binom{2n}{n}$ if and only if $n$ has at least one digit larger than or equal to $p/2$ in its base $p$ expansion.

|cite|improve this answer
$\endgroup$
4
$\begingroup$

Consider prime factorisations:

$$\lfloor\frac{1000}{7}\rfloor+\lfloor\frac{1000}{7^2}\rfloor+\lfloor\frac{1000}{7^3}\rfloor+...=142+20+2=164$$ Then $$7^{164}|1000!$$

Similarly:

$$\lfloor\frac{500}{7}\rfloor+\lfloor\frac{500}{7^2}\rfloor+\lfloor\frac{500}{7^3}\rfloor+...=71+10+1=82$$ Then $$7^{164}=7^{82\cdot2}=(7^{82})^2|(500!)^2$$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sorry, but didn't get it. $\endgroup$ – ami_ba Jan 24 '17 at 15:40
  • 1
    $\begingroup$ The fact that $7^{164}$ divides $1000!$ and $(500!)^2$ does not suffice to decide if $7$ divides their ratio or not. Please be more careful. $\endgroup$ – Did Jan 24 '17 at 15:42
  • $\begingroup$ Yes. But I considered prime factorisations $\endgroup$ – Roman83 Jan 24 '17 at 15:46
  • $\begingroup$ So the point is not that $7^{164}$ divides $1000!$, but that $7^{165}$ does not. $\endgroup$ – Callus Jan 24 '17 at 15:49
  • $\begingroup$ I'm understood, thank you! $\endgroup$ – Roman83 Jan 24 '17 at 16:00
2
$\begingroup$

In $\{1,\dots, 500\}$, there are 71 multiples of 7, 10 multiples of $7^2$ and one multiple of $7^3$.
How many multiples of $7$, $7^2$, $7^3$ do you have in $\{501,\dots, 1000\}$? Same amount.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why are they the same amount? $\endgroup$ – Jorge Fernández Hidalgo Jan 24 '17 at 15:59
  • 1
    $\begingroup$ 504 is first multiple of 7 (with multiplicity of seven is 1 in factorization), and $504 + 7 \cdot 70 = 994$. Also $7^2 \cdot 11 = 539$ (multiplicity is 2) and $7^2 \cdot 20 = 980$. At last $7^3 \cdot 2 = 686$ (fits only once). $\endgroup$ – johnnycrab Jan 24 '17 at 16:18

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.