Let $n$ be an arbitrary peculiar number and let $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ where $p_1 < p_2 < \dots < p_k$ be its prime factorization. Then, we have $\frac{n}{p_1}(\frac{n}{p_1}+1) \mid n(n+1)$ which implies $\frac{n}{p_1}+1 \mid n(n-\frac{n}{p_1})$. Since $\gcd(\frac{n}{p_1}+1, \frac{n}{p_1})=1$, this actually implies that $\frac{n}{p_1} +1 \mid p_1(p_1-1)$ and hence $p_2^{\alpha_2}\dots p_k^{\alpha_k} + 1 = \frac{n}{p_1}+1 \leq p_1(p_1-1)$. Therefore, $\alpha_2+\alpha_3+ \dots + \alpha_k = 1$ by the minimality of $p_1$. Hence, $n$ is either a prime or of the form $pq$ where $p$ and $q$ are primes. Let $pq$ be a peculiar number. Note that $pq$ being a peculiar number implies $p+1 \mid q(q-1)$ and $q+1 \mid p(p-1)$. Since we obviously can't have $p=q$, we may assume that $p>q$. If we have $q \nmid p+1$, we get $p+1 \mid q-1 \implies p+1 \leq q-1$ which contradicts $p>q$. Hence, $q \mid p+1$. Let $qk=p+1$. We must have $k \leq q-1$ because $qk=p+1 \mid q(q-1) \implies k \mid q-1$. Additionally, since $p>q$, we must have $p \nmid q+1$ which implies that $q+1 \mid p-1=qk-2$. Let $(q+1)s=qk-2$. It is evident that $s<k \leq q-1$. On the other hand, we have $2 \equiv (q+1)s \equiv s \pmod{q}$. Combining these results together, we may conclude that $q-2=s$. Therefore, $p=qk-1=(q+1)(q-2)+1=q^2-q-1$. Hence, for all primes $p$, there are at most $2$ distinct primes such that $pq$ is peculiar. In particular, one such that $p<q$ and one such that $p>q$. This implies the result. $\blacksquare$

What a joke! Let $n{}$ be peculiar and let $p{}$ be its smallest prime divisor. Then, letting $d=n/p$ it follows that $n/p+1{}$ divides $p(n+1).$ Evidently, $n/p+1$ divides $pn+p^2$ hence $n/p+1$ divides $p^2-p.$ It follows that $n<p^3$ so $\Omega(n)\leqslant 2.$ One may also trivially see that $n\neq p^2$ by choosing $d=p.{}$ So, any peculiar number is either prime, or of the form $n=pq$ for some prime numbers which satisfy $p+1\mid q(q-1)$ and $q+1\mid p(p-1).$ Therefore, it suffices to show that for a fixed prime $p$ there exist at most two primes $q{}$ with the previous properties. Assume, for the sake of contradiction, that at least three such primes exist. Evidently, $p\neq 2.{}$ By the pigeonhole principle, two of them are both greater or both smaller than $p{}.$ First, assume that $q_1,q_2>p.{}$ Fix $i=1,2$ arbitrarily. Since $q_i>p$ then $q_i+1\nmid p-1$ so because $q_i+1\mid p(p-1)$ we must have $p\mid q_i+1.$ Also, $q_i\neq p+1{}$ so from $p+1\mid q_i(q_i-1)$ we have $p+1\mid q_i-1.$ Thus, the primes $q_1,q_2{}$ satisfy the system of congruences \[q_i\equiv -1\bmod p,\quad q_i\equiv 1\bmod{p+1}.\]Therefore, at least one of the primes $q_1,q_2{}$ is greater than $p(p+1)$ which is absurd, because $q_i\mid p(p-1)$ for each $i.{}$ Now, assume that $q_1,q_2<p.{}$ Fix $i=1,2.{}$ Evidently, $q_i\neq p-1$ so $\gcd(p,q_i+1)=1$ which gives us $q_i+1\mid p-1.$ Also, because $q_i<p$ then $p+1\nmid q_i-1$ so from $p+1\mid q_i(q_i-1)$ we get $q_i\mid p+1.{}$ So, $p{}$ satisfies the congruences \[p\equiv -1\bmod{q_i},\quad p\equiv 1\bmod{q_i+1},\]so $p\geqslant q_i^2-q_i-1.$ However, $p+1\mid q_i(q_i-1)$ so this would imply $p=q_i^2-q_i-1$ for both $q_1,q_2$ which is absurd. Remark. There exist three peculiar numbers whose gcd is greater than one. For instance, $5,5\cdot 3$ and $5\cdot 19$ are all peculiar. Also, note that we've actually characterised all the triples of peculiar numbers $a,b,c$ with gcd greater than one. They are \[(p,p\cdot q, p\cdot r),\quad p=q^2-q-1,\quad r=p^2-p-1,\]where $p,q,r$ are prime numbers. I wonder if infinitely many triples exist.

Iveela wrote: If we have $q \nmid p+1$, we get $q+1 \mid p-1 \implies q+1 \leq p-1$ which contradicts $p>q$. Hence, $q \mid p+1$. How does this contradicts.

This solution, although a bit lengthy, felt rather straightforward.

