Maths Olympiad Prep

Library / /827 of 860

Algebra Difficulty 5.7 AIME, harder Find the answer

Let P(n)=(n13)(n23)(n403)P(n)=\left(n-1^{3}\right)\left(n-2^{3}\right) \ldots\left(n-40^{3}\right) for positive integers nn. Suppose that dd is the largest positive integer that divides P(n)P(n) for every integer n>2023n>2023. If dd is a product of mm (not necessarily distinct) prime numbers, compute mm.

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

Solution

We first investigate what primes divide dd. Notice that a prime pp divides P(n)P(n) for all n2024n \geq 2024 if and only if {13,23,,403}\left\{1^{3}, 2^{3}, \ldots, 40^{3}\right\} contains all residues in modulo pp. Hence, p40p \leq 40. Moreover, x31x^{3} \equiv 1 must not have other solution in modulo pp than 1, so p≢1(mod3)p \not \equiv 1(\bmod 3). Thus, the set of prime divisors of dd is S={2,3,5,11,17,23,29}S=\{2,3,5,11,17,23,29\}. Next, the main claim is that for all prime pSp \in S, the minimum value of νp(P(n))\nu_{p}(P(n)) across all n2024n \geq 2024 is 40p\left\lfloor\frac{40}{p}\right\rfloor. To see why, note the following: - Lower Bound. Note that for all nZn \in \mathbb{Z}, one can group n13,n23,,n403n-1^{3}, n-2^{3}, \ldots, n-40^{3} into 40p\left\lfloor\frac{40}{p}\right\rfloor contiguous blocks of size pp. Since p≢1(mod3),x3p \not \equiv 1(\bmod 3), x^{3} span through all residues modulo pp, so each block will have one number divisible by pp. Hence, among n13,n23,,n403n-1^{3}, n-2^{3}, \ldots, n-40^{3}, at least 40p\left\lfloor\frac{40}{p}\right\rfloor are divisible by pp, implying that νp(P(n))>40p\nu_{p}(P(n))>\left\lfloor\frac{40}{p}\right\rfloor. - Upper Bound. We pick any nn such that νp(n)=1\nu_{p}(n)=1 so that only terms in form np3,n(2p)3n-p^{3}, n-(2 p)^{3}, \ldots are divisible by pp. Note that these terms are not divisible by p2p^{2} either, so in this case, we have νp(P(n))=40p\nu_{p}(P(n))=\left\lfloor\frac{40}{p}\right\rfloor. Hence, νp(d)=40p\nu_{p}(d)=\left\lfloor\frac{40}{p}\right\rfloor for all prime pSp \in S. Thus, the answer is pS40p=402+403+405+4011+4017+4023+4029=48\sum_{p \in S}\left\lfloor\frac{40}{p}\right\rfloor=\left\lfloor\frac{40}{2}\right\rfloor+\left\lfloor\frac{40}{3}\right\rfloor+\left\lfloor\frac{40}{5}\right\rfloor+\left\lfloor\frac{40}{11}\right\rfloor+\left\lfloor\frac{40}{17}\right\rfloor+\left\lfloor\frac{40}{23}\right\rfloor+\left\lfloor\frac{40}{29}\right\rfloor=48

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.