Maths Olympiad Prep

Library / /8 of 20

Number theory Difficulty 6.4 National olympiad Find the answer

Let n,mn, m be positive integers. A set SS of positive integers is called (n,m)(n, m)-good, if:

(1) mSm \in S;
(2) for all aSa\in S, all divisors of aa are also in SS;
(3) for all distinct a,bSa, b \in S, an+bnSa^n+b^n \in S.

For which (n,m)(n, m), the only (n,m)(n, m)-good set is N\mathbb{N}?

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

Solution

To determine for which (n,m)(n, m), the only (n,m)(n, m)-good set is N\mathbb{N}, we need to examine the conditions given in the problem and their consequences.

A set SS of positive integers is called (n,m)(n, m)-good if:

1. mSm \in S,
2. For all aSa \in S, all divisors of aa are also in SS,
3. For all distinct a,bSa, b \in S, an+bnSa^n + b^n \in S.

We are tasked with finding values of nn such that the only set fulfilling these conditions is N\mathbb{N}, the set of all positive integers.

### Step-by-Step Analysis:

1. Condition 1 ensures that the element mm is included in the set SS.

2. Condition 2 implies a closure property under the division: all divisors of any element in SS must also be in SS.

3. Condition 3 needs more attention, as it extends the set whenever two distinct elements a,ba, b are present. If the set SS is not already N\mathbb{N}, adding element an+bna^n + b^n should eventually force SS to include all positive integers.

- For nn odd:
- Consider any positive integer kk. Choose a=ka = k and b=1b = 1. Then an+bn=kn+1k+1(modn)a^n + b^n = k^n + 1 \equiv k + 1 \pmod{n}. Due to the successive increments with odd powers, all larger numbers are eventually included in SS. Iterating this process leads SS to include all integers, thereby proving S=NS = \mathbb{N}.

- For nn even:
- The element an+bna^n + b^n with nn even can have gaps in the integers it produces from elements of SS. Specifically, a=1a = 1 and b=1b = 1 result in 21n=22 \cdot 1^n = 2, which doesn't necessarily generate all integers, maintaining the possibility of a restricted set.

### Conclusion:

The critical factor is whether nn is odd or even. When nn is odd, the condition (3)(3) progressively generates all earlier and further numbers from any starting integer mm, thus (n,m)(n, m)-good set becomes N\mathbb{N}. Conversely, when nn is even, this cascading effect does not occur universally.

Therefore, the given set SS is N\mathbb{N} if and only if nn is odd.

The only (n,m)-good set is N if and only if n is odd. \boxed{\text{The only } (n, m)\text{-good set is } \mathbb{N} \text{ if and only if } n \text{ is odd.}}

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.