For all integers $n\ge 2$ with the following property: for each pair of positive divisors $k,~\ell <n$, at least one of the numbers $2k-\ell$ and $2\ell-k$ is a (not necessarily positive) divisor of $n$ as well.
Problem
Source: Benelux MO 2014 Problem 3
Tags: inequalities, number theory unsolved, number theory
20.07.2014 05:08
Let call a positive integer satisfying these conditions a pretty number. If $k=l$, then $2k-l = 2l-k=k$, which is a divisor of $n$. If $n$ is a prime, the only proper divisor (i.e. a divisor $< n$) of $n$ is 1, which means $k=l=1$ is the only possibility. Hence all primes are pretty numbers. Next assume $n>2$ is even. Then ${\textstyle k=\frac{n}{2}}$ and $l=1$ are proper divisors of $n$. Thus $ {\textstyle 2k - l = n-1}$ or ${\textstyle 2l - k = 2 - \frac{n}{2}}$ is a divisor of $n$. In other words, ${\textstyle \frac{n}{n-1}}$ or ${\textstyle \frac{n}{\frac{n}{2} - 2} = \frac{2n}{n-4}}$ is an integer. Hence $n-1|1$ or $n-4|8$, which give us $n \in \{6,8,12\}$. Now 6 is a pretty number, but 8 $(k=2$ and $l=1$ yield $2k-l=3$ and $2l-k=0)$ and 12 $(k=6$ and $l=3$ yield $2k-l = 9$ and $2l-k=0)$ are not pretty numbers. Hence the only even pretty numbers are 2 and 6. Now assume $n$ is a composite odd integer. Let $p$ be the smallest prime divisor of $n$. Obviously $p$ is odd since $n$ is odd. Futhermore ${\textstyle k=\frac{n}{p}}$ and $l=1$ both are proper divisors of $n$. Thus $ {\textstyle 2k - l =2\frac{n}{p} - 1}$ or ${\textstyle 2l - k =2 - \frac{n}{p}}$ is a divisor of $n$. In other words, ${\textstyle \frac{n}{2\frac{n}{p}-1}}$ or ${\textstyle \frac{n}{\frac{n}{p} - 2}}$ is an integer. So we have to consider the following two cases: Case 1: ${\textstyle \frac{n}{2\frac{n}{p}-1} \in \mathbb{Z}}$. Let $d_1=GCD(n,{\textstyle 2\frac{n}{p}-1})$. Assume $q \neq p$ is a prime divisor of $d_1$. Then $q|n$ and ${\textstyle q|2\frac{n}{p}-1}$. Combining this with the fact that $p$ and $q$ are distinct primes implies $q|{\textstyle \frac{n}{p}}$, yielding ${\textstyle q | 2\frac{n}{p} - (2\frac{n}{p} - 1)}$, i.e. $q|1$. This contradiction means $p$ is the only prime divisor of $n$. Let us assume $p^2 | d_1$. Then $p^2 | n$ and ${\textstyle p|2\frac{n}{p}-1}$, yielding ${\textstyle p|\frac{n}{p}}$ and ${\textstyle p | 2\frac{n}{p} - (2\frac{n}{p} - 1)}$, i.e. $p|1$. Hence by contradiction we obtain $d_1 \in \{1,p\}$. The fact that ${\textstyle \frac{n}{2\frac{n}{p}-1} \in \mathbb{Z}}$ and $d_1=GCD(n,{\textstyle 2\frac{n}{p}-1})$ implies ${\textstyle 2\frac{n}{p}-1 = d_1}$. Therefore ${\textstyle 2\frac{n}{p}-1 = 1}$, i.e. $n=p$ (which is impossible since $n$ is not a prime) or ${\textstyle 2\frac{n}{p}-1 = p}$, i.e. ${\textstyle n=\frac{p(p+1)}{2}}$. But ${\textstyle \frac{p+1}{2}}$ (and $n$) must have a prime divisor ${\textstyle \leq \frac{p+1}{2}}$, implying ${\textstyle \frac{p+1}{2} \geq p}$ by the minimality of $p$. This inequality give us the contradiction $p \leq 1$. In other words, ${\textstyle \frac{n}{2\frac{n}{p}-1} \not \in \mathbb{Z}}$. Case 2: ${\textstyle \frac{n}{\frac{n}{p}-2} \in \mathbb{Z}}$. Let $d_2=GCD(n,{\textstyle \frac{n}{p}-2})$. Assume $q \neq p$ is a prime divisor of $d_2$. Clearly $q$ is odd since $n$ is odd. Moreover $q|n$ and ${\textstyle q|\frac{n}{p}-2}$. Therefore $q|{\textstyle \frac{n}{p}}$ since $p$ and $q$ are distinct primes, implying ${\textstyle q | \frac{n}{p} - (\frac{n}{p} - 2)}$, i.e. $q|2$, which is impossible since $q>2$. Let us assume $p^2 | d_2$. Then $p^2|n$ and ${\textstyle p|\frac{n}{p}-2}$ since $d_2|n$, yielding ${\textstyle p|\frac{n}{p}}$ and ${\textstyle p | \frac{n}{p} - (\frac{n}{p} - 2)}$, i.e. $p|2$, contradicting $p>2$. Thus $d_2 \in \{1,p\}$, which combined with the fact that ${\textstyle d_2 = \frac{n}{p}-2}$ result in $n \in \{3p,p(p+2)\}$. So we have the following two possibilities: (I) $n=3p$. Then $k=p$ and $l=1$ are two proper divisors of $n$. Therefore $2k-l = 2p-1$ or $2l-k=2-p$ is a divisor of $n=3p$, which means $2p-1|3p$ or $p-2|3p$, implying $2p-1|3$ since $GCD(p,2p-1)=1$ or $p-2|3 \cdot 2 = 6$. Consequently $p \in \{1,2,3,4,5,8\}$, yielding $p=3$ or $p=5$ because $p$ is an odd prime. Both $n = 3 \cdot 3 = 9$ and $n = 3 \cdot 5 = 15$ are pretty numbers. (II) $n=p(p+2)$. Then $k=p+2$ and $l=p$ are two proper divisors of $n$. Therefore $2k-l = 2(p+2)-p = p+4$ or $2l-k=2p-(p+2) = p-2$ is a divisor of $n=p(p+2)$, which means $p+4|p(p+2)$ or $p-2|p(p+2)$. Hence $p+4|-4(-4+2)=8$ or $p-2|2 \cdot 4 = 8$, yielding $p=3$ and $n = 3 \cdot 5 = 15$, which we know is pretty number. Conclusion: The only pretty numbers are primes and the composite numbers 6, 9 and 15.