A positive proper divisor is a positive divisor of a number, excluding itself. For positive integers $n \ge 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$.
Problem
Source: Saudi Arabia BMO TST Day I Problem 1
Tags: function, number theory, prime numbers, number theory unsolved
03.08.2014 20:10
$f(f(n))=2$ $\implies$ largest positive divisor of $f(n)$ is $1$ $\implies$ $f(n)=p$ a prime $\implies$ largest positive divisor of $n$ is $p-1$ If $p=2$ then the largest positive divisor of $n$ is $1$ so $n$ must be prime. If $p>2$ then $n$ is of the form $2(p-1),\,3(p-1),\,\ldots,\,q(p-1)$ where $q$ is the largest prime divisor of $p-1$.
03.08.2014 20:16
I believe it is , $n$ is prime or $n=2(p-1)$ where $p$ is a prime $>2$
04.08.2014 11:36
We have $f(f(n))=2$ so $f(n)$ is a prime number.Let $f(n)=p$ where $p$ is a prime number.If $p=2$ then the greatest proper divisor of n is 1,meaning that n is a prime number. Now suppose that $p>2$.If $n=p_1 ^ a_1 . p_2 ^ a_2 ... p_x ^ a_x$ ,where $p_1 <p_2 <...<p_x$ are distinct prime numbers and $a_1 ,a_2 ,...,a_x $ are positive integers,since $p-1$ is the gratest proper divisor of $n$ we must have $p-1=\dfrac{n}{p_1}=p_1 ^ (a_1 -1) . p_2 ^a_2 .... p_x ^a_x$.Denote the number $p_2 ^a_2 .... p_x ^a_x$ by $y$.If $a_1 > 0$, since $p-1$ is an even number and $y$ is an odd number it follows that $p_1 = 2$.Therefore in this case $n=2(p-1)$. If $a_1=1$ then $p-1=y$, but the number $p-1$ is even and the number $y$ is odd,contradicyion! In conclusion,$n$ is a prime number or $n=2(q-1)$ where $q$ is a prime number greater than 2.