0
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Only $a$ numbers, it cant be more than $a$. $\endgroup$
    – CryoDrakon
    Jan 25 '15 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.