Maths Olympiad Prep

Library / /618 of 860

Algebra Difficulty 5.3 AIME, harder Find the answer

Let f(x)=x2+x+1f(x)=x^{2}+x+1. Determine, with proof, all positive integers nn such that f(k)f(k) divides f(n)f(n) whenever kk is a positive divisor of nn.

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

Solution

Answer: nn can be 1, a prime that is 1mod31 \bmod 3, or the square of any prime except 3. Solution: The answer is nn can be 1, a prime that is 1mod31 \bmod 3, or the square of any prime except 3. It is easy to verify that all of these work. First note that nn must be 1mod31 \bmod 3 since 1 divides nn implies f(1)f(1) divides f(n)f(n). Next, suppose for sake of contradiction that n=abn=ab, with a>b>1a>b>1. We are given that f(a)f(a) divides f(n)f(n), which means f(a)f(a) divides f(n)f(a)f(n)-f(a). We can write this as a2+a+1n2+na2a=(na)(n+a+1) a^{2}+a+1 \mid n^{2}+n-a^{2}-a=(n-a)(n+a+1) Since we are working moda2+a+1\bmod a^{2}+a+1, we can replace a+1a+1 with a2-a^{2}, so we have a2+a+1(na)(na2)=a2(b1)(ba) a^{2}+a+1 \mid(n-a)\left(n-a^{2}\right)=a^{2}(b-1)(b-a) However, a2+a+1a^{2}+a+1 cannot share any factors with aa, and 0<(b1)(ba)<a2+a+10<|(b-1)(b-a)|<a^{2}+a+1, which is a contradiction.

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.