10
$\begingroup$

I am working on the following problem:

Let $x_n$ be a sequence of positive odd numbers. If $N$ is the number of ordered pairs $(x_1, x_2, x_3, \dots, x_{42})$ such that $$x_1 + x_2 + x_3 + \dots + x_{42} = 2014,$$

then find $N \pmod {1000}$

My progress: Let $x_n = 2a_n + 1$, with $a_n \geq 0$. Then $$a_1 + a_2 + a_3 + \dots + a_{42} = 986$$

By stars and bars, this equals ${1027 \choose 41}$.

To find what this is equal to $\pmod {1000}$, I first computed the number of $5$s in it. I found that there were $2$ more $5$s in the numerator, and I am sure there are at least $2$ more $2$s in the numerator as well (the top has $2^{10} = 1024$), so there are two ending zeros. However, I do not know how I might find the last non-zero digit of this number.

$\endgroup$
  • $\begingroup$ Look up Lucas' Theorem, and apply the Chinese Remainder Theorem. $\endgroup$ – Calvin Lin Mar 4 '14 at 2:30
  • $\begingroup$ So should I apply Lucas' Theorem with $p = 5$ and $p = 2$? I'm a bit unclear how to get this in a form where I can apply CRT $\endgroup$ – MCT Mar 4 '14 at 2:50
  • 2
    $\begingroup$ It's only a 74 digit number. Start multiplying and soon you'll have the answer. $\endgroup$ – Eric Lippert Apr 27 '14 at 17:14
3
$\begingroup$

I was able to solve the problem by using one of the generalizations to Lucas' theorem (taken from page 2 of the wonderful paper Binomial coefficients modulo prime power).

$$\dfrac1{p^k}\binom{n}{m}\equiv(-1)^k\left(\dfrac{n_0!}{m_0!r_0!}\right)\left(\dfrac{n_1!}{m_1!r_1!}\right)\cdots\left(\dfrac{n_d!}{m_d!r_d!}\right)\pmod{p}$$

where $r = n -m$ and $n_i, m_i, r_i$ are the $i$th digits in the base $p$ representation of $n, m, r$ respectively. $k$ is the largest power of $p$ dividing $\binom{n}{m}$.

We have $n=1027, m = 41, r = 986$. In base $p=5$, $n = (13102)_5, m = (00131)_5, r = (12421)_5$.

The above result gives

$\begin{align}\frac{1}{5^k}\binom{1027}{41} &\equiv (-1)^k\left(\frac{1!}{0!1!}\right)\left(\frac{3!}{0!2!}\right)\left(\frac{1!}{1!4!}\right)\left(\frac{0!}{3!2!}\right)\left(\frac{2!}{1!1!}\right) \mod{5}\\&\equiv (-1)^k \left(\frac{1}{1}\right) \left(\frac{6}{2}\right)\left(\frac{1}{24}\right)\left(\frac{1}{12}\right)\left(\frac{2}{1}\right) \mod{5}\\&\equiv (-1)^k \cdot 1 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \mod{5}\\&\equiv (-1)^k \cdot 2 \mod{5}\end{align}$

We get $2$ carries when adding $m$ and $r$ in base $5$, so from Kummer's theorem, $k=2$. $\begin{array}{c}\color{blue}{\text{carry}}&\color{blue}{0}&\color{blue}{0}&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}\\m&-&0&0&1&3&1\\r&-&1&2&4&2&1\\\hline \\m+r&-&1&3&1&0&2\end{array}$

We thus have

$\begin{align}\frac{1}{5^2}\binom{1027}{41} &\equiv (-1)^2 \cdot 2 \mod{5}\\\iff \frac{1}{5^2}\binom{1027}{41}&=5j + 2 \text{ where } j \in \mathbb{N}\\\iff\binom{1027}{41} &= 125j + 50\\\iff\binom{1027}{41} &\equiv 50 \mod{125}\end{align}$

Similar steps for base $p=2$ give $\begin{align}\binom{1027}{41} &\equiv 0 \mod{8}\end{align}$

And so we get our answer:

$\begin{align}x&\equiv \binom{1027}{41} (\text{mod }{1000})\equiv 50 (\text{mod }{125})\equiv 0 (\text{mod }{8})\\\implies x &\in \{50, 175, 300, 425, 550, 675, \color{green}{800}, 975\} \cap \{0, 8, 16, \cdots, 792, \color{green}{800}, 808, \cdots 992\}\\\implies x &= {800}\end{align}$

