a) Does there exist an infinite subset $S$ of the natural numbers, such that $S\neq \mathbb{N}$, and such that for each natural number $n\not \in S$, exactly $n$ members of $S$ are coprime with $n$? b) Does there exist an infinite subset $S$ of the natural numbers, such that for each natural number $n\in S$, exactly $n$ members of $S$ are coprime with $n$? Proposed by Morteza Saghafian
Problem
Source: Iran 3rd round 2012-Final exam-P8
Tags: number theory proposed, number theory
26.09.2012 22:26
A solution to the first part. Suppose that such an $S$ exists. Then there exists a natural number $n \not\in S$. Since only $n$ elements of $S$ are coprime to $n$ it follows that infinitely many primes are not in $S$. Let $p, q$ be distinct primes not in $S$. Then there are only finitely many natural numbers $i$ such that $p^i$ is in $S$, for otherwise we will violate the given condition for $q \not\in S$. Let $i \ge 2$ be such that $p^i \not\in S$. There are $p^i$ elements in $S$ that are coprime to $p^i$, and these are coprime to $p$ as well. This is a contradiction since $p^i > p$. Therefore such a set does not exist.
26.09.2012 23:25
And a brute-force construction for the second part. (I guess that there a simpler construction.) Let $S_1 = \{ 6 \}$. For $n \ge 2$, we construct inductively sets $S_n = \{ s_1, s_2, \ldots, s_n \}$ with $s_1 < s_2 < \cdots < s_n$ and satisfying the following properties: (a) each $s_i$ is divisible by at least two primes; (b) given $1 \le i < j \le n$ there exists a prime $p$ that divides $s_i$, but not $s_j$; (c) given $1 \le j \le n$, there exists a prime $p$ such that $p$ divides $s_j$ and $p$ does not divide $s_i$ for $i \le j$; (d) if $a_{i,n} = s_i - A(s_i,S_n)$ where $A(t, T)$ denotes the number of elements in $T$ that are coprime to $t$ then $a_{i,n} \le a_{j,n}$ whenever $i \le j$. Suppose that we have constructed such an $S_n$. Let $i$ be the least positive integer such that $a_{i,n} > 0$. For each $1 \le j \le i-1$ let $p_j$ be a prime that divides $s_j$ but not $s_i$. Let $s_{n+1} = q_1q_2 \prod_{j=1}^{i-1} p_j$, where $q_1$ and $q_2$ are large primes that do not divide $s_1 s_2 \cdots s_n$, and such that $s_{n+1} > s_n + n$. It is then easy to check $S = S_n \cup \{ s_{n+1} \}$ satisfies all the above conditions. Note that $a_{i,n+1} = a_{i,n} - 1$. We let $S = \cup_{n \ge 1} S_n$. Note that $a_{i,n}$ is monotonically decreasing and is bounded by zero. And by construction it follows that for any $i \ge 1$, there exits $n \ge 1$ such that $a_{i,n} = 0$. Therefore, each element $n$ of $S$ is coprime to exactly $n$ elements of $S$.
04.10.2012 21:20
semisimplicity wrote: ... (b) given $1 \le i < j \le n$ there exists a prime $p$ that divides $s_i$, but not $s_j$; ...It is then easy to check $S = S_n \cup \{ s_{n+1} \}$ satisfies all the above conditions... Why $S$ satisfies (b) for $j=n+1$? Thanks.
05.10.2012 22:31
Thanks hadikh for pointing out the missing point. My construction is indeed not complete. I don't know if it can be amended, but I will give it another try.
06.10.2012 10:44
I think the solution can be amended by replacing the condtions (b) and (c) by the following: "for $1 \le j \le n$, there are primes $p$ and $q$ that divide $s_j$ such that neither of them divides $s_i$ for $1 \le i < j$, and at most one of them divides $s_k$ for $j < k \le n$." Then in the construction of $s_{n+1}$, for each $1 \le j \le i - 1$ we choose $p_j$ to be one of these two primes.
04.06.2019 21:57
Part (a):We will prove that the answer is NO.Assume for contradiction that such a set exists.The solution is based on the following claim: Claim:Let $a,b$ be two natural numbers so that set of prime divisors of $a,b$ are the same then at least one of $a,b$ should be included in $S$. Proof of the claim:Assume for country that $a,b \not \in S$ then since for any natural number $k$ we have $\gcd (a,k)=1 \leftrightarrow \gcd (b,k)=1$ Then number of elements coprime to $a$ in $S$ should be both $a,b$ which is a contradiction. Returning to the problem let $k \not \in S$ and let $p$ be a prime number so that $\gcd (k,p)=1$.By the claim at most one of the numbers $p,p^2,p^3,\dots$ is not included in $S$ but all of these numbers are coprime with $k$ which is a contradiction. Part (b):Same as semisimplicity.