Maths Olympiad Prep

Library / /353 of 520

Number theory Difficulty 3.4 AMC 10/12 Find the answer

For how many positive integers nn less than or equal to 2424 is n!n! evenly divisible by 1+2++n?1 + 2 + \cdots + n?

Pick one

Solution

Since 1+2++n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}, the condition is equivalent to having an integer value for n!n(n+1)2\frac{n!} {\frac{n(n+1)}{2}}. This reduces, when n1n\ge 1, to having an integer value for 2(n1)!n+1\frac{2(n-1)!}{n+1}. This fraction is an
integer unless n+1n+1 is an odd prime. There are 88 odd primes less than or equal to 2424, so there
are 248=(C) 1624 - 8 = \boxed{\textbf{(C) }16} numbers less than or equal to 2424 that satisfy the condition.

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