Problem 2176

Solution:

Observe that $n=1$ is peculiar and that every prime is peculiar. Consider $\frac{n}{d}$, where $d>1$ is a divisor of $n$. Then $\frac{n}{d}\left(\frac{n}{d}+1\right)$ divides $n(n+1)$, equivalent to $n+d$ dividing $d^{2}(n+1)$. Since $n \equiv -d \pmod{n+d}$, we obtain that $n+d$ divides $d^{3}-d^{2}$, hence $n+d \leq d^{3}-d^{2}$ and in particular $n<d^{3}$. Now taking $d$ to be the smallest prime divisor of $n$, we deduce that $n$ cannot have more than two prime factors, counting multiplicities. Hence from now on we work with $n=pq$, where $p$ and $q$ are primes. In fact, $p \neq q$, as otherwise $p+1 \mid p^{2}-p$, i.e. $p+1 \mid 2$, contradiction.

Let us first prove that $n$ is square-free. Assume that $n=p^{k} h$, where $\operatorname{gcd}(p, h)=1$. Now $p^{k-1} h\left(p^{k-1} h+1\right) \mid p^{k} h\left(p^{k} h+1\right)$, which is equivalent to $\left(p^{k-1} h+1\right) \mid p\left(p^{k} h+1\right)$. Since $\operatorname{gcd}\left(p, p^{k-1} h+1\right)=1$, we must have
$$\left(p^{k-1} h+1\right) \mid \left(p^{k} h+1\right)=p^{k} h+p-p+1$$
so $\left(p^{k-1} h+1\right) \mid (p-1)$. If $k \geq 2$, this is a contradiction. Hence, $n$ is square-free.

Let us now show that $n$ has at most 2 different prime factors. Write $n=p_{1} p_{2} \cdots p_{k}$. Now we must have
$$p_{2} \cdots p_{k}\left(p_{2} \cdots p_{k}+1\right) \mid p_{1} \cdots p_{k}\left(p_{1} \cdots p_{k}+1\right)$$
which is equivalent to
$$\left(p_{2} \cdots p_{k}+1\right) \mid p_{1}\left(p_{1} \cdots p_{k}+1\right)$$
Now
$$p_{1}\left(p_{1} \cdots p_{k}+1\right)-p_{1}^{2}\left(p_{2} \cdots p_{k}+1\right)=p_{1}-p_{1}^{2}$$
Hence,
$$\left(p_{2} \cdots p_{k}+1\right) \mid p_{1}^{2}-p_{1}$$
Pick $p_{1}$ to be the smallest prime factor of $n$. Then $p_{2} \cdots p_{k}>p_{1}^{2}$ if $k>2$, which is a contradiction.

The only relations of concern are $p(p+1) \mid n(n+1)$ and $q(q+1) \mid n(n+1)$. The former yields $p(p+1) \mid p q(p q+1)$, i.e. $p+1 \mid q(p q+1)$, that is, $p+1 \mid q(q-1)$; analogously $q+1 \mid p(p-1)$. Without loss of generality assume $p>q$. If $q$ does not divide $p+1$, then since $p+1$ and $q$ are relatively prime, we obtain from $p+1 \mid q(q-1)$ that $p+1$ divides $q-1$ and hence $p<p+1 \leq q-1<q$, contradiction. Hence $q$ divides $p+1$. Also, $p$ does not divide $q+1$ due to $p>q$ (unless $p=q+1$, i.e. $p=3, q=2$, but then $p+1 \nmid q(q-1)$ ) and now from $q+1 \mid p(p-1)$ we deduce that $q+1$ divides $p-1$.

Write $p+1=m q$ for some positive integer $m$. Then $q+1$ divides $p-1=m q-2= m(q+1)-m-2$, so $q+1$ divides $m+2$. On the other hand, $p+1 \mid q(q-1)$ implies that $m$ divides $q-1$. If the ratio of the latter is greater than 1, then $m \leq \frac{q-1}{2}$, but $q+1$ dividing $m+2$ from above insists on $q \leq m+1$, so $m \leq \frac{q-1}{2} \leq \frac{m}{2}$, contradiction. Hence $m=q-1$ and we have proven the following: if $n>1$ is composite and peculiar, then $n=pq$, where $p>q$ are primes and $p=q^{2}-q-1$.

Hence from now on we work with $n=ab$, with $a<b$ primes. The only relations of concern are $a(a+1) \mid n(n+1)$ and $b(b+1) \mid n(n+1)$. The former yields $a(a+1) \mid ab(ab+1)$, i.e. $a+1 \mid b(ab+1)$, that is, $a+1 \mid b(b-1)$; analogously $b+1 \mid a(a-1)$. If $a$ does not divide $b+1$, then since $b+1$ and $a$ are relatively prime, we obtain from $b+1 \mid a(a-1)$ that $b+1$ divides $a-1$ and hence $b<b+1 \leq a-1<a$, contradiction. Hence $a$ divides $b+1$. Writing $b+1=ac$, from $b+1 \mid a(a-1)$ we have that $c$ divides $a-1$.

Now from $b+1=ac$ with $c \mid a-1$ and $a+1 \mid b(b-1)$ we derive that $b=a^{2}-a-1$ in a different (and longer) manner, without using the primality of $b$ until the final step. Note that since $b=ac-1 \equiv -c-2 \pmod{a+1}$, we have $a+1 \mid (c+1)(c+2)$. Since $c \mid a-1$, we may write $a-1=cd$, and note that $cd \equiv -2 \pmod{a+1}$. We then have
$$0 \equiv -d(c+1)(c+2) = -c^{2}d-3cd-2d \equiv 2(c-d)+6 \quad (\bmod a+1)$$
Since $1 \leq c, d \leq a-1$, we have $|2(c-d)+6| \leq 2(a-2)+6=2a+2$. Furthermore, we have $c \geq 2$ (otherwise $b=ac-1<a$, contradiction), and so $d \leq \frac{a-1}{2}$, thus $2(c-d)+6 \geq 11-a>-(a+1)$. From these inequalities and equivalence (1), we obtain $2(c-d)+6 \in\{0, a+1,2(a+1)\}$. It is immediate to verify that these three possible values correspond to the following three cases, respectively:
(i) $d=c+3$ and $a=c^{2}+3c+1$;
(ii) $d=2, c=\frac{a-1}{2}, a=2c+1$; and
(iii) $d=1, c=a-1$.
Substituting these values in $b=ac-1$, we obtain in case (i), $b=c^{3}+3c^{2}+c-1=(c+1)(c^{2}+2c-1)$, and in case (ii), $b=2c^{2}+c-1=(c+1)(2c-1)$. In both cases these decompositions contradict the primality of $b$, as $c \geq 2$. Thus we are left only with case (iii), where $b=a^{2}-a+1$, as claimed.

In conclusion, a prime $p$ can only divide the peculiar numbers $p$, $p(p^{2}-p-1)$ (if $p^{2}-p-1$ is prime) and $pq$ where $p=q^{2}-q-1$ (if $q$ is prime). In particular, the greatest common divisor of more than three peculiar numbers must be $1$. (Note that three peculiar numbers may indeed have a common divisor, e.g. $5, 15=3 \cdot 5$ and $95=5 \cdot 19$ are all peculiar.)