Maths Olympiad Prep

Library / /976 of 1394

Number theory Difficulty 5.5 AIME, harder Prove it United States

Problem:

For any integer xx, let
f(x)=100!(1+x+x22!+x33!++x100100!). f(x) = 100! \left(1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \dots + \frac{x^{100}}{100!}\right).
A positive integer aa is chosen such that f(a)20f(a) - 20 is divisible by 1012101^{2}. Compute the remainder when f(a+101)f(a + 101) is divided by 1012101^{2}.

Solutions — 2

Solution 1

Solution:

By the binomial theorem,
(a+101)nan+(n1)an1101=an+101nan1(mod1012). (a + 101)^{n} \equiv a^{n} + \binom{n}{1} a^{n - 1}101 = a^{n} + 101n a^{n - 1} \pmod {101^{2}}.
Using this gives (all congruences are modulo 1012101^{2})
f(a+101)=100!n=0100(a+101)nn!100!n=0100(ann!+101nan1n!)f(a)+100!101n=1100an1(n1)!f(a)+101f(a)100!101a100100!f(a)+101(f(a)1)20+101(201)=1939(mod 1012). \begin{align*} f(a + 101) &= 100!\sum_{n = 0}^{100}\frac{(a + 101)^{n}}{n!} \\ &\equiv 100!\sum_{n = 0}^{100}\left(\frac{a^{n}}{n!} +\frac{101n a^{n - 1}}{n!}\right) \\ &\equiv f(a) + 100!\cdot 101\sum_{n = 1}^{100}\frac{a^{n - 1}}{(n - 1)!} \\ &\equiv f(a) + 101f(a) - 100!\cdot 101\frac{a^{100}}{100!} \\ &\equiv f(a) + 101(f(a) - 1) \\ &\equiv 20 + 101(20 - 1) = \boxed{1939}\quad (\mathrm{mod}\ 101^{2}). \end{align*}

Solution 2

Solution:

The above solution can be viewed as a consequence of Hensel's lemma as follows. Because 101101 is prime, for any integer xx not divisible by 101101, we have that
f(x)=100!(1+x+x22!++x9999!)=f(x)x100f(x)1(mod101). f^{\prime}(x) = 100!\left(1 + x + \frac{x^{2}}{2!} +\dots +\frac{x^{99}}{99!}\right) = f(x) - x^{100}\equiv f(x) - 1\pmod {101}.
Clearly 101a101 \nmid a. Hence, by Hensel's lemma, we get that
f(a+101)f(a)+101f(a)20+101191939(mod1012). f(a + 101) \equiv f(a) + 101f^{\prime}(a) \equiv 20 + 101 \cdot 19 \equiv \boxed{1939} \pmod {101^{2}}.

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.