Legendre would be proud of you

The last 14 digits of 31 ! 31 ! are 255628 X Y 000000 \overline{255628XY000000} . Find X Y \overline{XY} .

Inspired by Calvin Lin


The answer is 80.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Henry U
Dec 15, 2018

First, let's see how many trailing zeroes there are in 31 ! 31! . For this, we look for pairs of numbers in 31 ! 31! whoose product is divisible by 10.

factors trailing zeroes
10 10 1
20 20 1
30 30 1
2 5 2 \cdot 5 1
4 25 4 \cdot 25 2
6 15 6 \cdot 15 1
total 7

The last six trailing zeroes are given in the problem, so one is missing, which means Y = 0 \boxed{Y = 0} .

In the remaining factors, there are still enough even numbers to make the product divisible by 16. The divisibility rule for 16 is that the numbrt formed by the last 4 digits is divisible by 16. This number is 628 X = 392 16 + 8 + X 628X = 392 \cdot 16 + 8 + X . To make it divisible by 16, X has to cancel out the 8, so X = 8 \boxed{X = 8} .

Combining both results, the answer is X Y = 80 \overline{XY} = \boxed{80} .

Chew-Seong Cheong
Dec 19, 2018

We can factorize a factorial as n ! = k = 1 p k q k n! = \displaystyle \prod_{k=1}^\infty p_k^{q_k} , where p k p_k is the k k th prime and q k q_k is the highest power of p k p_k . If p k p_k is not a factor of n ! n! , then q k = 0 q_k = 0 . We can find q k q_k by q k = j = 1 n p k j q_k = \displaystyle \sum_{j=1}^\infty \left \lfloor \frac n{p_k^j} \right \rfloor , where \lfloor \cdot \rfloor denotes the floor function. For n = 31 n=31 , we get:

31 ! = 2 26 3 14 5 7 7 4 1 1 2 1 3 2 1 7 1 1 9 1 2 3 1 2 9 1 3 1 1 As 2 7 5 7 = 1 0 7 = 2 19 3 14 7 4 1 1 2 1 3 2 1 7 1 1 9 1 2 3 1 2 9 1 3 1 1 1 0 7 or 7 trialing 0’s \begin{aligned} 31! & = {\color{#3D99F6}2^{26}}\cdot3^{14}\cdot {\color{#3D99F6}5^{7}} \cdot7^{4}\cdot11^{2}\cdot13^{2}\cdot17^{1}\cdot19^{1}\cdot23^{1}\cdot29^{1}\cdot31^{1} & \small \color{#3D99F6} \text{As }2^7 \cdot 5^7 = 10^7 \\ & = {\color{#3D99F6}2^{19}}\cdot3^{14} \cdot7^{4}\cdot11^{2}\cdot13^{2}\cdot17^{1}\cdot19^{1}\cdot23^{1}\cdot29^{1}\cdot31^{1} \cdot \color{#3D99F6} 10^7 & \small \color{#3D99F6} \text{or 7 trialing 0's} \end{aligned}

This means that Y = 0 Y=0 . Now let N = 31 ! 1 0 7 N = \dfrac {31!}{10^7} . Then X = N m o d 10 X = N \bmod 10 .

N 2 19 3 14 7 4 1 1 2 1 3 2 17 19 23 29 31 (mod 10) ( 1 6 4 8 ) 9 7 4 9 2 1 2 3 2 7 9 3 9 1 (mod 10) ( 6 8 ) ( 10 1 ) 7 ( 50 1 ) 2 ( 1 ) ( 1 ) ( 7 ) ( 1 ) ( 3 ) ( 1 ) ( 1 ) (mod 10) ( 8 ) ( 1 ) ( 1 ) ( 1 ) ( 1 ) (mod 10) 8 (mod 10) \begin{aligned} N & \equiv 2^{19}\cdot3^{14} \cdot7^{4}\cdot11^{2}\cdot13^{2}\cdot 17 \cdot19 \cdot 23 \cdot 29\cdot 31 \text{ (mod 10)} \\ & \equiv (16^4 \cdot 8) \cdot 9^7 \cdot 49^2 \cdot 1^2 \cdot 3^2 \cdot 7 \cdot 9 \cdot 3 \cdot 9 \cdot 1 \text{ (mod 10)} \\ & \equiv (6\cdot 8) (10-1)^7 (50-1)^2 (1)(-1)(7) (-1) (3) (-1)(1) \text{ (mod 10)} \\ & \equiv (8) (-1)(-1)(-1)(-1) \text{ (mod 10)} \\ & \equiv 8 \text{ (mod 10)} \end{aligned}

Implying X = 8 X=8 and X Y = 80 \overline{XY} = \boxed{80} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...