Maths Olympiad Prep

Library / /11 of 37

Number theory Difficulty 6.5 National olympiad Find the answer

Let DnD_n be the set of divisors of nn. Find all natural nn such that it is possible to split DnD_n into two disjoint sets AA and GG, both containing at least three elements each, such that the elements in AA form an arithmetic progression while the elements in GG form a geometric progression.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let Dn D_n be the set of divisors of n n . We need to find all natural numbers n n such that it is possible to split Dn D_n into two disjoint sets A A and G G , both containing at least three elements each, where the elements in A A form an arithmetic progression and the elements in G G form a geometric progression.

We will analyze two main cases:

### Case 1: 1A 1 \in A
Suppose A={1,1+k,1+2k,,1+mk} A = \{1, 1+k, 1+2k, \ldots, 1+mk\} for some integer k k .

#### Subcase 1a: nA n \in A
If nA n \in A , then n=1+mk n = 1 + mk for some m m . However, this implies that n n and 1+(m1)k 1 + (m-1)k are consecutive terms in the arithmetic progression, which leads to a contradiction because their greatest common divisor must be 1, but n n is a multiple of k k .

#### Subcase 1b: nG n \in G
If G={s,sq,sq2,,sqz=n} G = \{s, sq, sq^2, \ldots, sq^z = n\} , then the least common multiple of the elements in A A must divide n n . If s=1 s = 1 , then G G contains 1 1 , which contradicts the disjointness of A A and G G . If s>1 s > 1 , then qzt q^{z-t} for t<z t < z must belong to A A , but this leads to further contradictions regarding the divisibility and properties of the elements in A A and G G .

### Case 2: 1G 1 \in G
Suppose G={1,q,q2,,qd} G = \{1, q, q^2, \ldots, q^d\} .

#### Subcase 2a: nG n \in G
If n=qd n = q^d , then q q must not be prime, as otherwise A A and G G would not be disjoint. Let t t be the smallest divisor of q q greater than 1. Then A A must contain t t and other elements forming an arithmetic progression. However, this leads to contradictions regarding the divisibility and properties of the elements in A A and G G .

#### Subcase 2b: nA n \in A
If nA n \in A , then for some k k , nkA n - k \in A . This implies nk n - k divides n n , leading to nkk n - k \leq k , which implies A2 |A| \leq 2 , contradicting the requirement that A A must contain at least three elements.

After analyzing all possible cases, we conclude that there are no natural numbers n n that satisfy the given conditions.

The answer is: \boxed{\text{No such } n \text{ exists}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.