We will show below that peculiar integers are exactly those of the form $n=1$, $n=p$ for $p$ prime and $n=p\left(p^2-p-1\right)$ for $p$ and $p^2-p-1$ prime. This would then complete the proof as the only possibilities for peculiar integers that are divisible by a prime $p$ are $n \in \left\{p,p\left(p^2-p-1\right),q\left(q^2-q-1\right)\right\}$ where $q^2-q-1=p$ and in particular, there are at most $3$ possibilities. Assume $n$ is peculiar. If $a \mid n$, then writing $n=ab$ and choosing $d=b$ we have: $$ b(b+1) \mid n(n+1)=ab(ab+1) \implies b+1 \mid a(ab+1) \implies b+1 \mid a(a-1) \quad \quad (\ast) $$ Claim 1: $n$ is square-free. Proof: If $p^2 \mid n$ for a prime $p$ then choosing $a=p$, $b=kp$ in $(\ast)$ gives $$ kp+1 \mid p \left(p-1\right) \xRightarrow{p \text{ prime}} kp+1 \mid p-1. $$But this can't happen since $0<p-1<kp+1$. Claim 2: $n$ is divisible by at most $2$ primes (counting multiplicity). Proof: Let $p \mid n$ for a prime $p$ and write $n=bp$. Using $(\ast)$ with $a=p$: $$ b+1 \mid p(p-1) \implies b=\frac{n}{p} \leq p(p-1)-1 \implies n \leq p^3-p^2-p $$If $n$ is divisible by $3$ (not necessarily distinct) primes $p \leq p_2 \leq p_3$ then we'd have $n \geq p p_2 p_3 \geq p^3$ which contradicts the above. Combining the above claims, we see the only possibilities for $n$ are $n=1$, $n=p$, $n=p^2$, $n=pq$ for distinct primes $p<q$. $n=1$ and $n=p$ can easily be seen to be peculiar. $n=p^2$ is not peculiar since: $$ p(p+1) \mid p^2 \left(p^2+1\right) \implies p+1 \mid p\left(p^2+1\right) \implies p+1 \mid p^2+1 \implies p+1 \mid 2 $$which can't happen. For $n=pq$, setting $d=p$ we get: $$ p(p+1) \mid pq(pq+1) \implies p+1 \mid q(pq+1) $$If $p=2$, $q=3$ then $n=6$ which isn't peculiar since $3(3+1) \nmid 6(6+1)$. Otherwise, $p+1<q$ (as $p<q$) and so $q \nmid p+1$ this means the above implies: $$ p+1 \mid pq+1 \implies p+1 \mid q-1 \implies q=k(p+1)+1 $$for some $k \geq 1$. Now choosing $d=q$ we have: $$ q(q+1) \mid pq(pq+1) \implies q+1 \mid p(pq+1) \implies k(p+1)+2=q+1 \mid p(p-1) $$This forces $p \mid k(p+1)+2$ as otherwise $k(p+1)+2 \mid p-1<k(p+1)+2$. Therefore $p \mid k+2$. As $k \geq 1$, this means $k \geq p-2$ but then: $$ p(p-1)=(p-2)(p+1)+2 \leq k(p+1)+2 \mid p(p-1) $$so we must in fact have $k=p-2$. This gives $n=p\left(p^2-p-1\right)$ for $p$ and $p^2-p-1$ prime and it's straightforward to check $n$ of this form are peculiar. Thus we have classified all peculiar integers as originally claimed.

In what follows, let $n$ be a peculiar number. Claim 1: Pecuilar numbers are square free

Claim 2: If $q \mid n$, $q \leq \sqrt{n}$ and $q$ is prime then $q^2 \mid n+q$

Assume $n$ is not a prime, If $p$ is the smallest prime dividing $n$ then $n+p \mid p^2n+p^2$ or $n+p \mid p^3-p^2$ and it follows that $n = pq$ or prime, now if $n=pq$ we clearly have $q$ of the form $p^2-p+1$ , and we're done since for each prime there are at most $2$ primes such that $pq$ is peculiar.

The point is to characterize all peculiar $n$. I claim that either $n=p$ with $p$ prime, or $n=p(p^2-p-1)$ where $p$ and $p^2-p-1$ are both prime. Oh and also $n=1$, which I forgot. (-1 maybe) If $n$ is prime or $n=1$, we are done. Otherwise suppose $n$ is not prime and let $d$ be the smallest prime factor. Note $d\le \sqrt{n}$. Then \[\frac{n}{d}\left(\frac{n}{d}+1\right)\mid n(n+1)\implies n+d\mid d^2(n+1)\implies n+d\mid d^3-d^2.\]In particular let $k=\frac{d^3-d^2}{n+d}$. Notice \[k=\frac{d^3-d^2}{n+d}\le \frac{d^3-d^2}{d^2+d}=\frac{d^2-d}{d+1}<d-1\]hence $k\le d-2$. Since $k\mid d^3-d^2=d^2(d-1)$ and $d$ is prime, it follows that $k\mid d-1$. Note that \[n=d\left(d\cdot \frac{d-1}{k}-1\right)\]and so the prime factorization of $d\cdot \frac{d-1}{k}-1$ contains only primes at least $d$. Hence if the value is composite, it must be at least $d^2$. Thus: \[d^2\le d\cdot \frac{d-1}{k}-1<d\cdot \frac{d-1}{k}\implies d<\frac{d-1}{k}\le d-1\]which is a contradiction. Hence $d\cdot \frac{d-1}{k}-1$ is a prime, with $n$ being of the form $pq$. We'll replace variables now: let $n=pq$ and let $q=p\cdot \frac{p-1}{k}-1>p$. Clearly $q>p+1$; otherwise $(p,q)=(2,3)$ and since $3\cdot 4\nmid 6\cdot 7$ we fail. Now notice \[p(p+1)\mid pq(pq+1)\implies p+1\mid q(pq+1)\implies p+1\mid pq+1\implies p+1\mid q-1.\]Thus \[p+1\mid p\cdot \frac{p-1}{k}-2\implies p+1\mid \frac{p-1}{k}+2\implies k=1.\]Looking back, we find $n=p(p^2-p-1)$ where $p$ and $p^2-p-1$ are both prime. Now suppose there is a prime $q$ which divides four different peculiar positive integers. The only prime which could be a multiple of $q$ is $q$ itself. The only numbers of the form $p(p^2-p-1)$ with $p$ and $p^2-p-1$ prime that are multiples of $q$ must have $p=q$ or $p^2-p-1=q$, yielding two other numbers. Thus obtaining four different numbers is impossible (the above counts three). We are done. $\blacksquare$

