Maths Olympiad Prep

Library / /1 of 12

Algebra Difficulty 7.3 National olympiad, round 2 Prove it Netherlands

The sequence a0,a1,a2,a_0, a_1, a_2, \dots of integers is defined by a0=3a_0 = 3 and
an+1an=n(an1) a_{n+1} - a_n = n(a_n - 1)
for all n0n \ge 0. Determine all integers m2m \ge 2 for which gcd(m,an)=1\gcd(m, a_n) = 1 for all n0n \ge 0.

Solution

The sequence is given by the formula an=2n!+1a_n = 2 \cdot n! + 1 for n0n \ge 0. (We use the usual definition 0!=10! = 1, which satisfies 1!=10!1! = 1 \cdot 0!, in the same way we have n!=n(n1)!n! = n \cdot (n-1)! for other positive integers nn.) We will prove the equality by induction. We have a0=3a_0 = 3, which equals 20!+12 \cdot 0! + 1. Now suppose for certain k0k \ge 0 that ak=2k!+1a_k = 2 \cdot k! + 1, then
ak+1=ak+k(ak1)=2k!+1+k2k!=2k!(1+k)+1=2(k+1)!+1. a_{k+1} = a_k + k(a_k - 1) = 2 \cdot k! + 1 + k \cdot 2 \cdot k! = 2 \cdot k! \cdot (1+k) + 1 = 2 \cdot (k+1)! + 1.
This finishes the induction.

We see that ana_n is always odd, hence gcd(2,an)=1\gcd(2, a_n) = 1 for all nn. It follows also that gcd(2i,an)=1\gcd(2^i, a_n) = 1 for all i1i \ge 1. Hence, m=2im = 2^i with i1i \ge 1 satisfies the condition. Now consider an m2m \ge 2 which is not a power of two. Then mm has an odd prime divisor, say pp. We will show that pp is a divisor of ap3a_{p-3}. By Wilson's theorem, we have (p1)!1(modp)(p-1)! \equiv -1 \pmod{p}. Hence,
2(p3)!2(p1)!((p2)(p1))121(21)121211(modp). \begin{aligned} 2 \cdot (p-3)! &\equiv 2 \cdot (p-1)! \cdot ((p-2)(p-1))^{-1} \\ &\equiv 2 \cdot -1 \cdot (-2 \cdot -1)^{-1} \equiv 2 \cdot -1 \cdot 2^{-1} \equiv -1 \pmod{p}. \end{aligned}
So indeed we have ap3=2(p3)!+10(modp)a_{p-3} = 2 \cdot (p-3)! + 1 \equiv 0 \pmod{p}. We conclude that mm does not satisfy the condition. Hence, the only values of mm satisfying the condition are powers of two. \square

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.