# Is there a subset of natural numbers with a special property

Let set $A$ be an infinite big subset of the set $\mathbb{N}$ (set of natural numbers),it is not equal to $\mathbb{N}$ and it has the following property:

For every $a$ that is not from the set $A$ there exist exact $a$ numbers in $A$, $x_1,x_2,...,x_a$, so that $gcd(a,x_i)=1, i=1,2,...,a$.

• What about $A=\mathbb N\setminus\{1\}$? Jan 25 '15 at 14:40
• @Hagen von Eitzen it cant be like that bcs all numbers from A satisfy the condition, which is obviously greater than 1. Jan 25 '15 at 14:45

I believe that the only subset that works is $\{1,2,3,4,\dots\}$. (There are no $a$'s not in the set, so it satisfies the condition vacuously.)

Reason: First, notice that $1$ has to be in the set.

Now, consider, what if $n$ was missing from the set? Call one of its prime factors $p_n$. Now, if $n$ was missing, that would mean that there are exactly $n$ numbers in the set, $x_1,x_2\dots,x_n$, such that $\gcd(n,x_i)=1$. This means that there are exactly $n$ numbers in $A$ that are not multiples of $p_n$.

Now, what if, in addition, another multiple of $p_n$ was not in the set? Let's call it $m$. So, $m$ is a multiple of $p_n$ and $m\neq n$. By the condition, there are exactly $m$ numbers in the set, $y_1,y_2,\dots,y_m$, such that $\gcd(m,y_i)=1$. This means that exactly $m$ numbers in $A$ are not multiples of $p_n$. But we already said that there are exactly $n$ such numbers! Since $m\neq n$, this is a contradiction.

Conclusion: If $n$ is missing from the set, and it is a multiple of $p_n$, then it is the only multiple of $p_n$ missing from the set. Furthermore, if $n$ is missing from the set, there are exactly $n$ numbers in the set that are not multiples of $p_n$! (Call them $x_1,x_2,\dots,x_n$.)

Consider a number, call it $q$, that is not in $A$ and not a multiple of $p_n$. (We know these exist, because only finitely many not-multiples-of-$p_n$ are in the set.) Now, according to the condition, there are exactly $q$ numbers, $z_1,z_2,\dots,z_q$ such that $\gcd(q,z_i)=1$. However, we know there are infinitely many multiples of $p_n$ in the set, and, since $q$ isn't a multiple of $p_n$, we know that $\gcd(q,k\cdot p_n)=1$ for infinitely many multiples of $p_n$. Contradiction! Thus, our original assumption—that there is an $n$ missing from the set—is false.

Sorry if this was badly written. I hope you can make sense of it.

Do you want only $a$ numbers to exist or at least $a$ numbers? Because if it is latter then how about $A$ be the set of primes.

• Only $a$ numbers, it cant be more than $a$. Jan 25 '15 at 14:33