Since $S\subset N^{\ast},S\neq\emptyset$,there exists positive integer $a\in S$ Then $\frac{a+a}{(a,a)}=2\in S$ If there exists positive integer $b\neq2$,$b\in S$ (i)b is odd,$\frac{b+2}{(b,2)}=b+2\in S$ and $b+2$ is odd,too. so by induction,for all $k\in N,b+2k\in S$,a contradiction with S finite empty. (ii)b is even,suppose b is the smallest even number in S except 2,(b=2m,m>2) so $\frac{b+2}{(b,2)}=m+1<2m$,a contradiction. So $S=\{2\}$.

What if $ i$ and $ j$ are distinct?

This is one of my problems, asked in one of the Romanian 2007 Tests (even without the finiteness requirement), see http://www.mathlinks.ro/viewtopic.php?p=815602#815602 for an incomplete discussion, which basically however identifies all solutions. The only such finite sets are $ S = \{ n, n(n - 1) \}$, for integer $ n > 2$. The infinite sets are $ \mathbb{N}^*$, $ \mathbb{N}^* \setminus \{1\}$, $ \mathbb{N}^* \setminus \{2\}$ and $ \mathbb{N}^* \setminus \{1,2\}$. EDIT. In my problem, $ S$ was required to have at least two elements. Under the statement here, also all sets $ S$ with only one element trivially fulfill (since there exist no distinct $ i$ and $ j$).

In your problem, was it required for I and j to be distinct

Konigsberg wrote: In your problem, was it required for i and j to be distinct Yes (The alternative would be too ez) *I read the problem as determine all S (infinite as well) and was meandering about for an hour We wish to prove that all finite sets fall under the following categories: All sets of the form $S = \boxed{(n, n(n-1))}$ for $n > 2$ and the solutions $\boxed{S = (n)}$. It can be verified that these finite sets satisfy the problem's conditions. Lemma 1 Denote f(i,j) = $\frac{i+j}{(i,j)}$. First, we prove that (i,j) is involutive iff (i,j) falls into the first category. Note that i = i' * gcd(i,j) and j = j' * gcd(i,j). WLOG, let i < j. For gcd(i,j) > 1, f(i,j) = i' + j' < 2j' $\leq$ j. Hence, f(i,j) = i. f(i,j) $\iff$ f(i,j) = i' + j' = i $\iff$ (i,j) = (i, i(i-1)). This follows from a gcd manipulation. For gcd(i,j) = 1, f(i,j) = i+j > j > i. This contradicts our assumption that (i,j) is involutive. Lemma 2 If (i,j) is not involutive, at least one pair among the pairs i, f(i,j), j is not involutive. Suppose that i, f(i,j) is involutive. Hence, i = n, $f(i,j) = n^2 - n$, and $j = n^3 - n^2 - n$ But f(i,j) and j are not involutive (follows from a simple bounding argument from Lemma 1). Contradiction. Now suppose that f(i,j) is not involutive. We will prove that no other finite sets exist via proof by contradiction. We split the problem into the following categories: If gcd(i,j) = 1, then the infinite set S = (i+nj), for any positive n can be generated. This is a contradiction. Now suppose that gcd(i,j) = k > 1. From lemma 2, at least one of the pairs (i,j) , (i, f(i,j)), (f(i,j), j) is not involutive. Hence, taking the function on this pair results in a number distinct from i, j, or f(i,j). Since this number must be less than j as proved in lemma 1, repeating the procedure for the smallest three elements of S in each iteration, one obtains 2 numbers of gcd(i,j) = 1. (Else you could invoke infinite descent since S is bounded above by the largest number of such a triple.) Taking this pair gives the infinite set we found in the previous case, contradiction.

Here is a sketch of my solution I also added some motivation: In these kind of problems where we have a lot of assumptions It is usually useful to analyize the assumption for extreme elements rather than thinking them all in a place.Consider the three small elements and analyze them if the first element is fixed the other two will be determined uniqualy but they form a contradiction.I will explain more asap.

shobber wrote: Determine all finite nonempty sets $S$ of positive integers satisfying \[ {i+j\over (i,j)}\qquad\mbox{is an element of S for all i,j in S}, \]where $(i,j)$ is the greatest common divisor of $i$ and $j$. My Solution Since $S$ is non empty, it must contain atleast 1 element, which is clearly 2, when $i=j$. Now, we prove that this is the only non-empty finite set. Let $x\neq 2$ be the smallest number in the set. Case 1- $x$ is odd Let $x=2m+1$ Then, there also exists $\frac{2+(2m+1)}{gcd(2,2m+1)}=2m+3$ in the set. And, repeating the process with $2m+3$, we find that $2m+5$ also exists in the set, and so on. Thus, this becomes an infinite set with all odd numbers greater than or equal to $x$, contradicting the fact that $S$ is finite. Case 2-$x$ is even Let $x=2m$. Then, there also exists $\frac{2+2m}{gcd(2,2m)}=m+1$ in the set. But, this contradicts our assumption that $x$ is the least element in the set, as $2m\geq m+1\forall m\in\mathbb{N}$. Hence, the answer is $S=\{2\}$

jin wrote: Since $S\subset N^{\ast},S\neq\emptyset$,there exists positive integer $a\in S$ Then $\frac{a+a}{(a,a)}=2\in S$ If there exists positive integer $b\neq2$,$b\in S$ (i)b is odd,$\frac{b+2}{(b,2)}=b+2\in S$ and $b+2$ is odd,too. so by induction,for all $k\in N,b+2k\in S$,a contradiction with S finite empty. (ii)b is even,suppose b is the smallest even number in S except 2,(b=2m,m>2) so $\frac{b+2}{(b,2)}=m+1<2m$,a contradiction. So $S=\{2\}$. what if the problem turns into for all i different from j in S??

