13tn European Girls' Mathematical Olympiad (EGMO 2024)

Problem 3. We call a positive integer n peculiar if, for any positive divisor d of n , the integer d ( d + 1) divides n ( n + 1). Prove that for any four different peculiar positive integers A , B , C and D , the following holds:

gcd( A, B, C, D ) = 1 .

Here gcd( A, B, C, D ) is the largest positive integer that divides all of A, B, C and D .

Solution 1

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.

Solution 2

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.

Solution 3

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

Solution 4

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$ .