# Find the sum of p+q?

If

p = last non zero digit of 96!

and

q = Remainder(121212....300 times / 99 )

Find the value of p+q.

How we can get the value from such big numbers?

-
In your definition of $q$, do you mean to start with the number $1212\ldots 12$ where "$12$" is repeated 300 times? – arjafi Mar 17 '12 at 14:07
sequence $121212$ is repeated $300$ times ? – pedja Mar 17 '12 at 14:07
@Arthur "12" is repeated 300 times – vikiiii Mar 17 '12 at 15:07

Calculating $p$:

First, note that the number of trailing zeros is the number of $5$s in the product. Every multiple of $5$ less than $96$ contributes one such factor, giving $19$ factors, and the numbers $25, 50, 75$ contribute an extra factor, giving $22$ trailing zeroes in total. So we want to find the value of

$$\frac{96!}{10^{22}} \bmod 10.$$

We will later use the Chinese Remainder Theorem on

\begin{align} \frac{96!}{10^{22}} &\bmod 2, \\ \frac{96!}{10^{22}} &\bmod 5,\end{align}

so that we now only have to find those two values separately. First, $96!$ contains many more factors $2$ than $5$, so

$$\frac{96!}{10^{22}} \equiv 0 \bmod 2.$$

Next, for the value modulo $5$, we first factor the number in two integers:

$$\frac{96!}{10^{22}} = \frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot \ldots \cdot 96}{2^{22}} \cdot \frac{5 \cdot 10 \cdot 15 \cdot \ldots \cdot 95}{5^{22}}.$$

Let us first look at the first term. Since

$$1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot \ldots \cdot 96 \equiv (1 \cdot 2 \cdot 3 \cdot 4)^{19} \cdot 1 \equiv 4^{19} \equiv (16)^9 \cdot 4 \equiv 4 \bmod 5,$$

and

$$2^{22} \equiv 16^{5} \cdot 4 \equiv 4 \bmod 5,$$

we get

$$\frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot \ldots \cdot 96}{2^{22}} \equiv 1 \bmod 5.$$

For the other term, we have to divide out all the factors $5$ in the product to get

\begin{align}\frac{5 \cdot 10 \cdot 15 \cdot 20 \cdot \ldots \cdot 95}{5^{22}} &= (1 \cdot 2 \cdot 3 \cdot 4 \cdot 1) (1 \cdot 2 \cdot 3 \cdot 4 \cdot 2) (1 \cdot 2 \cdot 3 \cdot 4 \cdot 3) (1 \cdot 2 \cdot 3 \cdot 4) \\ &\equiv (-1) \cdot (-2) \cdot 2 \cdot (-1) \\ &\equiv 1 \bmod 5.\end{align}

Combining these two terms, we get

$$\frac{96!}{10^{22}} = \frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot \ldots \cdot 96}{2^{22}} \cdot \frac{5 \cdot 10 \cdot 15 \cdot \ldots \cdot 95}{5^{22}} \equiv 1 \cdot 1 \equiv 1 \bmod 5.$$

So

\begin{align}\frac{96!}{10^{22}} &\equiv 0 \bmod 2, \\ \frac{96!}{10^{22}} &\equiv 1 \bmod 5.\end{align}

Solving this using CRT gives us

$$\frac{96!}{10^{22}} \equiv 6 \bmod 10.$$

So $p = 6$.

Calculating $q$:

Let $n = 121212\ldots12$ with the pattern $(12)$ repeated $300$ times. Using the Chinese Remainder Theorem, we only need to find $n \bmod 9$ and $n \bmod 11$ to recover $n \bmod 99$. Since the sum of the digits is $900$ and is divisible by $9$, we have

$$n \equiv 0 \bmod 9.$$

For $n \bmod 11$, we can use the following rule:

Lemma: If $n = d_k d_{k-1} d_{k-2} \ldots d_2 d_1 d_0$ is the decimal representation of $n$, then $n \equiv d_0 - d_1 + d_2 - d_3 \pm \ldots \pm d_k \equiv \sum_{i=0}^k d_i (-1)^i \bmod 11$.

Proof: $d_k d_{k-1} d_{k-2} \ldots d_2 d_1 d_0 = \sum_{i=0}^k d_i (10)^i \equiv \sum_{i=0}^k d_i (-1)^i \bmod 11$, where we used the fact that $10 \equiv -1 \bmod 11$.

Applying this to our $n$, we get $n \equiv - 1 + 2 - 1 + 2 \mp \ldots + 2 \equiv -300 + 600 \equiv 300 \equiv 3 \bmod 11$. So we apply the Chinese Remainder Theorem to

\begin{align} n &\equiv 0 \bmod 9, \\ n &\equiv 3 \bmod 11,\end{align}

to obtain

$$n \equiv 36 \bmod 99.$$

So $q = 36$.

Combining the results:

Combining the two answers above, we get $p + q = 42$.