We claim that $S=\{2\}$ is the only solution. Suppose otherwise, that there is a $2\ne a\in S$. Let $a$ be the minimal element in the set. Taking $i=j=a$, we have $2\in S$. If $a$ is odd, taking $i=a$ and $j=2$, we have $a+2\in S$, so by induction $a+2n\in S$ for $0\le n\in\mathbb Z$, a contradiction with the finitude of $S$. Note that this means that no odd elements in $S$ exist, so $a\ge2$. If $a$ is even, taking $i=a$ and $j=2$, we have $\frac a2+1\in S$. But: $$\frac a2+1\le a\Leftrightarrow a\ge2,$$which is true, so $a$ is not the minimal element in $S$. Contradiction.

Solution. The answer is $\mathcal{S} = \{2\}$. This clearly works. One can easily show $2 \in \mathcal{S}$ by putting $i=j$. If $|\mathcal{S}|=1$, then we get the claimed answer. So from here on, assume that $|\mathcal{S}|>1$. Let $a \ne 2 \in \mathcal{S}$. We will now do a case work on the parity of $a$. If $a$ is odd, then $\gcd(a,2)=1$. Putting $i=a$ and $j=2$ we get $a+2 \in \mathcal{S}$ and $a+2$ is also odd. Simple induction yields that $a+2n \in \mathcal{S}$ for $n \in \mathbb{N}$ which is a contradiction on finiteness of $|\mathcal{S}|$. One can say pairing odd number and 2 gives infinite number of elements in $\mathcal{S}$. If $a$ is even, then putting $i=a$ and $j=2$ we get $a/2 +1 \in \mathcal{S}$. If $a/2 +1$ is odd, then pairing it with 2 will give a contradiction as stated above. So, $a/2 +1$ must be even. Now pair $a/2+1$ with 2 to get $\frac{a+6}{4} \in \mathcal{S}$. This would give an infinite sequence of decreasing positive even numbers which is impossible. Therefore, this sequence must reach an odd number once and we are done. $\blacksquare$ Remark.To be really clear which infinite sequence we are talking about in the the case where we assumed $a$ to be even. Let the the pair of 2 and $a$ give $a_1$ as a new element. Now $a_2$ is a new element after pairing 2 and $a_1$. One can now define $a_k$ easily. Induct to find $a_k$. This $a_k$ is the exact sequence we are talking about.

Take any $i=j \in S$. Then we know that $ 2 \in S$. If there is an odd number of form $2m-1 \in S$, letting $i=2m-1,j=2$ we know that $2m+1\in S$, then we can repeat this to conclude $S$ is infinite contradiction , hence for any $m\in \mathbb{N}$, we have $2m-1 \not\in S$. Choose the smallest even integer $2m \in S$. Letting $i=2m, j=2$ we have that $m+1 \in S$. If $m+1$ is odd, we have contradiction. If it is even, we can repeat this until we get an odd integer, contradiction. Hence no other integer exists other than $2$. Therefore $S= \{ 2 \}$.

Claim: $2\in S$. Take any element $n$ of $S$. Then, $$\frac{2n}{\gcd(n,n)}=2\in S.$$ Claim 2: $S$ does not have any odd numbers. Note that any finite set of positive integers has a largest element. Suppose for the sake of contradiction that we have a maximial odd element $m$. Then, $$\frac{m+2}{\gcd(m,2)}=m+2\in S,$$which contradicts the maximality of $M$. Claim 3: If $f(n)=\frac{n}{2}+1$, and $a\geq 4$ is a even number, then there exists some integer $k\geq 1$ such that $$f^k(a)$$is odd. Rewrite this as $$f(n)-2=\frac{n-2}{2}.$$This is essentially saying that the distance from $a$ to 2 is halved each time. Therefore, eventually it will go between 2 and 3 and thus not be an integer. However, for it to go into a non-integer, it must have been odd right before the first time it became non-integer, hence proved. Now, note that if $m\geq 4$ is even, then if $m\in S$ then $$\frac{m+2}{\gcd(m,2)}=\frac{m}{2}+1\in S.$$However, we can keep repeating this with the new element, and by Claim 3, $S$ would then contain an odd number, contradiction, so $S$ also does not contain any even numbers $\geq4$. Hence, the answer is $$S=\{2\}$$only, which clearly works.

We claim that $S=\{2\}$ is the only possible set. Suppose that $S=\{a\}$ is a singleton set. Then, $\frac{a+a}{\gcd(a,a)}=2\in S$. So, $a=2$. Now suppose that $|S|>2$. If $a\in S$, then $\frac{a+a}{\gcd(a,a)}=2\in S$. Note that if $a$ is odd, then $\frac{a+2}{\gcd(a,2)}=a+2\in S$. So, $S\supseteq\{a,a+2,a+4,\ldots\}$ which contradicts the fact that $S$ is a finite set. It follows that all elements of this set are even. Let $S=\{2\}\cap\{2a_1,2a_2,\cdots,2a_k\}$ where $a_k>a_{k-1}>\cdots>a_1>1$. However, note that $\frac{2a_1+2}{\gcd(2a_1,2)}=a_1+1\in S$. However, $2<a_1+1<2a_2$, so $a_1+1$ is a new element in $S$, which is a contradiction. So, no other sets satisfy all the given conditions.