10
$\begingroup$

Find the values of $a,b,c,d\in\mathbb{N}$ such that

$$ 34!=295232799cd9604140847618609643ab0000000 $$

My Attempt:

The factorial of $34$ contains a $3$, so the RHS must be divisible by $3$. Similarly, it must be divisible by $7$, $11$, $13$, $19$ etc.

But I do not understand how can I calculate $a,b,c,d$ in this equation.

$\endgroup$
  • $\begingroup$ Sorry for the misinformation. I've edited my solution to answer your question as stated. $\endgroup$ – Calvin Lin Feb 23 '13 at 18:06
  • $\begingroup$ This problem is inspired by an old BMO problem (though it is not exactly the same problem), so I added the contest-math tag. $\endgroup$ – wythagoras Aug 15 '16 at 7:49
8
$\begingroup$

$34!$ has 7 powers of 5, which explains the last 7 0's.

Since $34!$ has $17+8+4+2+1 = 32$ powers of 2, $34! / 10^{7}$ has $32-7=25$ powers of 2. Doing a divisibility by $2^{7} = 128$ on the last 7 digits, we get that $ab = 52$.

(Note: If we had the last 3 digits missing, we could do a divisibility by $2^{10} = 1024$ on the last 10 digits. This is a useful approach that isn't often mentioned.)

Now, since these are digits, $0 \leq c, d \leq 9$, so $-9 \leq c-d \leq 9$ and $0 \leq c+d \leq 18$.

Use the fact that $34!$ is a multiple of 9, to tell you the value of $c+d$. We get that $c+d = 3$ or $12$. Use the fact that $34!$ is a multiply of 11, to tell you the value of $c-d$. We get that $c-d = -3$ or $8$. Since $2c$ is an even number from 0 to 18, we conclude that $c=0, d=3$.

$\endgroup$
  • 1
    $\begingroup$ I think you miscounted the zeroes. $34!$ is divisible by $5^7$, hence ends in the seven zeroes displayed. (And the OP did not accidentally add a zero because indeed two nonzero digits follow after $\ldots 643$). In other words: The original BMO problem should contain the answer for this problem's $a$. $\endgroup$ – Hagen von Eitzen Feb 23 '13 at 17:50
  • $\begingroup$ @HagenvonEitzen Ah, sorry, I read it wrongly then. Didn't expect the problem to have been changed in such a way. $\endgroup$ – Calvin Lin Feb 23 '13 at 17:57
3
$\begingroup$

So $34!=(\ldots) + b10^7+a10^8+c10^{27}+d10^{28}$. Any divisibility rule by $k$ with $k\mid10^{20}-1$ cannot help here because it would allow to increase $a$ at the cost of $c$ and $b$ at the cost of $d$. Unfortunately, this rules out $9$ and $11$. But $7$ and $13$ combined should be helpful (note that $7\cdot 13=10^2-10+1$).

$\endgroup$
  • $\begingroup$ Not to mention that $7\cdot11\cdot13=1001$ … $\endgroup$ – Harald Hanche-Olsen Feb 23 '13 at 17:47
2
$\begingroup$

Ah, nice. Have you tried applying the divisibility criteria (in terms of decimal digits) for the various numbers you mention? Did I take it right that you have just covered those criteria?

$\endgroup$
  • 3
    $\begingroup$ You might also get some mileage out of the fact that, after you chop off the zeros at the end, what remains must still be divisible by some good sized power of 2. $\endgroup$ – Harald Hanche-Olsen Feb 23 '13 at 17:36
2
$\begingroup$

$34! = 295232799cd96041408476186096435ab000000$

$\left \lfloor \dfrac{34}{5} \right \rfloor = 6$

$\left \lfloor \dfrac{6}{5} \right \rfloor = 1$

So there are $6+1 = 7$ zeros at the end of $34!$. Hence $$\color{red}{b = 0}$$


THEOREM: Compute the following

  • $N = 5q_1 + R_1$

  • $q_1 = 5q_2 + R_2$

  • $q_2 = 5q_3 + R_3$

  • ...

  • $q_{n-1} = 5q_n + R_n$

where $0 \le R_i < 5$ for all $i$ and $0 \le q_n < 5$.

Then the first non zero digit in $N!$ is

$U(N!) = 2^P \times Q! \times R_1! \times R_2! \times R_3! \dots \times R_n! \pmod{10}$

Where

  • $P = q_1 + q_2 + \cdots + q_n$
  • $Q = q_n$

We compute \begin{align} 34 &= 5(6) + 4 \\ 6 &= 5(1) + 1 \\ 1 &= 5(0) + 1 \\ \end{align}

$P = 6 + 1 = 7$

$Q = 0$

\begin{align} U(34!) &= 2^7 \times 0! \times 4! \times 1! \times 1! \pmod{10} \\ &= 8 \times 0! \times 4 \times 1! \times 1! \pmod{10} \\ &= 2 \end{align}

So $$\color{red}{a = 2}$$


$34! = 2\; 95\; 23\; 27\; 99\; \color{red}{cd}\; 96\; 04\; 14\; 08\; 47\; 61\; 86\; 09\; 64\; 35\; 20\; 00\; 00\; 00$

Clearly $99 \mid 34!$ So, when we cast out $99's$, we should get $0$. Pairing off the numbers in $34!$ from right to left, skipping $cd$, and adding modulo $99$, we get

$ 2 + 95 + 23 + 27 + 99 + 96 + 04 + 14 + 08 + 47 + 61 + 86 + 09 + 64 + 35 + 20 + 00 + 00 + 00 \pmod{99} = 96$

So $cd = 99 - 96 = 03$

Hence

$$ \color{red}{c = 0} $$

$$ \color{red}{d = 3} $$

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