-
Note that the first answer can be easily verified with a computer, i.e. Mathematica says $96! = 9916779\ldots639874560000000000000000000000$ so $p = 6$ indeed. – TMM Mar 17 '12 at 15:24
I think q should be 1 – Tomarinator Mar 17 '12 at 15:33
@5ToM: No. Trivially $n \equiv 0 \bmod 9$ so also $q \equiv 0 \bmod 9$, so $q \neq 1$. – TMM Mar 17 '12 at 15:39
Please have a look at my answer. because I still am getting q = 1. – Tomarinator Mar 17 '12 at 15:57
@TMM thank you so much for helping me on this question. – vikiiii Mar 18 '12 at 3:26

Hint $\$ Computing the remainder $\rm\:q\:$ is easy, simply cast $99$'s, as in casting nines, i.e.

$$\rm mod\ 99\!:\ \ 100\equiv 1\ \ \Rightarrow\ \ a + b\cdot 100 + c\cdot 100^2+d\cdot 100^3+\:\!\cdots\: \equiv\ a + b + c + d+\cdots$$

Therefore $\rm\: q \equiv 300\cdot 12 \equiv 3\cdot 12 \equiv 36\pmod{99}$

To find the last nonzero digit $\rm\:d\:$ of $\:96\:\!!\:$ it suffices to pull out factors of $10,\:$ then evaluate what remains modulo $10$. Since the product has more $2$'s than $5$'s, we infer $\rm\:d\:$ is even. Hence we need only determine $\rm d$ mod $5$. Fill an array row-wise with $1,2,\ldots,96$ as below, pulling out in each row a factor of $\color{blue}{\:2}\:$ from $\rm\:\color{blue}{10\:n+2},\:\:$ a factor of $\rm\:\color{red}5\:$ from $\rm\:\color{red}{10\:n+5},\:$ and a factor of $\color{green}{\:10}\:$ from $\rm\:\color{green}{10\:n+10},\:$ accumulating these factors into the last column (factors of $10$)

$$\begin{array}{} \color{blue}{01} & \color{blue}{01} & \color{blue}{03} & \color{blue}{04} & \color{red}{01} & 06 & 07 & 08 &09 & \color{green}{1}&|\quad \color{blue}{2}\cdot\color{red}{5}\cdot\color{green}{10}\\ \color{blue}{11} & \color{blue}{06} & \color{blue}{13} & \color{blue}{14} & \color{red}{03} & 16 & 17 & 18 &19 &\color{green}{2} &|\quad \color{blue}{2}\cdot\color{red}{5}\cdot\color{green}{10} \\ \color{blue}{21} & \color{blue}{11} & \color{blue}{23} & \color{blue}{24} & \color{red}{05} & 26 & 27 & 28 &29 &\color{green}{3} &|\quad \color{blue}{2}\cdot\color{red}{5}\cdot\color{green}{10} \\ & & \cdots & & & & & \cdots\\ \color{blue}{71} & \color{blue}{36} & \color{blue}{73} & \color{blue}{74} & \color{red}{15} & 76 & 77 & 78 &79 &\color{green}{8} &|\quad \color{blue}{2}\cdot\color{red}{5}\cdot\color{green}{10} \\ \color{blue}{81} & \color{blue}{41} & \color{blue}{83} & \color{blue}{84} & \color{red}{17} & 86 & 87 & 88 &89 &\color{green}{9} &|\quad \color{blue}{2}\cdot\color{red}{5}\cdot\color{green}{10} \\ \color{blue}{91} & \color{blue}{46} & \color{blue}{93} & \color{blue}{94} & \color{red}{19} & 96 \end{array}$$

Each blue subrow has product $\rm\equiv 1\cdot 1\cdot 3\cdot 4\equiv 2\pmod 5,\:$ thus the $10\:$ blue rows have product $\rm\:2^{10} \equiv (2^5)^2 \equiv 2^2\equiv 4\pmod 5.$ Each black subrow has product $\rm\equiv 1\cdot 2\cdot 3\cdot 4\equiv -1\pmod 5,\:$ therefore the $9$ black rows have product $\rm\equiv (-1)^9 \equiv -1\pmod 5.\:$ Multiply these with the products mod $5$ of the red column $1\cdot 3\cdot 5\cdots 19\:$ and the green column $9\:\!!$, after pulling out $10$'s.

-

I think that TMM answered correctly .

Maple program that calculates $p+q$ :

for n from 0 to 50 do
if not(96! mod 10^n = 0) then
p:=(96! mod 10^n)/(10^(n-1));
break;
end if;
end do;
q:=(sum(2*10^(2*i),i=0..299)+sum(10^(2*i+1),i=0..299)) mod 99:
print(p+q);


Output is $42$ .

-

My method for computing $q$ is as follows:

First note that if we define $a_1 = 12$ and a recurrence $a_{n+1} = 100a_n + 12$, then what we are looking for is the residue class of $a_{300}$ modulo $99$. Note that $100 \equiv 1 \pmod{99}$, and it follows that $a_{n+1} = 100 a_n + 12 \equiv 1 \cdot b + 12 \pmod{99} \equiv b + 12 \pmod{99}$. This quickly leads us to seeing that $a_n \equiv 12n \pmod{99}$. And therefore $$a_{300} \equiv 12 \cdot 300 \pmod{99} \equiv 3600 \pmod{99} \equiv 36 \pmod{99}.$$ Therefore $q = 36$.

I couldn't think of a novel non-brute-force method of computing $p$.

-