Maths Olympiad Prep

Library / /438 of 860

Algebra Difficulty 5.2 AIME, harder Find the answer

Let a1=3a_{1}=3, and for n1n \geq 1, let an+1=(n+1)anna_{n+1}=(n+1) a_{n}-n. Find the smallest m2005m \geq 2005 such that am+11am21a_{m+1}-1 \mid a_{m}^{2}-1.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We will show that an=2n!+1a_{n}=2 \cdot n!+1 by induction. Indeed, the claim is obvious for n=1n=1, and (n+1)(2n!+1)n=2(n+1)!+1(n+1)(2 \cdot n!+1)-n=2 \cdot(n+1)!+1. Then we wish to find m2005m \geq 2005 such that 2(m+1)!4(m!)2+4m2(m+1)!\mid 4(m!)^{2}+4 m !, or dividing by 2m2 \cdot m !, we want m+12(m!+1)m+1 \mid 2(m!+1). Suppose m+1m+1 is composite. Then it has a proper divisor d>2d>2, and since dmd \mid m !, we must have d2d \mid 2, which is impossible. Therefore, m+1m+1 must be prime, and if this is the case, then m+1m!+1m+1 \mid m!+1 by Wilson's Theorem. Therefore, since the smallest prime greater than 2005 is 2011, the smallest possible value of mm is 2010.

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.