Maths Olympiad Prep

Library / /21 of 133

Number theory Difficulty 5.0 AIME Prove it Saudi Arabia

A positive proper divisor is a positive divisor of a number, excluding itself. For positive integers n2n \geq 2, let f(n)f(n) denote the number that is one more than the largest proper divisor of nn. Determine all positive integers nn such that f(f(n))=2f(f(n))=2.

Solution

Let n2n \geq 2 such that f(f(n))=2f(f(n))=2. The largest proper divisor of f(n)f(n) is 1 if and only if f(n)f(n) is a prime number.

If f(n)=2f(n)=2, this is equivalent to nn being a prime number.

If f(n)=p3f(n)=p \geq 3, then p1p-1, the largest proper divisor of nn is an even number. This means that nn is even and therefore, its largest proper divisor is n2\frac{n}{2}. This is equivalent to n=2(p1)n=2(p-1).

Hence, the positive integers nn such that f(f(n))=2f(f(n))=2 are prime numbers or numbers n=2(p1)n=2(p-1) for any prime number pp.

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.