Number theoryDifficulty 5.5AIME, harderProve itUnited States
Problem:
For any integer x, let f(x)=100!(1+x+2!x2+3!x3+⋯+100!x100). A positive integer a is chosen such that f(a)−20 is divisible by 1012. Compute the remainder when f(a+101) is divided by 1012.
Solutions — 2
Solution 1
Solution:
By the binomial theorem, (a+101)n≡an+(1n)an−1101=an+101nan−1(mod1012). Using this gives (all congruences are modulo 1012) f(a+101)=100!n=0∑100n!(a+101)n≡100!n=0∑100(n!an+n!101nan−1)≡f(a)+100!⋅101n=1∑100(n−1)!an−1≡f(a)+101f(a)−100!⋅101100!a100≡f(a)+101(f(a)−1)≡20+101(20−1)=1939(mod1012).
Solution 2
Solution:
The above solution can be viewed as a consequence of Hensel's lemma as follows. Because 101 is prime, for any integer x not divisible by 101, we have that f′(x)=100!(1+x+2!x2+⋯+99!x99)=f(x)−x100≡f(x)−1(mod101). Clearly 101∤a. Hence, by Hensel's lemma, we get that f(a+101)≡f(a)+101f′(a)≡20+101⋅19≡1939(mod1012).
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.