Maths Olympiad Prep

Library / /29 of 39

Number theory Difficulty 5.7 AIME, harder Prove it Ireland

For any positive integer nn define
E(n)=n(n+1)(2n+1)(3n+1)(10n+1) E(n) = n(n + 1)(2n + 1)(3n + 1) \cdots (10n + 1)
Find the greatest common divisor of E(1)E(1), E(2)E(2), E(3)E(3), \ldots E(2009)E(2009).

Solution

Let mm be the g.c.d. of E(1),E(2),E(3),,E(2009)E(1), E(2), E(3), \dots, E(2009). Since mE(1)=2311m|E(1) = 2 \cdot 3 \dots 11, it follows that any prime divisor of mm is less than or equal to 1111. Let pp be a prime number such that pmp \nmid m. Since p11<2009p \le 11 < 2009, it follows that mE(p)=p(p+1)(2p+1)(3p+1)(10p+1)m|E(p) = p(p+1)(2p+1)(3p+1)\cdots(10p+1). Observe that p+1,2p+1,3p+1,,10p+1p+1, 2p+1, 3p+1, \dots, 10p+1 are relatively prime to pp. so E(p)E(p) (and thus mm) is divisible by pp but not by p2p^2. We have thus proved that mm is not divisible by the square of any prime number.

Since mE(1)=2311m|E(1) = 2 \cdot 3 \cdots 11, it follows that mm divides the product of all prime numbers less than or equal to 1111, that is, m2310m|2310.

To show that m=2310m = 2310 it is enough to prove that for all n1n \ge 1, the number E(n)E(n) is divisible by 23102310.

Let n1n \ge 1. Then, one of the numbers nn or n+1n+1 is divisible by 22, so 2E(n)2|E(n). Similarly, one of the numbers n,n+1,2n+1n, n+1, 2n+1 is divisible by 33 so 3E(n)3|E(n). Then, one of the numbers n,n+1,2n+1,3n+1,4n+1n, n+1, 2n+1, 3n+1, 4n+1 is divisible by 55 which yields 5E(n)5|E(n). In the same manner we obtain 7E(n)7|E(n) and 11E(n)11|E(n). Therefore E(n)E(n) is a multiple of 235711=23102 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310 and so, the g.c.d. is 23102310.

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 and solution reproduced as published; topic and difficulty added by this site.