Consider any peculiar number $n$. Let $p$ be the smallest prime divisor of $n$, $n=pk$. Note that $n=p$ works and $n=p^2$ doesn't work, now $k \geq p+1$. $k(k+1) | pk(pk+1)$, hecne $p(pk+1) \equiv -p(p-1) \equiv 0 (mod k+1)$. Because $k > p$, $k+1=pd$, where $d | p-1$. Now $p(p+1) | pk(pk+1)$, so $k(pk+1) \equiv -k(d+2) \equiv 0 (mod p+1)$. Suppose $(k,p+1)>1$, then let $q$ be such a prime that $q | k | n$ and $q | p+1$. Because $p$ was the smallest, $q \geq p$. $p+1$ can not be divisible by $p$, so $q=p+1$. Then by parity $p=2$, so $k+1=2*1$, so $k=1$, but we consider $k \geq p+1$ - contradiction. So $(k+1,p)=1$, hence $d+2 \vdots p+1$. But $d+2 \leq p-1+2=p+1$, so $d=p-1$, $n=p(p^2-p-1)$. If $p^2-p-1$ is not a prime, then it has a prime divisor $\leq \sqrt{p^2-p-1}<p$ - contradiction. So $p^2-p-1$ is a prime. So we now know that $n=p$ or $n=p(p^2-p-1)$, where $p^2-p-1$ is prime. Obviously, not more than three numbers of such form can be divisible by a fixed prime. Hence we are done.

Suppose that $n > 1$ is a peculiar number. Let $p$ be the smallest prime that divides $n$. If $p \neq 2$, $$p(p+1) | n(n+1) \implies p+1 | n(n+1) \implies p+1 | n+1 \implies n \equiv p \pmod {p(p+1)}.$$ So, $n = p$ or $p(k(p+1) +1)$, for $k \geq 1$, then $$(k(p+1) +1)(k(p+1) +2) | p(k(p+1) +1)(p(k(p+1) +1)+1) \implies kp+k+2 | p(p-1).$$ If $p \not | kp + k +2$, we get that $kp+k+2 | p-1$, that is impossible by size. So, $p | kp + k +2 \implies p | k+2 \implies k = p-2$, again, by size. Therefore, $n = p(p^2-p-1).$ Now, let $r$ be the smallest prime that divides $p^2 - p - 1$, then, $$r \geq p \implies r^2 \geq p^2 \implies r^2 > p^2-p-1 \implies r = p^2-p-1,$$because if a number is not prime, there is a prime factor smaller than its square root. Then, $n = p$ or $p \cdot r$, where $r = p^2 - p - 1$, so there are no $4$ peculiar numbers that the same prime divides. $_\blacksquare$ Now if $p = 2$ we do the same, the only difference is that we can get $n = p(p+1) k = 6k$, but in this case, $$3k(3k+1) | 6k(6k+1) \implies 3k+1 | 2(6k+1) \implies 3k+1 | 2,$$and that is impossible.

Claim: all good numbers are of the form $p$ or $pq$ where $p$ and $q$ are different primes. Proof: Let $p\mid n$ be the smallest prime divisor of $n$. Then choosing $d=\frac{n}{p}$ we have $\frac{n}{p}+1\mid p(n+1)$ but $\frac{n}{p}+1\mid n+p\mid p(n+p)$ so we have $\frac{n}{p}+1\mid p^2-1$ but then $\frac{n}{p}<\frac{n}{p}\le p^2-1<p^2$ so $n<p^3$. Since p was the smallest prime divisor we get $\Omega(n)\le 2$ which means $n$ is of the form $p,pq$ or $p^2$. But $p^2$ fails so the claim is done $\blacksquare$ Now suppose $p\mid \gcd(A, B, C, D)$ then we have $pq,pr,ps$ are good numbers for $p,q,r,s$ all different prime numbers. Then we have $p+1\mid q(q-1)$ and $q+1\mid p(p-1)$ Claim: In the above case we have $q=p^2-p-1$ or $q\mid p+1$ Proof:Suppose not so $p+1\mid q-1$ meaning $q+1\equiv 2 \pmod {p+1}$. Let $k$ such that $p(p-1)=k(q+1)$ taking $\pmod {p+1}$ we get $k\equiv 1 \pmod {\frac{p+1}{2}}$. Since $q+1\ge p+3>p$ we get that $k<p$ so $k$ can only be $1$ or $\frac{p+3}{2}$. But the second case fails (you get $p$ is $3$ or $5$ but then $p(p-1)$ cannot have divisors $q+1,r+1,s+1$) and in the first case you get $q=p^2-p-1$ so the claim is done $\blacksquare$ So we can WLOG assume $sr\mid p+1$. Since $p+1\mid r(r-1)$ we get that $s\mid r-1$ and similary $r\mid s-1$. By size reasons this is impossible so the problem is solved. Remark: Found this quite straightforward for a P3 because if you get the idea of smallest prime divisors(which is standard) then the rest is just cases and bash.

