Maths Olympiad Prep

Library / /2 of 8

Number theory Difficulty 3.2 AMC 10/12 Find the answer Japan

Determine the last 3 digits of the number obtained by multiplying all the odd numbers between 11 and 100100.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let NN be the product of all the odd integers lying in between 11 and 100100. It is clear that the last 33 digits of NN equals the remainder obtained when NN is divided by 10001000. Note that 1000=103=23×53=8×1251000 = 10^3 = 2^3 \times 5^3 = 8 \times 125.

From the identity (8x+a)(8y+b)=8(axy+a+b)+ab(8x + a)(8y + b) = 8(axy + a + b) + ab, valid for any choice of integers x,y,a,bx, y, a, b, it follows that for any integer PP which can be written as a product P1P2P_1P_2 of integers P1P_1 and P2P_2, the remainder obtained when PP is divided by 88 is the same as the product of the remainders obtained when P1P_1 and P2P_2 are divided by 88, respectively. Therefore, the remainder obtained by dividing NN by 88 must be the product of the remainders obtained when each odd integer lying in between 11 and 100100 are divided by 88.

When odd numbers 1,3,5,7,9,11,1, 3, 5, 7, 9, 11, \dots are divided by 88 the remainders 1,3,3,1,1,1, 3, -3, -1, 1, \dots are obtained, and one can see easily that the block of 44 numbers 1,3,3,11, 3, -3, -1, repeats 1212 times and followed by 1,31, 3 (as 97=8×12+197 = 8 \times 12 + 1 and 99=8×13+399 = 8 \times 13 + 3). Therefore, we can conclude that the remainder obtained when NN is divided by 88 equals the remainder obtained by dividing 3253^{25} by 88, and this number equals 33, since 325=912×33^{25} = 9^{12} \times 3, and the remainder obtained by dividing 99 by 88 is 11.

Furthermore, since 10001000 is divisible by 88, the remainder obtained when the last 33-digits of NN is divided by 88 must also be 33. From these considerations we conclude that the solution to the problem is given by the number between 00 and 999999 which is a multiple of 125125 and gives a remainder 33 when divided by 88. The number 875875 is the only number satisfying these requirements and is the desired answer.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.