Let $n, m$ be positive integers. A set $S$ of positive integers is called $(n, m)$-good, if: (1) $m \in S$; (2) for all $a\in S$, all divisors of $a$ are also in $S$; (3) for all distinct $a, b \in S$, $a^n+b^n \in S$. For which $(n, m)$, the only $(n, m)$-good set is $\mathbb{N}$?
Problem
Source: MEMO 2023 I4
Tags: number theory, MEMO2023
cadaeibf
24.08.2023 13:26
The answer is all $(n,m)$ such that $n$ is odd. If $n$ is even, take a prime $p$ such that $p\nmid m$ and $p\equiv 3\pmod 4$ (of which there exist infinitely many). Such a prime cannot be in the minimal $(n,m)$-good sets (i.e. the intersection of all $(n,m)$-good sets), which can be proven by induction. This because $p$ does not divide $m$, and in general if $a\in S$ is not divisible by $p$ there can't be any of its divisors divisible by $p$. Also, since $n$ is even, $a^n+b^n\equiv 0\pmod p\implies a\equiv b\equiv 0\pmod p$, which is impossible by inductive hypothesis. Therefore there can't be any element of $S$ divisible by $p$, and in particular there can't be $p$. If instead $n$ is odd, we immediately note that $1|m$ and so $1\in S$. But now, $a\in S\implies a^n+1^n=(a+1)(a^{n-1}-\cdots +1)\in S\implies a+1\in S$; therefore, by induction we are done, and $S$ must be the entire set of positive integers
VicKmath7
09.09.2023 17:06
If $n$ is odd, we claim that $S$ contains all positive integers. Indeed, since $a+b \mid a^n+b^n$, we know that $a, b \in S \implies a+b \in S$. Hence, $m \in S \implies m+1 \in S \implies m+2 \in S \ldots$, hence all numbers greater than $m$ are in $S$. On the other hand, if we take large $k$, such that $k(m-2)\in S$, then $m-2+1=m-1 \in S$ and applying this for the other numbers yields that all numbers less than $m$ are also in $S$.
If $n$ is even, let $p_1, p_2, \ldots, p_k$ be the prime factors $3\pmod 4$ of $m$; then select $S$ to be the set of positive integers whose prime factors are among $2, p_1, p_2, \ldots, p_k$ and the primes $1 \pmod 4$. Obviously $m \in S$ and if a number is in $S$, then all its divisors are also in $S$. If this doesn't work, then we can obtain a number in $S$ that has a prime factor $q \equiv 3 \pmod 4$ that is not a $p_i$, and this can happen only through $(3)$. If we consider the smallest such number in $S$, then it is of the form $a^n+b^n$ for $a, b \in S$, so $q \mid a, b$ and they are smaller, contradiction. Hence, this works and we are done.