$\endgroup$
1
$\begingroup$

$\sum_{i = 1}^{\infty} \left \lfloor \frac{1027}{5^i} \right \rfloor - \left \lfloor \frac{41}{5^i} \right \rfloor - \left \lfloor \frac{1027-41}{5^i} \right \rfloor= 2$ so there are only two trailing zeroes.

Therefore, it suffices to find the binomial coefficient modulo $1000$.

Now $\sum_{i = 1}^{\infty} \left \lfloor \frac{1027}{2^i} \right \rfloor - \left \lfloor \frac{41}{2^i} \right \rfloor- \left \lfloor \frac{1027-41}{2^i} \right \rfloor >3$ so $ \dbinom{1027}{41} \equiv 0 \pmod 8$.

Now to evaluate the expression modulo $125$, we rewrite it.

$\dbinom{1027}{41} = \frac{1027 \cdot 1026 \cdot 1025 \cdots 1001}{986 \cdot 985 \cdot 984 \cdots 960} \dbinom{1000}{959} \equiv \frac{27!}{111 \cdot 110 \cdots 85} \dbinom{1000}{959} $

$\dbinom{1000}{959} = \frac{1000}{959} \dbinom{999}{958} = \frac{42}{959} \dbinom{1000}{958}$.

Continuing in this fashion,

$\dbinom{1000}{959} = \frac{42 \cdot 43 \cdots 125}{959 \cdot 958 \cdots 876} \dbinom{1000}{875}$.

Now by Wolstenholme's Theorem which thats $\dbinom{ap}{bp} \equiv \dbinom{a}{b} \pmod {p^3}$, $\dbinom{1000}{875} \equiv \dbinom{8}7 \equiv 8 \pmod {125}$.

Now we need to evaluate $\frac{27! \cdot 42 \cdot 43 \cdots 125}{111 \cdot 110 \cdots 85 \cdot 876 \cdots 958 \cdot 959} \pmod {125}$.

We can rewrite this as $\frac{27! \cdot 42 \cdot 43 \cdots 125}{111!} \pmod {125}$.

Now we can cancel to get

$\frac{27! \cdot 42 \cdot 43 \cdots 125}{111!} \equiv \frac{ 112 \cdot 113 \cdots 125}{28 \cdot 29 \cdots 41} \pmod {125}$.

Then $\frac{112 \cdot 113 \cdots 124 \cdot 125}{28 \cdot 29 \cdots 41} \equiv \frac{(-1)(13!) \cdot 125}{28 \cdot 29 \cdots 41} \pmod {125}$.

Then $28 \cdot 29 \cdots 41 = 5^3K$ where $K \equiv 12 \pmod {125}$. (Easily get this by multiplying two numbers at the ends at one time and reduce.)

Finally, $\frac{(-1)(13!) \cdot 125}{28 \cdot 29 \cdots 41} \equiv \frac{-13!}{12} \equiv 100 \pmod {125}$.

Then finally, $\dbinom{1027}{41} \equiv 8 \cdot 100 \equiv 50 \pmod {125}$.

Solving the system $N \equiv 0 \pmod 8, N \equiv 50 \pmod {125}$ gives that $N \equiv 800 \pmod {1000}$ so the last non zero digit is $8$.

$\endgroup$
  • $\begingroup$ I don't know what method you really used to find the number of factors of twos and fives but the one you show in the answer is clearly incorrect $\endgroup$ – MCT Apr 29 '14 at 23:27
  • $\begingroup$ Please elaborate on how it is incorrect. This formula is well known. $\endgroup$ – Sandeep Silwal Apr 29 '14 at 23:36
  • $\begingroup$ Evaluate the first expression yourself and see what you get. I realize now what you're going for, but in its current form its wrong. $\endgroup$ – MCT Apr 29 '14 at 23:38
  • $\begingroup$ Oh I see. I will fix it. $\endgroup$ – Sandeep Silwal Apr 29 '14 at 23:45
  • 1
    $\begingroup$ @SandeepSilwal at several places in your answer you write that certain fractions with denominator divisible by $5$ are equal modulo 125. That looks fishy to me. So you use a definition of what $\frac{a}{b} \equiv \frac{c}{d} \ ({\sf mod}\ 125)$ means for any integers $a,b,c,d$ ? I only know one when $b$ and $d$ are coprime to $5$. $\endgroup$ – Ewan Delanoy Apr 30 '14 at 7:56

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.