Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If

p = last non zero digit of 96!

and

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

Find the value of p+q.

Thanks in advance.

How we can get the value from such big numbers?

Any link that gives more knowledge about this type of questions will be very much thankful.

share|improve this question
    
In your definition of $q$, do you mean to start with the number $1212\ldots 12$ where "$12$" is repeated 300 times? –  Arthur Fischer 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
add comment

4 Answers 4

up vote 10 down vote accepted

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

share|improve this answer
    
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
1  
@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
show 3 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.