Solved with megarnie. Let $a\in\mathbb{N}$ be peculiar. We first claim that Claim: $a$ is squarefree proof: Toward a contradiction assume there is a prime $p$ such that $p^2\mid a$. Then for convenience write $a = p^2a'$ and then we have \[ pa'(pa'+1)\mid a(a+1)\implies pa'+1\mid p(p^2a' + 1)\implies pa' + 1\mid p(p-1)\implies pa'+1\mid p-1,\]absurd for size reasons. $\square$ This means we can write $a = p_1p_2\cdots p_k$ for distinct primes $p_i$. Now let $P$ be the minimal prime divisor of $a$. Then \[\frac{a}{P}\left(\frac{a}{P}+ 1\right)\mid a(a+1)\implies a+P\mid P^2(a+1)\implies a+P\mid P^2(P-1),\]so $a < P^3-P$. But if $k\ge 3$ then $a = p_1\cdots p_k > P^k > P^3-P$, contradiction. Hence, $k\le 2$. If $k = 0,1$ then we get $a = 1$ or $a$ is prime, both of which are always peculiar. Now assume $k= 2$ and $a = pq$ for primes $q < p$. Then \[p(p+1)\mid pq(pq+1)\implies p+1\mid q(pq+1)\implies p+1\mid q(q-1),\]which means $q\mid p+1$ as otherwise $p+1\mid q-1\implies p < q$, contradiction. Hence $p = nq-1$ for some $n$. We also have \[ q(q+1)\mid pq(pq+1)\implies q+1\mid p(pq+1)\implies q+1\mid pq+1\implies q+1\mid p-1,\]so $q+1\mid nq-2\implies n = m(q+1) - 2$ for some $m$. Hence $p = mq^2 + (m-2)q - 1$. But substituting this back into $p+1\mid q(q-1)$ gives $m = 1$ for size reasons. Hence $p = q^2 - q - 1$. Additionally, it's easy to check that indeed $a = q(q^2 - q - 1)$ is peculiar if $q, q^2-q-1$ are primes. In summary, the peculiar numbers are $1$, primes $q$ and semiprimes $q(q^2-q-1)$. Finally, for a given prime $p$, note that the only peculiar numbers divisible by $p$ are $p$, $p(p^2-p-1)$, and $r(r^2-r-1)$ if there exists a prime $r$ such that $r^2 -r - 1 = p$. Hence there are at most $3$ peculiar numbers divisible by $p$ for a given prime $p$, so $p\nmid (A,B,C,D)$ for distinct peculiar numbers $A,B,C,D$. Thus $(A,B,C,D) = 1$, as needed.

NT for P3 is nice, please algebra for P6

oVlad wrote: They are \[(p,p\cdot q, p\cdot r),\quad p=q^2-q-1,\quad r=p^2-p-1,\]where $p,q,r$ are prime numbers. I wonder if infinitely many triples exist. Certainly yes, under the assumption of Schinzel's Hypothesis (which basically just says that polynomials like $p^2-p-1$ should be prime infinitely often unless they are not for obvious modular reasons). On the other hand, you would likely win a Fields medal for a proof that infinitely many non-prime peculiar numbers exist (i.e. showing that $p^2-p-1$ is prime infinitely often, although even $n^2-n-1$ would surely suffice for the Fields medal), let alone the existence of infinitely many such triplets.

Solved with MathLuis and sixoneeight. Claim. If $n$ is peculiar, then it is a prime, semiprime, or $1$. Proof. Assume $n>1$. Let $p$ be the smallest prime dividing $n$, and let $n=dp$. Then \[d(d+1)\mid n(n+1)=pd(pd+1)\Longrightarrow d+1\mid p(pd+1)\Longrightarrow d+1\mid p(p-1).\]Thus $d+1\le p(p-1)$ (since $p>1$), so $d<p^2$. Since $p$ is the smallest prime dividing $n$, this means $d$ is $1$ or a prime. We may finish by showing that squares of primes never work as $p+1\nmid p(p-1)$. Obviously $1$ and all primes are peculiar. So let $n=pq$. We have \[p(p+1)\mid n(n+1)=pq(pq+1)\Longrightarrow p+1\mid q(pq+1)\Longrightarrow p+1\mid q(q-1).\]Similarly, \[q+1\mid p(p-1).\]Assume WLOG that $p<q$. Then if $p=2$ the second divisibility is impossible, and otherwise $p+2\le q$, so $q\nmid p$, meaning that $p+1\mid q-1$. Also, if $p\nmid q+1$, then $q+1\mid p-1$ which is impossible, so $p\mid q+1$. Therefore, \[p\mid q+1+2p\]and \[p+1\mid q-1+2(p+1)=q+1+2p,\]so since $p$ and $p+1$ are relatively prime, \[p(p+1)\mid q+1+2p.\]Thus $p(p+1)\le q+1+2p$, so $p(p-1)\le q+1$. But since $q+1\mid p(p-1)$, we have $q+1=p(p-1)$. Thus if a prime $r$ divides a peculiar number $n$, we must have $n=r$ or $r$ acts as either $p$ or $q$, meaning that $r$ can divide at most three peculiar numbers. $\blacksquare$

The problem is typically overcomplicated and given in the place of P3 Claim 1: The set of all peculiar numbers is $\{1,p,pq\}$ for all primes $p$ and $q$ such that $p\neq q$. Proof: In the condition of $d(d+1)|n(n+1)$, we put $d\rightarrow \frac{n}{d}$ to get $n+d|d^2(n+1) \implies n+d|d^2(d-1)$. Now let $p$ be the minimum prime dividing $n$. Then $n\ge p$. The above condition implies $n<p^3$. We make two cases: Case 1: There exists prime $q\neq p$ such $q|n$. If $v_q(n) \ge 2$, $n\ge pq^2 > p^3$ which is not the case. Thus $v_q(n)=1$. If $v_p(n) \ge 2$, we get the same contradiction. Thus $v_p(n)=v_q(n)=1$. Again the same argument implies no more prime divisor of $n$ exists. Hence $n=pq$ are peculiar where $p\neq q$ are primes. Case 2: $n$ is a power of $p$. Then $v_p(n) \in \{1,2\}$ and hence $n=p,p^2$. But we note that for $p^2$, we put $d=p$ and note that we must have $$p+1|p(p^2+1) \implies p+1|2$$This contradiction implies $n=p$ for prime $p$ are peculiar. Also $n=1$ is clearly peculiar. This completes the proof of claim. Claim 2: For any prime $p$, there exists atmost two distinct primes $q$ such that $pq$ is peculiar. Proof:So we have $p+1|q(q-1)$ and $q+1|p(p-1)$. Case:$q|p+1$. Then if $q>p$, we must have that $q=p+1$ which is possible only when $p=2,q=3 \implies n=6$ and $6$ is not peculiar(Check!). Thus $q<p$. Now swapping $p$ and $q$ in the above argument we can conclude that $$p \nmid q+1 \implies 1+q | p-1$$Also we have $q|p+1$. Applying CRT, we conclude that $q(q+1)|p+1+2q \implies p\ge q^2-q-1$, and $p+1|q(q-1) \implies p \le q^2-q-1$. Combining, we have $p=q^2-q-1$. Case:$p|q+1$. Then same argument as above Case proves that $q=p^2-p-1$ Case: Contrary to both the above cases. Then $p+1|q-1 \implies p\le q-2$ and $q+1|p-1 \implies q\le p-2$. The statements contradict each other. Case closed. So for any prime $p$ there exist atmost two primes $q$ such that $pq$ are peculiar where $q=p^2-p-1$ or $q^2-q-1=p$ if they are primes, proving the Claim. Finally let there exist four peculiar numbers $A,B,C,D$ such that $\gcd(A,B,C,D)>1$. Then there exists prime $p$ dividing all the four numbers. For any prime $p$, we have proved that $p$ is peculiar and $\le 2$ primes $q$ such that $pq$ is peculiar. Thus we can have atmost $3$ peculiar numbers sharing a prime factor. This completes the proof.

Tintarn wrote: oVlad wrote: They are \[(p,p\cdot q, p\cdot r),\quad p=q^2-q-1,\quad r=p^2-p-1,\]where $p,q,r$ are prime numbers. I wonder if infinitely many triples exist. Certainly yes, under the assumption of Schinzel's Hypothesis. [...] On the other hand, you would likely win a Fields medal for a proof that infinitely many non-prime peculiar numbers exist [...]. Of course, I am aware of the difficulty of this problem. I was merely posing a rhetorical question. sanyalarnab wrote: The problem is typically overcomplicated and given in the place of P3 I totally agree. The solution is just bashy and completely uninteresting. I've got no idea what such a problem is doind on the P3 spot at a prestigious competition such as EGMO. This is what you'd expect to see at the JBMO on the P3 spot...

Let $n = p^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, where $p < \dots < p_k$, taking $d = \frac{n}{p}$ gives: $$\frac{n}{p} \left( \frac{n}{p} + 1 \right) \mid n(n + 1) \implies \frac{n}{p} + 1 \mid p(n + 1) \implies \frac{n}{p} + 1 \mid p(p - 1) $$This means $p_2^{\alpha_2}\cdots p_k^{\alpha_k} \leq p^2 - p - 1$, obviously impossible unless $n = 1,p, p^2, pq$ where $q$ is another prime such that $p < q$. If $n = p^2$, we have: $$p(p + 1) \mid p^2(p^2 + 1) \implies p + 1 \mid p^2 + 1 \implies p + 1 \mid p - 1$$which is impossible. If $n$ is of the form $pq$, we have $p(p + 1) \mid pq(pq + 1) \implies p + 1 \mid q(pq + 1)$. If $q \mid p + 1$, then $q \leq p + 1 \implies q = p + 1$ as $q > p$, which means $p = 2$, $q = 3$, however $6$ isn't a peculiar number. Therefore, $$q \nmid p + 1 \implies p + 1 \mid pq + 1 \implies p + 1 \mid q - 1$$So let $q - 1 = k(p + 1) \implies q = k(p + 1) + 1$. Now, we also have: $$q(q + 1) \mid pq(pq + 1) \implies q + 1 \mid p(pq + 1) \implies q + 1 = k(p + 1) + 2 \mid p(p - 1)$$If $p \nmid q + 1$, we have $k(p + 1) + 2 \mid p - 1$, impossible as it's greater, which means $p \mid kp + k + 2 \implies p \mid k + 2$. Due to size reasons, we have $p = k + 2 \implies q = p^2 - p - 1 \implies n = p(p^2 - p - 1)$. Now, we can have at most three peculiar numbers divisible by $p$. The only possible prime is $p$, and the other two peculiar numbers can be $p(p^2 - p - 1), q(q^2 - q - 1)$, where $q^2 - q - 1 = p$.

Note that $1$ and all primes are peculiar. Claim: If $n>1$ is peculiar and $n$ is not a prime, then it is the product of two distinct primes. Proof. We show that if $n$ is peculiar and $d$ is a divisor of $n$, then $n+d\mid d^3-d$. It follows from $\frac{n}{d}\left(\frac{n}{d}+1\right)\mid n(n+1)$. Taking $d>1$, we have that $n+d\leq d^3-d\Longrightarrow n\leq d^3-2d$. We first show that $n$ is the product of two (not necessarily distinct) primes. Suppose $n$ is the product of 3 or more primes. Let $p$ be the smallest prime divisor of $n$. Then, we have $p^3\leq n\leq p^3-2p$, which is absurd. Hence, $n$ is the product of two primes. Suppose possible that $n=p^2$ was peculiar. Then, we want $p(p+1)\mid p^2(p^2+1)$ which means $p+1\mid p^2+1$ and hence $p+1\mid 2$, impossible. So, $n$ is the product of two distinct primes. $\blacksquare$ Claim: For any prime $p$, there are at most two peculiar composite numbers divisible by $p$. Proof. Suppose $n=pq$ is peculiar with distinct primes $p,q$. Then, $p(p+1)\mid pq(pq+1)$ which means $p+1\mid q(pq+1)$. Suppose $(p,q)\ne(2,3)$. Let $r\ne q$ be a prime such that $r^u\mid p+1$. Then, $r^u\mid pq+1$. Hence, $r^u\mid q-1$. Let $v_q(p+1)=v$. Note that $v\leq v_q(q(pq+1))=1$, so $v=0,1$. We have that every divisor of $p+1$ co-prime with $q$ is also a divisor of $q-1$. So, $\frac{p+1}{q^v}\mid q-1$. Similarly, if $w=v_p(q+1)$ then $\frac{q+1}{p^w}\mid p-1$ WLOG let $p>q$. Then, $p+1\mid q-1$ is impossible, which means $v=1$. So, $p+1\mid q^2-q$. Also, $p\mid q+1$ is impossible as well, which means $w=0$ and $q+1\mid p-1$. So, we have the following conditions \[n=pq, p>q \text{ is peculiar}\Longleftrightarrow p+1\mid q^2-q, q+1\mid p-1\]Since $q\mid p+1$, we can write $p=qk+k+1\equiv-1\pmod{q}$, and hence $k\equiv -2\pmod{q}$. But we also have $p+1\leq q^2-q$ and hence $qk+k\leq q^2-q-2$, so $0<k\leq q+1$. This, along with $k\equiv q-2\pmod{q}$, forces $k=q-2$. Hence, $p=q^2-q-1$ is forced. So, for any prime $p$, there are at most two peculiar composite numbers divisible by $p$. Hence, for any prime $p$, there are at most three peculiar numbers (one prime, and at most two composite) divisible by $p$. So, four numbers divisible by a prime cannot be peculiar. This forces $\gcd(A,B,C,D)=1$ for any four peculiar numbers $A,B,C,D$. The proof is complete. $\blacksquare$

Claim: $n$ is squarefree pf) FTSOC assume $p^2 \mid n$. Let $n = p^2m$ $pm(pm+1) \mid p^2m(p^2m + 1) \Rightarrow pm+1 \mid p^2m + 1$ This is a contradiction Let $p$ and $q$ be two prime factors of $n$. Let $n = pqm$. $pm(pm+1)$, $pq(pq+1)$, and $qm(qm+1)$ are all factors of $pqm(pqm+1)$ If $m \neq 1$ this is a contradiction by size $\therefore n = p$ or $n = pq$ for some $q$ If $n = pq$ (assume $p<q$), $q(q+1) \mid pq(pq+1) \Rightarrow q+1 \mid p(p-1) \Rightarrow q \leq p^2-p-1$, $p \mid q+1$ Also, $p(p+1) \mid pq(pq+1) \Rightarrow p+1 \mid q(pq+1) \Rightarrow p+1 \mid q(q-1) \Rightarrow p+1 \mid q-1$ This means that $q = p^2 - p - 1$ We now have shown that if $n$ is a peculiar number, $n = p$ or $n = p(p^2-p-1)$ where $p^2-p-1$ is prime. The problem statement is a trivial corollary.

Lemma. All peculiar numbers are of the form $n=1$, $n=p$ where $p$ is prime or $n=p(p^2-p-1)$ where $p,p^2-p-1$ are both primes. Proof. Suppose $n$ is composite. Let $p$ be the smallest prime divisor of $n$ and let $n=pq$. Then $q\ge p$ and $$p(p+1)\mid n(n+1)=pq(pq+1)\implies p+1\mid q(pq+1)\implies p+1\mid q(q-1)\qquad(1)$$Similarly we have $$q+1\mid p(p-1)\qquad(2)$$ Claim 1. $q$ is prime. Proof. Assume FSTOC that $q$ is composite. Since $p$ is the smallest prime divisor of $n$, it follows that $q\ge p^2$ so $$p(p-1)<p^2\le q<q+1$$contradiction to $(1)$. Claim 2. We have $p\mid q+1$. Proof. Assume FSTOC that $p\nmid q+1$. Hence $(2)$ implies that $q+1\mid p-1$, contradiction to the fact that $q\ge p$. Claim 3. We have $p+1\mid q-1$. Proof. First, we will prove that $q>p+1$. Assume FSTOC that $q\le p+1$. From claim 2 we know that $q\ne p$. As $q\ge p$, this implies that $q=p+1$ so $(p,q)=(2,3)$. But this contradicts $(2)$. Now $(1)$ implies that $p+1\mid q-1$, as desired. Now let $k=\frac{q+1}{p}\in\mathbb N$. Hence $q=kp-1$. Moreover $k\le p-1$ by $(2)$ so $$p+1\mid q-1=kp-2\implies p+1\mid k+2\implies p+1\le k+2\le p+1.$$Since equality holds, we have $k=p-1$ so $q=kp-1=p(p-1)-1$. $\square$ Now the problem easily follows.

Suppose there is a prime \( r \) for which \( r^2 | n \). Then for \( d = \frac{n}{r} \) we have: \[ \frac{n}{r} \left( \frac{n}{r} + 1 \right) | n(n+1) \Rightarrow \frac{n}{r} + 1 | r(n+1) \Rightarrow \frac{n}{r} + 1 | n+1 \] The latter holds because \( r^2 | n \). Now, observe that: \[ r - 1 < \frac{n+1}{\frac{n}{r}+1} < r \] which is absurd. Now, let \( n = p_1 \cdot \ldots \cdot p_a \) (with \( p_1 < \ldots < p_a \)). For \( d = p_2 \cdot \ldots \cdot p_a = m \), we have: \[ m(m+1) | n(n+1) \Rightarrow m+1 | p_1(m p_1 + 1) \] But for \( a \geq 3 \), we notice that: \[ p_1^2 - 1 < \frac{m p_1^2 + 1}{m+1} < p_1^2 \] which is out of place. So, odd strange numbers have the form \( n = pq \). For \( d = p,q \), we deduce: \[ p+1 | q(q-1) \ \ \ (1) \]\[ q+1 | p(p+1) \ \ \ (2) \] If one is 2, we have no solution, so both will be odd.

This is such a beautiful problem, and I'm so proud of the American EGMO team for sweeping this!!! yall are so blobheart I'll try to present this solution in a more understandable manner Note that the desired conclusion is equivalent to the fact that for any prime $p$, at most $3$ multiples of $p$ are peculiar. Furthermore, if $ab=n$, then $a(a+1)\mid ab(ab+1)$, so $a+1\mid b(ab+1)$, which is equivalent to $$a+1\mid b((-1)b+1)\iff a+1\mid b(b-1).$$Similarly, we have $b+1\mid a(a+1)$ as well. This is a simplification of the "peculiar" condition, which we now know requires $a+1\mid b(b-1)$ and $b+1\mid a(a-1)$ for all $a,b$ such that $ab=n$. This problem has two main ideas. We will present them in order. Main Idea 1 (Reduction to semiprimes): If $p$ is a prime divisor of a peculiar number $n$, then $n<p^3$. In particular, by taking $p$ to be the smallest prime divisor of $n$, $n$ is the product of at most two primes. Let $k=\frac{n}{p}$. Then, by the above work, we have $$k+1\mid p(p-1)\rightarrow k+1\leq p^2-p\rightarrow k\leq p^2-p-1.$$However, this means that $$n=pk\leq p^3-p^2-p,$$as desired. Now, note that primes are always peculiar, but squares of primes are never peculiar, since we cannot have $p+1\mid p(p-1)$ since $p(p-1)\equiv (-1)(-2)\equiv 2\pmod{p+1}$. Thus, it remains to consider semiprimes. This leads us to the second main idea of the problem. Main Idea 2 (Characterization of peculiar semiprimes): If $n=pq$ for primes $p>q$ is peculiar, then we must have $p=q^2-q-1$. We need $p+1\mid q(q-1)$ and $q+1\mid p(p-1)$. Note that since $q<p$, we have $q+1<p$ unless $q=2,p=3$, but that doesn't work anyways. Thus, $q+1$ cannot have a factor of $p$, hence the second divisibility can be strengthened to $q+1\mid p-1$, so $$p\equiv 1\pmod{q+1}.$$However, now consider $p+1\mid q(q-1).$ If $p+1$ did not have a factor of $q$, then we must have $p+1\mid q-1$ but this is clearly not possible if $p>q$. Thus, $$p\equiv -1\pmod{q}.$$By Chinese Remainder Theorem, the above two congruences imply $$p\equiv q^2-q-1\pmod{q(q+1)}.$$However, from $p+1\mid q(q-1)$, we clearly have $p\leq q^2-q-1$, so $p=q^2-q-1$ is the only solution. In particular, this means that the smaller prime factor determines the large one, and vice versa (the other root of the quadratic is negative). Hence, from this characterization, a prime factor can appear at most 3 times in a peculiar number. Once by itself, once as the smaller factor of a semiprime, and once as the larger factor. Remark: Since $5=3^2-3-1$ and $19=5^2-5-1$ are both prime, $5$, $5\cdot 3$, and $5\cdot 19$ are all peculiar, which shows that the problem is "tight".

Nice problem but too easy for P3. Claim 1. $n < m^3$ for any divisor $m$ Proof. $m(m+1) \mid mx(mx+1) \Leftrightarrow m+1 \mid mx^2 + x \Leftrightarrow m+1 \mid mx^2+x - x^2(m+1) = x^2-x$ $\implies n/x + 1 \mid x^2 -x \implies n/x + 1 \le x^2-x \implies n < x^3.$ I might've swapped $m$ and $x$ but it's true for any as both are divisors ofc. It's clear to see this implies that $n$ must be a prime, $p$, or a product of two primes, $pq$ Final Touches If $n=pq$ and $p<q$ From $p(p+1) \mid pq(pq+1) \implies p+1 \mid (pq+1) \Leftrightarrow p+1 \mid q-1$ But from $q(q+1) \mid pq(pq+1) \implies q+1 \mid p(p-1) \implies q \le p^2 - p -1$ $\implies q=p^2-p-1$ Which clearly finishes the problem.

Note that $n = 1$ and $n = p$ are all peculiar. Let $n = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. We first show that $\alpha_i = 1$ for all $i$. Assume otherwise. Let $p$ be such prime. Then, we have \[\frac{n}{p}(\frac{n}{p}+1) \mid n(n+1) \implies \frac{n}{p} + 1 \mid p(n+1) \implies \frac{n}{p}+1 \mid n+1.\] But, this means $$\frac{n}{p} + 1 \mid \frac {n}{p}(p-1) \implies \frac{n}{p} + 1 \mid p-1 \implies p+1 \leq \frac{n}{p} + 1 \leq p - 1,$$ which is a contradiction. Thus, $\alpha_i = 1$ for all $i$. Therefore, we have $n = p_1p_2\dots p_k.$ Now we show that $k \leq 2.$ Let $p_1$ and $p_k$ be the smallest and largest primes respectively. Now, similar to before \[\frac{n}{p_1} (\frac{n}{p_1} + 1) \mid n(n+1) \implies \frac{n}{p_1} + 1 \mid p_1^2 - 1.\] This means \[p_1^{k-1} < p_2p_3 \dots p_k + 1 \leq p_1^2 - 1 < p_1^2.\] Thus, $ k \leq 2$ as needed. If $n = pq$ for $p < q$ primes, then \[p+1 \mid q(pq+1) \implies p+1 \mid q(q-1) \implies p+1 \mid q-1 \implies q = pm+m+1.\] Also, \[q+1 \leq p^2 - p \implies pm + m + 1 \leq p^2 - p -1 \implies (p+1)(m+1) \leq p^2 - 1 \implies m \leq p-2.\] Lastly, \[pm + m + 2 \mid p^2 - p \implies pm+m+2 \mid 2p(m+1).\] If $\gcd(p,m+2) = 1,$ then $pm+m+2 \mid 2(m+1) \implies 3m+2 \leq pm+m+ 2 \leq 2(m+1)$ a contradiction. Hence, $p \mid m+2 \implies p = m+2.$ So $q = pm + m + 1 = p(p-2)+ p-2 + 1 = p^2 - p - 1.$ Which gives us gcd of four peculiar numbers $= 1$, as a prime appears in at most $3$ peculiar numbers.

Another problem abusing the flipping divisors trick. Let $x$ divide $n$, then $\frac nx\left(\frac nx+1\right)\mid n(n+1)$. Multiplying by $\frac xn$ gives $\frac nx+1\mid x^2n+x^2$. So $\frac nx+1\mid x^2-x$. (This is equivalent to the original problem!) Let $p$ be a prime dividing $n$. Then $\frac np+1\mid p^2-p$. If $p\mid\frac np$ then $p$ doesn't divide the LHS, which means it must divide $p-1$, giving a contradiction by size: $\frac np+1\mid p-1$ so $p\leq\frac np\leq p-2$. Now $n$ is squarefree, letting now $p$ be the smallest prime factor of $n$ with $n=pq$, we get $q+1\mid p^2-p$ and $p+1\mid q^2-q$. If $q$ is $1$ then it works. If $q$ is composite then $q>p^2$, impossible. If $q$ is prime, then if $p+1=q$ then $p=2,q=3$ which fails the other condition, otherwise $p+1<q$ so $p+1\mid q-1$. Letting the quotient be $k$, we can get from the other condition that $k(p+1)+2\mid p^2-p$. If $p$ doesn't divide LHS then it will be too small as it must divide $p-1$, else $k\geq p-2$ in which equality holds. So $q=p^2-p-1$. Finally, this shows that the only solutions could be $p$ or $pq$ where $q=p^2-p-1$ is prime (we didn't check they work, but we don't need to), which leaves only three possible peculiar numbers which are multiples of $p$ for any $p$. Thus the gcd condition holds and we are done.

Solution from Twitch Solves ISL: Note that $1$ and any prime are peculiar. We classify all composite peculiar numbers in a series of claims. Claim: A peculiar number $n$ has at most two prime factors. Proof. Let $p$ be the smallest prime dividing $n$, and let $\frac np = c$. Then \[ \frac np \cdot \left( \frac np + 1 \right) \mid n(n+1) \]In particular, \[ c + 1 \mid cp \cdot (cp+1). \]However, \[ cp \cdot (cp+1) \equiv p(p-1) \pmod{c+1}. \]So, since $p(p-1) \neq 0$, we get a bound \[ c \le p^2-p \implies n = cp \le p^3-p^2 < p^3. \]Hence, $n < p^3$ and $p$ is the smallest prime dividing $n$, $n$ can have at most one additional prime factor. $\blacksquare$ Claim: The square of a prime is never peculiar. Proof. If $n = p^2$ we need $p(p+1) \mid p^2(p^2+1)$, or $p+1 \mid p^2+1$, which never holds as $p^2+1 \equiv 2 \pmod{p+1}$. $\blacksquare$ Claim: If $n = pq$ is peculiar for primes $p > q$, then $p = (q+1)(q-2)+1$. Proof. Note that $6$ is not peculiar (as $3 \cdot 4 \nmid 6 \cdot 7$). Assume $n > 6$ and write the equations \begin{align*} p(p+1) \mid pq(pq+1) \iff p+1 \mid q(pq+1) &\iff p+1 \mid q(q-1) \\ q(q+1) \mid pq(pq+1) \iff q+1 \mid p(pq+1) &\iff q+1 \mid p(p-1) \end{align*}In the second equation, since $p > q+1$, we find $\gcd(q+1, p) = 0$ so \[ p \equiv 1 \pmod{q+1}. \]So let $p = 1 + k(q+1)$. On the other hand, we also note that \[ 2 + k(q+1) = p+1 \le q(q-1) \]and hence $k < q-1$; that is, $k \in \{1,2,\dots,q-2\}$. Now, if $p+1 = 2+k(q+1)$ is divisible by $q$, it follows $k \equiv -2 \pmod q$ and therefore $k =q-2$ exactly. If it isn't, then we would have $p+1 \mid q-1$ which is impossible. So the claim is proved. $\blacksquare$ Hence, given a fixed prime $\ell$, there are at most three peculiar numbers divisible by $\ell$: namely $\ell$ itself; $\ell \cdot \left[ (\ell+1)(\ell-2)+1 \right]$, if the bracketed number is indeed prime; $\ell \cdot r$, if there is indeed a prime $r$ such that $\ell = (r+1)(r-2)+1$. Hence given four distinct peculiar numbers, they can have no common prime factor.

We uploaded our solution https://calimath.org/pdf/EGMO2024-3.pdf on youtube https://youtu.be/4YCdtVGNg4w.

To solve the problem, it seems easiest to first classify all peculiar numbers, from which the result should follow easily. We'll break this into a few different steps. Claim: A peculiar number has at most two prime factors (counted with multiplicity). Proof. Let $n$ be a peculiar number. The idea is to look at the largest proper divisor of $n$. Indeed, let $p$ be the smallest prime divisor of $n$, so that we have \[\frac np\left(\frac np + 1\right) \mid n(n + 1),\]which implies that $\frac np + 1 \mid p(n + 1) = pn + p$. We also have \[\frac np + 1 \mid p^2\left(\frac np + 1\right) = pn + p^2,\]and subtracting these yields $\frac np + 1 \mid p^2 - p = p(p - 1)$. But this gives us \[\frac np + 1 \leq p(p - 1) \implies n \leq p^3 - p^2 - p < p^3,\]and since $p$ is the smallest prime divisor of $n$, this implies that $n$ has less than $3$ prime factors. $\square$ Claim: Let $n > 1$ be a peculiar number. Then $n$ is either prime itself or can be expressed as $p(p^2 - p - 1)$, where both $p$ and $p^2 - p - 1$ are primes. Proof. It's clear that all primes are peculiar, so we restrict our attention to the case where $n = pq$ for primes $p, q$. If $p = q$, we obtain \[p(p + 1) \mid p^2(p^2 + 1),\]and since $\gcd(p, p + 1) = 1$ this yields $p + 1 \mid p^2 + 1$, which is impossible since $p > 1$. Thus we can assume $p < q$. Writing out the divisibility relations for the two nontrivial divisors of $n$, we have \[p(p + 1) \mid pq(pq + 1) \implies p + 1 \mid q^2p + q \implies p + 1 \mid q(q - 1)\]and \[q(q + 1) \mid pq(pq + 1) \implies q + 1 \mid p^2q + p \implies q + 1 \mid p(p - 1),\]where the last divisibilities on the first and second lines follow from $p + 1 \mid q^2p + q^2$ and $q + 1 \mid p^2q + p^2$, respectively. Notice that $\gcd(p + 1, q) = 1$, since otherwise $(p, q) = (2, 3)$, which doesn't produce a peculiar number. Applying this to the first divisibility gives $p + 1 \mid q - 1$. On the other hand, we must have $p \mid q + 1$, since otherwise $\gcd(p, q + 1) = 1$ and then $q + 1 \mid p - 1$, which is impossible because $p < q$. Viewing these as congruences in $q$, we can put them together via CRT to obtain \[q \equiv p^2 - p - 1 \pmod{p(p + 1)}.\]But $q + 1 \leq p(p - 1)$ from before, which produces $q \leq p^2 - p - 1$. We have $q > 0$, so the only possible solution is $q = p^2 - p - 1$. Obviously this only works when $p^2 - p - 1$ is prime, so this finishes the proof of our second claim. $\square$ Now fix a prime $p$. There are at most three peculiar numbers divisible by $p$, namely $p$ itself, $p(p^2 - p - 1)$ if $p^2 - p - 1$ is prime, and $q(q^2 - q - 1)$ if it's possible to write $p = q^2 - q - 1$ for some prime $q$. Thus it's impossible that $p \mid \gcd(A, B, C, D)$ for any prime $p$ and four distinct peculiar numbers $A, B, C, D$, so $\gcd(A, B, C, D) = 1$ always holds as desired. $\square$ Remark. (Comments about the problem) I don't know much about the difficulty of an average EGMO problem, but this felt a little easy for a P3 (this is probably just my bias towards NT). After playing around a bit, it seems natural to look at the largest proper divisor of each peculiar number, which yields the bound after a little bit of computation. The rest was a bit more annoying, but there's not really a main idea to prompt the second claim; it's more just writing out the given divisibilities involving $p$ and $q$ and messing around from there.

Take a minimum prime p dividing n Let n/p= x d(d+1)|n(n+1) put d= x x+1|p(xp+1) If gcd(x+1,p) = 1 Then n is prime or 1 If gcd(x+1,p)=p Then x+1 | p²-p This clearly means x = prime Some obvious manuplations yield x= p²-p-1 So clearly gcd of any 4 peculiar numbers is 1