Library / Saudi Arabian Mathematical Competitions /81 of 395

Saudi Arabian Mathematical Competitions

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 $n \geq 2$ , let $f(n)$ denote the number that is one more than the largest proper divisor of $n$ . Determine all positive integers $n$ such that $f(f(n))=2$ .

Solution

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

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

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

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

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.