Proposed by me!

Mindstormer wrote: Proposed by me! WOW! Thanks for this problem

Assume for contradiction not. Fix any $u \in S$. By pigeonhole, take a divisor $d \mid u$ such that $D \coloneqq \{s \in S : \gcd(s,u) = d\}$ is infinite. Because of our contradiction assumption, any two elements of $D$ also have gcd $d$. Since the gcd's are not all the same, there is some $v$ with $d' \coloneqq \gcd(u,v) \neq d$. (If there wasn't, every pair of elements would now have gcd $d$.) Since $|D| = \infty$, we can find a divisor $e \mid v$ such that two elements $w_1, w_2 \in D$ have $\gcd(w_1, v) = \gcd(w_2, v) = e$. If $e \neq d$, take $(x,y,z) = (w_1, v, w_2)$. If $e = d$, take $(x,y,z) = (u,w_1,v)$. [asy][asy] pair u = (2,4); draw(box( (0,0),(1.5,3) ), lightred); pair v = (3,2); label("$D$", (1.5,0), dir(45), red); pair t1 = (0.2,2.4); pair t2 = (0.5,2.1); pair t3 = (0.9,1.7); draw(u--t1, red); draw(u--t2, red); draw(u--t3, red); pair t4 = (0.3,1.2); pair t5 = (0.6,0.4); draw("$e$", v--t4, blue); draw("$e$", v--t5, blue); dot("$w_1$", t4, dir(90), red); dot("$w_2$", t5, dir(-60), red); draw("$d$", t4--t5, dir(225), red); label("$d$", u--t1, dir(90), red); dot("$u$", u, dir(90), blue); dot("$v$", v, dir(0), deepgreen); draw("$d'$", u--v, deepgreen); [/asy][/asy]

Similar to the above one, probably: Select some random element $x=x_0$ from $S$. There exist infinitely many $x_i$ such that $gcd(x,x_i)=d$ for all $i=1,2,...$ (infinite version of PHP). If there is a pair $(x_i, x_j)$ with gcd different from $d$, we are done taking $(x, x_i, x_j)$. Hence we now assume $gcd(x_i,x_j)=d$ for all $i,j$, including $x_0$. If the set of $x_i$ cover $S$, we have a contradiction, since the gcd's will be all the same. So now we can consider some element $a$ outside the $x_i$ (hence $gcd(a,x_i)$ can't be always $d$ for all $i$). Case 1. $gcd(a,x_i)=d$ isn't achieved for any $i$. Hence there exist $x_i, x_j$ such that $gcd(a,x_i)=gcd(a,x_j)=d'$ is distinct from $d=gcd(x_i,x_j)$ (this is due to the infinite pigeonhole; in fact those $(i,j)$ which give $d'$ are infinitely many) Case 2. $gcd(a,x_i)=d$ is achieved for some $i$, but not for all $i$. Then take some $x_j$, such that $gcd(a,x_j)$ is not $d$, but $gcd(a,x_i)=gcd(x_i,x_j)=d$, so we are done.

Assume that no such triple of $x,y,z \in S$ exists. We begin with some Claims: Claim 1: There exists an element $a$ of $S$ such that $A=\{d : \gcd(a,b)=d \, {\rm for \, some} \, b \neq a \, {\rm with} \, b \in S \}$ has more than one element. Proof: Assume otherwise, then for all distinct $a,b,c,d \in S$, we would have $\gcd(a,b)=\gcd(a,c)=\gcd(c,d)$, which is a contradiction because of the problem statement $\blacksquare$ Claim 2: For that $a$, there exists a $d_1 \in A$ such that $B=\{ b: \gcd(a,b)=d_1 \, {\rm{and}} \, b \in S \}$ is infinite. Proof: This is clear since $A$ is infinite and $\gcd(a,b)$ can take finitely many values as $b$ runs through the elements of $S$ $\blacksquare$ From Claim 1, we may take a $c \in S$ such that $\gcd(a,c) \neq d_1$. Moreover, since $c$ has finitely many divisors and $B$ is infinite, we may take $x,y \in B$ such that $\gcd(x,c)=\gcd(y,c)$. Let $d_2$ be their common value. Note that since $\gcd(x,c)=\gcd(y,c)=d_2$, from our initial assumption we must have $\gcd(x,y)=d_2$ too. Similarly, since $\gcd(a,x)=\gcd(a,y)=d_1$, we must have $\gcd(x,y)=d_1$ too, thus $d_1=d_2$. To finish, note that $\gcd(a,x)=d_1=d_2=\gcd(x,c)$, and so $\gcd(a,c)=d_1$, which contradicts our initial choice of $c$. Hence we reached a contradiction, which means that such a triple must exist.

Assume the contrary that for any three pairwise distinct $x,y,z \in T$, if $\gcd(x,y)=\gcd(y,z)$ then $\gcd(x,y)=\gcd(y,z)=\gcd(z,x)$. Let $m\in T$. We know that $\gcd(m,n) \mid m$ for any $n\in T$. Since $T$ is an infinite set but the set of divisors of $m$ is finite, there exist $k \in \mathbb{N}$ such that $$U=\{n\in T \mid \gcd(m,n)=k \} $$is infinite. Thus, there exist infinitely many $n\in T$ such that there exist $l \in T$ that $gcd(n,l)=k$ for some positive integer k. So, the set $U_{k} = \{n\in T \mid \gcd(n,l)=k \quad \text{for some} \ l\in T \}$ is infinite. If $U_k=T$, then $gcd(t_1,t_2)=k \quad \forall t_1,t_2 \in T$ which is a contradiction. Thus, there exist $t\in T-U_k$. Since $U_k$ is an infinite set but the set of divisors of $t$ is finite, there exists $u_1,u_2 \in U_k$ such that $\gcd(t,s_1)=\gcd(t,s_2)$ which implies $\gcd(t,s_1)=\gcd(t,s_2)=\gcd(s_1,s_2)=k$. Thus, $t \in U_k$, a contradiction. Therefore, there exist three pairwise distinct $x,y,z \in T$ such that $\gcd(x,y)=\gcd(y,z)\neq \gcd(z,x)$. Solved by G. who still wanted to remain anonymous.

Mindstormer wrote: Proposed by me! How did you come up with this nice problem?

Here is a video where I solve this one! I loved this problem.. congrats to the proposer https://youtu.be/PtWpKimXrfk

Assume for the sake of contradiction that there does not exist three distinct $x,y,z$ with $\gcd(x,y)=\gcd(y,z)\neq \gcd(z,x).$ Note that for every $x\in S$ there exists an infinite subset $S_x$ of $S$ such that $\gcd(y,x)=d$ for all $y\in S_X$, for some constant $d$ However, if $\gcd(y_1,y_2)\neq d$ for some $y_1,y_2\in S_x$ then we have a contradiction, so we have all $y_1,y_2$ in $S_x\cup x$ have $\gcd(y_1,y_2)=d.$ Note that this $S_x\cup x$ set is infinite. If there is another number $z$ not in $S_x\cup x$ such that $\gcd(z,y)=d$ for some $y\in S_x\cup x.$ Then, we must have $\gcd(z,y)=d$ for all such $y$ so we just add it in. Obviously we must eventually encounter a $z$ such that $\gcd(z,y)\neq d$ for all $y\in S_x\cup x$ otherwise all the values in $S$ would have the same gcd. Since there are infinite values in $S_x\cup x$ we see that then there exists two $\gcd(z,y_1)=\gcd(z,y_2)\neq d$ and so we're done.

We prove the contrapositive statement. Consider an element $x\in S$. Then (by infinite PHP) there must exist an infinite $T\subset S$ such that $k= \gcd(x, y)=\gcd(x, z)$ for all $y, z\in T$. Since there are no $x, y, z$ such that $\gcd(x,y)=\gcd(x,z) \neq \gcd(y, z)$, we must also have $\gcd(y, z)=k$ for every $ y, z \in T$. This solves the problem, as we may take any distinct $a, b, c, d\in T$ and we know that $\gcd(a, b)=k=\gcd(c, d)$

Suppose otherwise. Then either we never have $\gcd{(x,y)}=\gcd{(y,z)}$ (impossible, since $S$ is infinite), or we have that $\gcd{(x,y)}=\gcd{(y,z)}$ always implies $\gcd{(x,y)}=\gcd{(y,z)}=\gcd{(x,z)}$. Consider a complete graph where an edge connecting $a$ and $b$ and an edge connecting $c$ and $d$ ($a$ and $b$ aren't necessarily distinct from $c$ and $d$) have the same color if and only if $\gcd{(a,b)}=\gcd{(c,d)}$. Then every group of three edges that connect three nodes either all have the same color or all have different colors. Consider some number $n\in S$. I claim that there is some infinite set $S'$ containing $n$ such that every edge connecting two numbers in $S'$ have the same color, and such that the $\gcd{}$ of any number not in $S'$ with any number in $S'$ is not equal to the $\gcd{}$ of any two elements within $S'$. To show this, note that the $\gcd{}$ of any number with $n$ can take on a finite number of values. So, there is an infinite set such that every edge connecting a number in that set to $n$ has the same color. This immediately implies the existence of $S'$. Now suppose FTSOC there exists a number $k$ not in $S'$. Then the $\gcd{}$ of every pair of numbers in $S$ with $k$ can't be equal, which is a contradiction. Finally, this implies that the $\gcd{}$ of any pair of numbers in $S$ is the same, a contradiction. We are done. $\blacksquare$

Assume without loss of generality that there is no integer $n$ greater than $1$ dividing every element of $S$, since we can define $T = \left \{\frac{s}{n} \mid s\in S\right \}$, which has the same property, so if we find a working pair $(x, y, z)\in T^3$, then we can just scale $x, y, z$ by $n$ to get a working pair $(x', y', z') = (nx, ny, nz)$ in $S$. Then, let $a, b, c, d$ be four pairwise distinct integers such that $\gcd(a, b)\neq \gcd(c, d).$ WLOG, say $\gcd(a, b) > \gcd(c, d)$. Then, $\gcd(a, b) > 1$. If there exists a $c$ such that $\gcd(a, c) = \gcd(b, c) = 1$, then we're done. Else, every $c\in S\setminus \{a, b\}$ is divisible by at least one prime dividing $ab$, so by PHP there exists a prime $p$ dividing infinitely many $c\in S$. Let $S_p$ denote the elements in $S$ which are divisible by $p$. By our assumption, there exists an element $A$ with $p\nmid A$. Then, if we can find $x = pX_p$, $y = pY_p$ such that $\gcd(X_p, A) = \gcd(Y_p, A) = 1$, then we are done since $p \mid \gcd(X, Y)$, implying $\gcd(X, Y) > 1$. Else, this means that every element in $S_p$ is divisible by at least one prime dividing $A$, so by PHP there exists a infinite set $S_{pq}$ which is a subset of $S_p$ such that all elements in $S_{pq}$ are divisible by $pq$, where $q$ is a prime dividing $A$. If we could find $x = pqA_{pq}$, $y = pqB_{pq}$ both in $S_{pq}$ satisfying $\gcd(A_{pq}, A) = \gcd(B_{pq}, A) = 1$, then we are done since $\gcd(x, A) = \gcd(y, A) = q$ and $p\nmid \gcd(x, y).$ Else, by the same PHP argument, we can find an infinite set $S_{pqr}$ which is a subset of $S_{pq}$ such that all elements of $S_{pqr}$ are divisible by $pqr$, where $r$ is a prime (not necessarily distinct from $q$) dividing $A$. We can repeat this same argument over and over again to obtain an infinite set $S_{pA}$ in $S$ such that all elements in it are divisible by $pA$, or that we can find such a triple in the intermediate process of applying the argument over and over again. If the latter happens, then we are done. Else, there exists such an $S_{pA}$, so letting $x = pAz_1$ and $y = pAz_2$ in $S_{pA}$, we have $pA\mid \gcd(x, y)$ and $\gcd(x, A) = \gcd(y, A) = A$, implying $\gcd(x, A) = \gcd(y, A)\neq \gcd(x, y)$, as desired.

Also Iran 3rd combinatorics exam p1 .

a nice c1

Assume the opposite; by PHP for any fixed $p\in S$ and it's divisor $d_1$ we may choose infinite set $S'$ of numbers $s\in S$ satisfying $\gcd (p,s)=d_1$. Note that by the assumption $\forall s_1,s_2 \in S'$ $\gcd(s_1,s_2)=d_1,$ therefore $\exists q\in S\backslash S'$ due to the fact $\gcd(a,b) \neq \gcd(c,d).$ Now we may take such $d_2|q$ that $\exists r_1,r_2\in S'$ $\gcd (q,r_1)=d_2=\gcd (q,r_2).$ If $d_1\neq d_2$ triple $(x,y,z)=(r_1,q,r_2)$ satisfies, otherwise we may take $(x,y,z)=(p,r_1,q).$

Lemma 1. There exists some positive integer in $S$, say $m$, that has at least two different $\gcd$'s with the rest of set $S$. Proof. Suppose not. Then for any four pairwise distinct $a,b,c,d\in S$, $\gcd(a,b)=\gcd(a,d)=\gcd(c,d)$, contradiction. Assume FTSOC that our wanted condition cannot be satisfied. Consider $m$ from Lemma 1. Since it is finite, it must have finitely many distinct $\gcd$'s with other elements in $S$. So, for each element $r\ne m$ in $S$, put it in set $S_a$ if $\gcd(m,r)=a$. At least one of these $S_k$ sets are infinite, let's name it $A$. There is at least one other set, let's name it $B$. Consider any two elements $s,t$ in $A$. We have $a=\gcd(m,s)=\gcd(m,t)$, so we must also have $\gcd(s,t)=a$ by our assumption FTSOC. Now, consider any element $n$ in $B$. It only has finitely many distinct $\gcd$'s it can have with elements in $A$, so there must be some $\gcd$ that occurs infinitely many times. So let $b=\gcd(c,n)=\gcd(d,n)$ for $c,d\in A$. Now, $a=b$ to not violate our assumption FTSOC. Finally, we can see that $a=\gcd(m,c)=\gcd(c,n)\ne\gcd(m,n)$, contradiction. QED.

We start by proving Claim: For all $a \in S$ there are infinite $b, c \in S$ (with $a\neq b\neq c\neq a$) with $\gcd(a,b)=\gcd(a,c)$. Proof: Notice that $\gcd(a,x)$ takes on finitely many values over all $x \in \mathbb{Z}^+$. Since $|S| = \infty$, the above claim must be true. Let $S_a$ be the set of all values $b_i \in S$ with $\gcd(a,b_i)=g_a$ where $g_a$ is an arbitrary value such that $|S_a|=\infty$ (this must exist by the above claim). If there are $b_i$, $b_j$ with $\gcd(b_i,b_j)\neq g_a$ we are done by taking the triple $a,b_i,b_j$. Otherwise, we must have $\gcd(b_i,b_j)=g_a$ for all $b_i$, $b_j$. Obviously $S_a \neq S$, so let $p \in S\setminus S_a$. Case 1: $\gcd(p,b_i)\neq g_a$ for all $b_i$. Then we must have two $b_i$, $b_j$ such that $\gcd(p,b_i)=\gcd(p,b_j)$ since $\gcd(p,x)$ takes on finitely many values and $|S_a|=\infty$. Taking $p,b_i,b_j$ finishes. Case 2: $\gcd(p,b_i)=g_a$ for some $b_i$. If $\gcd(p,b_i)=g_a$ for all $b_i$ and all $p$, then the condition that $\gcd(a,b)\neq\gcd(c,d)$ for some distinct $a$, $b$, $c$, $d$ is contradicted, thus for some $p$, there exist $b_j$ such that $\gcd(p, b_j) \neq g_a$ and taking the triple $p,b_i,b_j$ finishes.

Wow this is the first problem that I have solved while not sitting on my table, infact i started thinking about this problem when lying down on the bed at like 5:40 a.m. Choose a positive integer $a \neq 1$. Draw an infinite 'graph' of some sorts, basically draw an edge between each pair of integers and colour them a different color the edges a different color for each possible gcd (like colour integers joining gcd $d$ with \ \ \ like $c_d$eez or something.) Now, vertex $a$ can have at most $\tau(a)$ possible gcd's, importantly it can have only a finitely many coloured edges joining to it. So, There is an infinite set of integers $M$ such that gcd(a,m) is fixed number d, and let c_d be blue, so basically, join $a$ with each vertex in $M$ with a blue edge. Now, each vertex in $M$ must have been joined to each other with a blue edge only (otherwise we are done clearly) Now, as for all $a \neq 1, \tau(a) > 1$, there exists at least one other integer $b$ connected to $a$ by say a yellow edge (if not then $M$ is equal to $S$ and we are done clearly (because then everything has gcd $d$) So there exists another integer $b$ such that $ab$ is not blue, say $ab$ is yellow. Again, at max $\tau(b)$ possible coloured edges originate from $b$, so there are two integers in $M$, $x$ and $y$ such that $bx$ and $by$ are the same coloured edges. Now if $bx$ and $by$ are blue, $a,b,x$ works ($ax, bx$ blue and $ab$ yellow), and if $bx,by$ are not blue, say they are red, $b,x,y$ works, ($xy$ blue and $bx,by$ red) This is so fun

Cute problem. The key claim is the following: Claim. For any element $a \in S$, there exists a positive integer $d$ such that there are infinitely many positive integers $k \in S$ with $\gcd(a, k) = d$. Proof. Notice that $d \mid a$, so Pigeonhole works. $\blacksquare$ Now, pick any $n \in S$, and draw an edge between two numbers in $S$ if they have GCD equal to $d$ for that $n$. Assume for the sake of contradiction that the statement is false; then, for any $a, b \in S$ such that $\gcd(a, n) = \gcd(b, n) = d$, we must also have $\gcd(a, b) = d$. Thus, $S$ must be a complete graph. Next, pick any $m \not \in S$. Because $S$ is infinite, there exists another positive integer $d_1$ such that $\gcd(m, k) = d_1$ for infinitely many $k \in S$. But picking two of these values $k_1$ and $k_2$ yields $\gcd(m, k_1) = \gcd(m, k_2) = \gcd(k_1, k_2) = d$, so $d_1 = d$. This means that $$\gcd(m, n) = \gcd(m, k_1) = \gcd(k_1, n) = d,$$so $m \in S$ too. As a result, $\gcd(a, b) = d$ for any $a, b \in S$, but this contradicts the given condition.

Assume otherwise. Take any $a,b,c,d$ and I'll show $\gcd(a,b)=\gcd(c,d)$. By pigeonhole there's $k \mid a$ such that there are infinitely many $x \in S$ whose gcd with $a$ is $k$; let the set of all these $x$ be $X$. Then everything within $X$ must have gcd $k$ with each other. Now by pigeonhole there's $m \mid b$ such that there are infinitely many $y \in X$ whose gcd with $b$ is $m$; let the set of all these be $Y \subseteq X$. Then everything within $y$ must have gcd $m$ with each other, but since all gcd's within $X$ are $k$, we must have $m=k$. This implies $\gcd(a,b)=k$. Similarly we get $\gcd(a,c)=\gcd(a,d)=k$, which implies $\gcd(c,d)=k$.

Assume toward a contradiction this is false. Let $a\in S$. Then, since there are finitely many divisors of $a$, there exists $x$ and an infinite set $X\subseteq S$ such that for all $b\in X$, $gcd(a, b)=x$. By our assumption, if $m, n\in X$, then $gcd(m, n)=x$. Let $k\not\in X$. Then, assume towards a contradiction that there is no $q\in X$ with $gcd(k, q)=x$. Then, clearly all values of $gcd(k, q)$ must be different for different $q\in X$. However, $k$ only has finitely many divisors, a contradiction. So, there exists $q\in X$ with $gcd(k, q)=x$. Let $p\in X$. Then, since $gcd(k, q)=gcd(p, q)=x$, $gcd(k, p)=x$. So, we can add $k$ to $X$. Sine the number of positive integers is countable, we can repeat this and add every positive integer of $S$ to $X$. However, this contradicts the assumption that there exists $a, b, c, d\in S$ with $gcd(a, b)\neq gcd(c, d)$.

Another masterpiece by Fedir Yudin, orz. Consider some fixed element $a\in S$, note that $gcd(a,b)$ can only take finitely many values as $b$ runs through infinitely many elements of $S$, thus there must exist $d$ such that $gcd(a,b)=d$ for infinitely many distinct $b\in S$, we let $T$ be the infinite set of these values of $b$. Clearly, $T\neq S$, as otherwise, the $gcd$ of any two numbers is some constant, which contradicts the existence of the $4$-tuple in the problem statement. Thus, there must exist some $c\in S$ with $c \notin T$, i.e. with $gcd(a,c)\neq d$. We now start looking at the values of $gcd(b_i,c)$ as $b_i$ runs through $T$. If there exists $b_0\in T$ with $gcd(b_0,c)=d$, then $(a,b_0,c)$ is our desired triple with $$d=gcd(a,b_0)=gcd(b_0,c)\neq gcd(a,c).$$ If $gcd(b_i,c)\neq d$ for all $b_i\in T$, then since $gcd(b_i,c)$ takes finitely many values as $b$ runs through infinitely many elements of $S$, there must exist some $b_1, b_2\in T$ with $gcd(b_1,c)=gcd(b_2,c)$. But then $(b_1,c,b_2)$ is our desired triple with $$gcd(b_1,c)=gcd(c,b_2)\neq gcd(b_2,b_1)=d.$$

Why does this look sus? A solution from some time back so I'm not very confident on its accuracy. Consider an element $s \in S$. There are only finitely many possible values for $\gcd(s,t)$ for another $t \in S$ (the divisors of $s$). Thus, there must be some value $k$ such that $\gcd(s,t)=k$ for infinitely many $t \in S$. Consider the set $S$ as a graph with its elements as nodes and the $\gcd$ between two integers as the edge connecting them. Color the edges according to the value (same $\gcd$ means the edges have the same color). We represent the edge between to vertices $a_1,a_2$ by $a_1-a_2$ Consider an element $a \in S$, notice that there must be an infinite set $B$ such that for all $b_i \in B$, $\gcd(a,b_i)$ is the same. Thus, $a-b_1,a-b_2,\dots$ are all of the same color. Let this color be $C_1$. Notice that then, $b_i-b_j$ for all $b_i,b_j \in B$ must also be of $C_1$ (or else we already have a working triplet) Then, by the condition that there exists pairwise distinct $a,b,c,d$ such that $\gcd(a,b)\neq \gcd(c,d)$, so there must be some $c \in S \neq a \not \in B$ such that $a-c$ is not $C_1$. Let this color be $C_2$. Then, notice that $c-b_1$ must be $C_3$ (or else we have a working triplet) since $a-c$ is $C_2$ and $a-b_1$ is $C_1$, similarly, the colors of $c-b_i$ must be distinct for all $i$. Thus, we use all colors $C_3,C_4,\dots$. Now, there must also be infinitely many elements $d_i \in D$ in $S$ such that $\gcd(c,d_i)$ is the same. Then, notice that if atleast two of $d_i \in B$ (say $d_1$ and $d_2$), then we have a working triplet by taking $(c,d_1,d_2)$. If one of them is in $B$, then we have a working configuration by taking $(c,d_1,d_2)$ as well, since if $d_2 \not \in B$ then $d_2-b_i$ is never $C_1$. If none of them is in $B$, then $c-d_i = C_k$ for some $k$ (for all $d_i$)but since all $k$ were used up before, we clearly have a working configuration by taking $(c,d_i,b_j)$ where $c-b_j$ is $C_k$. Thus, all always in an infinite set $S$ of positive integers, such that there exists pairwise distinct integers $a,b,c,d \in S$ satisfying $\gcd(a,b) \neq \gcd(c,d)$, there must exist pairwise distinct $x,y,z \in S$ satisfying $\gcd(x,y)=\gcd(y,z)\neq gcd(z,x)$

why is combo so hard to write up :sob: if anyone could check if im missing anything that would be greatly appreaciated Assume otherwise; i.e. there do not exist integers $x,y,z$ that satisfy the condition. Take some number $p \in S;$ then by infinite pidgeonhole principle there exists some infinite set $K \subset S$ such that for all $k \in K$, $\gcd(p, k) = d$ for some fixed $d \mid p$ ($p \in K$). By the assumption, any $k_1, k_2 \in K$ must have $\gcd(k_1, k_2) = d$. WLOG assume $K$ is maximal (i.e. all $q \notin K$ do not have $\gcd(p,q) = d$); otherwise simply add any number that satisfies the condition for $K$ into $K$, and it will share a gcd with all other members of $K$ by the assumption. Clearly, by the condition, $K \neq S$; however, for any $a \notin K$, one can clearly select two integers $k_1, k_2 \in K$ such that $\gcd(a, k_1) = \gcd(a, k_2) \neq \gcd(k_1, k_2) = d$, contradiction.

The set of possible values of $gcd(n, x)$ with $n, x \in S$ as $x$ ranges is finite, it has to be a divisor of $n$. Since $x$ can take on infinitely many values, there is some value $d|n$ such that $gcd(n, n_i) = d$ for infinitely many $n_i$. FTSoC, asume that its impossible to have $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$. Then for all triples $x, y, z$, $$\gcd(x,y) = \gcd(y, z) \implies \gcd(x,y) = \gcd(y, z) = \gcd(x, z).$$ This means that $\gcd(n_i, n_j) = d$ for all $i, j$. Now consider any number $m$ outside the possible $n_i$'s, so $\gcd(n_i, m) \neq d$. Since the set of all $n_i$'s is an infinite set, and the values $\gcd(m, n_i)$ can only take finitely many values(the divisors of $m$, then there are infinitely many $n_j$ such that $gcd(m, n_i) = \gcd(m, n_j) \neq d$. However, $\gcd(n_i, d) = \gcd(n_j, d) = \gcd(n_i, n_j) = d$, a contradiction to the existence of $m$. Thus, all numbers in the set have a pairwise gcd of $d$, a contradiction, as we can't have $\gcd(a, b) \neq \gcd(c, d)$. Thus, there must exist $x, y, z \in$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.

Assume not. Since S is infinite, there exists a fixed element a with infinite set A with b|a consisting of elements s in S such that gcd(s,a)=b; because of the assumption, the pairwise gcd of any elements in A is also b (otherwise choose two elements in A and a and we're done). Since not all gcds are b, there is some c and d s.t. c=gcd(a,d) which is not b. Now, find e,f,g for some fixed g|d s.t. gcd(e,d)=gcd(f,d)=g and e,f are elements in A. If g is not equal to b, take x,y,z=e,d,f, while if g=b, take x,y,z=a,e,d, which again satisfies the condition. (written up lazily cuz i have to go soon oops)

Let $y_1, y_2,\ldots, y_n$ be the $n$ positive divisors of $y$, and let \[Y_i = \{x: \gcd(x, y) = y_i \text{ and } x\in S\}\]for all $1\leq i\leq n$. We set $y=a$, so $\gcd(a,b)=y_k$ for some $1\leq k\leq n$, meaning $b\in Y_k$. Now, since $\gcd(c,d)\neq \gcd(a,b)=y_k$, if $c,d\in Y_k$ then we have \[y_k=\gcd(a,c)=\gcd(a,d)\neq \gcd(c,d)\]Otherwise, if at least one of $c$ or $d$ is not in $Y_k$, we know that there are at least two nonempty $Y_i$, and at least one of them must contain an infinite number of elements, since $S$ is infinite. If two elements $x,z\in Y_i$ had $\gcd(x,z)\neq y_i$ then we would be done, because \[y_i=\gcd(x,y)=\gcd(y,z)\neq\gcd(x,z)\]So, we let the elements of $Y_i$ be $y_ip_1, y_ip_2, y_ip_3,\ldots$ so that $p_1, p_2, p_3,\ldots$ is a sequence of numbers such that $\gcd(p_i, p_j)=1$ for all $i\neq j$. Now, WLOG $Y_j$ is an infinite set for some $1\leq j\leq n$ with $j\neq k$. Then, select two numbers in $Y_j$, say $y_jp_{\alpha}$ and $y_jp_{\beta}$, such that $\gcd(p_{\alpha}, b)=\gcd(p_{\beta}, b)=1$. Then, if $y_j\nmid b$, we get \[\gcd(b,y_j)=\gcd(b,y_jp_{\alpha})=\gcd(b,y_jp_{\beta})\neq \gcd(y_jp_{\alpha}, y_jp_{\beta})=y_j\]Now, if $y_j\mid b$, then we select some $y_jp_{\alpha}\in Y_j$ with $\gcd(p_{\alpha}, y) = \gcd(p_{\alpha}, b)=1$, and we can make this selection since there are infinitely many $p_i$ but finitely many pairwise relatively prime numbers such that $\gcd(p_i, y)$ or $\gcd(p_i, b)$ isn't $1$. We then get \[y_j=\gcd(b,y_jp_{\alpha})=\gcd(y,y_jp_{\alpha})\neq \gcd(b,y)=y_k\]Since we've shown what we desire for every case, we're done.

Let's pick an arbitrary number $ a \in S$. Since $a$ has finite number of divisors and there are infinite numbers in $S$, pigeonhole principle tells us that there will be infinite amount numbers b such that gcd$(a,b) = x$. Let's call this new set $B$. If we can show that gcd$(b_k, b_n)$ $\neq$ gcd$(a,b_k)$ we will be over. Let's say gcd$(b_k, b_n) = x$, then there are two possibilities: $\mid$ - gcd$(a,b_n) = x$ \Longrightarrow We can pick a number c not in the set $B$ and such $b_k \in B$ that gcd$(c,b_k) \neq x$ (Since the set $B$ is infinite). $\mid$ $\mid$ - gcd$(a,b_n) \neq x$ \Longrightarrow As we mentioned we would get a desired solution since gcd$(b_k, b_n)$ $\neq$ gcd$(a,b_n)$

We will prove the contrapositive. Suppose that any two $\gcd$s in $S$ are distinct. Then consider some $a \in S$, and note that for all $s \neq a$ in $S$, the numbers $\gcd(a, s)$ are all distinct. Thus there are infinitely many distinct $\gcd(a, s)$. However, this is at most $\tau(a)$, so we have a contradiction.

For the sake of contradiction, assume that there do not exist integers $x,y,z$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$. Then, we look at a number $a \in S$. Obviously, there exists an infinite set $T \subset S$ such that for all $k \in T$, we have $\gcd(a,k)=b$ for fixed $b \mid a$. Because of our conditions for $T$, we must have $a_1, a_2 \in T$ such that $\gcd(a_1,a_2)=b$. Without loss of generality, assume that if $p \notin T$, then $\gcd(a,p) \neq b$. If this is not true, we append all such numbers that satisfy the condition for $T$ to $T$. Since $T \neq S$, we can easily find a pair $a_1,a_2 \in T$ such that $\gcd(a, a_1) = \gcd(a, a_2) \neq \gcd(a_1, a_2)$, contradiction. $\square$

We can derive a few existence results using Pigeonhole and the infinite size of $S$. Consider an integer $k \in S$. Then there are infinitely many values $m$ for which $\gcd(k,m)=d$ for at least 1 divisor $d$ of $k$, which we denote as the set $M$. Suppose there exists $m_1 \ne m_2 \in M$ such that $\gcd(m_1,m_2) \ne d$. Then we have the valid triple \[(x,y,z) = (m_1,k,m_2).\] Otherwise we conclude $\gcd(m_i, m_j)=d$ for all possible $m_i \ne m_j \in M$. Now, we must have some element $n \neq k$ in set $S$ but not in set $M$ to not violate the first condition. Similar to before, we can find infinitely many $p \in M$ such that $\gcd(n,p) = d'$. Thus we construct our ordered triple \[(x,y,z) = \begin{cases} (p_1,n,p_2) & \text{if } d \ne d' \\ (k,p_1,n) & \text{if } d = d' \end{cases}. \quad \blacksquare\]

Feel dubious about this solution, a look-over from someone else would be very appreciated. Fix some element $t \in S$. We prove the contrapositive of the given statement; that is, we assume there do not exist pairwise distinct $x, y, z \in S$ such that $\gcd (x,y) = \gcd (y,z) \neq \gcd (z, x)$ and prove that all pairwise distinct $a, b, c, d \in S$ satisfy $\gcd (a, b) = \gcd (c, d).$ Suppose $S = \{t, t_1, t_2, t_3, \ldots\}$. The set of possible $\gcd (t, u)$ for $u \in \mathbb{Z}^{+}$ is finite, and is the set of divisors of $t$. Thus the sequence $\gcd (t,t_1), \gcd (t,t_2), \gcd (t,t_3), \ldots$ has at least one infinite constant subsequence; pick one of them arbitrarily, and call the constant $k$. Let $U$ be the set of all $t_i$ such that $\gcd (t, t_i)= k$. Note that If for any distinct $i, j \in \mathbb{Z}^{+}$ it is true that $\gcd (t, t_i) = \gcd (t, t_j) = k$, then $\gcd (t, t_i) = \gcd (t, t_j) = \gcd (t_i, t_j)$. Thus any two elements of $U$ have $\gcd$ equal to $k$. So we assume $U \neq S \backslash \{t\}$; if $U = S \backslash \{t\}$, then clearly the $\gcd$ of any two elements of $S$ is equal to $k$ and we are done. Without loss of generality assume $t_1 \notin U$. Let $U = \{u_1, u_2, u_3, \ldots\}$ for notational ease, such that $\gcd (t, u_i) = k$ for any positive integer $i$. Now note that for any positive integer $i$, $\gcd (t, t_1) \neq \gcd (t, u_i) = k$, so therefore $\gcd (t,t_1), \gcd (t, u_i), \gcd (u_i, t_1)$ are pairwise distinct; thus for all $i \in \mathbb{Z}^{+}$, $\gcd (u_i, t_1) \neq k$. Using similar methods as before, noting that $U = \{u_i\}$ is infinite, and noting that there are a finite number of possible values for the $\gcd$ of $t_1$ and a member of $U$, we find that the sequence $\gcd (t_1, u_1), \gcd (t_1, u_2), \gcd (t_1, u_3), \ldots$ has at least one infinite constant subsequence; pick one of them arbitrarily, and call the constant $l$. Note that $l = \gcd (t_1, i_i) \neq k$. Let $V$ be the set of all $u_i$ such that $\gcd (t_1, u_i) = l$. Take distinct $v_1, v_2$ in $V$. Then $\gcd (t_1,v_1) = \gcd (t_1, v_2) = l$, and as $v_1, v_2 \in V \subseteq U$, we find $\gcd (v_1, v_2) = k$. But we found before that $k \neq l$, a contradiction. Thus $U$ must be equal to $S \backslash \{ t\}$ and we are done.

Consider the complete graph $G$ where each element of $S$ is a vertex. An edge between $a, b$ is "colored" by $\gcd(a,b)$. We wish to prove that there exists a triangle $x,y,z$ with 2 colors. By the problem statement there are at least 2 seperate colors in $G$. Also since $\gcd(a, x) \leq a$ we have that each vertex has an infinite degree, but finitely many colors of its edges. By the pigeon hole principle each vertex has an infinite amnount of edges of some color. Consider some vertex $V$ with an infinite number of edges with the color $C_1$. Let its neighbors by these edges be $V_1, V_2, V_3, \cdots$. If any $V_i, V_j$ are joined by some other color, then we are done, so assume that this is not the case. (All $V_i, V_j$ are joined by an edge of color $C_1$). Clearly with this logic we have some subgraph $H$ which is a completely connected graph with edges only of color $C_1$. There must exist some $V'$ outside of H. Thus $V'$ does not share an edge of color $C_1$ with any member of $H$. Since $H$ is infinite and $V'$ has finitely many colors, there must be two vertices $V_x, V_y \in H$ such that the edges $\overline{V'V_x}$ and $\overline{V'V_y}$ are of some color $C_2 \neq C_1$, as desired.

Take some integer $x$, and consider the values of $\gcd(i, x)$ over all $i \in S$. One of these values, $k$, must be repeated infinitely many times. Let $A$ be the set of all $i \in S$ satisfying $\gcd(i, a) = k, i \neq x$. If $\gcd(c,d) \neq k$ for two elements $c,d \in A$, we are done. Otherwise, we must have some element in $S$ and not in $A$ for the condition to be true. In addition, for each prime power $p$ such that $p$ does not divide $k$, $p$ can divide at most one element in $A$, otherwise we would have the $\gcd$ of two elements in $A$ is greater than $k$. Now take some element $y \in S, y \notin A$. Consider all prime divisors $q_i$ of $y$. For each $q_i$, the statement $v_{q_i}(z) = v_{q_i}(k)$ holds for all but at most one element $z$ of $A$ (note that the equal sign can be a greater than for exactly one number, and it can never be a less than by the $\gcd$ condition). To finish, there must exist infinitely many numbers in $A$ that mirror the $q_i$ valuation of $k$ over all $i$, so take two of these numbers $e,f$. We know $\gcd(y,e) = \gcd(y,f)$, if $\gcd(y,e) \neq k$ we are done, otherwise we have $k = \gcd(x,e) = \gcd(y,e) \neq \gcd(x,y)$ from the definition of $y$.

OG! My solution is same as #5

The problem stated in its contrapositive is as follows. Quote: Let $S$ be an infinite set such that if $x$, $y$ and $z$ are distinct elements of $S$ satisfying $\gcd( x,y) = \gcd(y,z)$, then $\gcd(x,y) = \gcd(y,z) = \gcd(z,x)$. Prove that for all pairwise distinct $a,b, c, d \in S$, we have $\gcd(a,b) = \gcd(c,d)$. Let $y$ be an element of $S$. Then, by pigeonhole there must exist some $k$ for which the equation $\gcd(y,x) = k$ has infinitely many solutions for $x \in S$. Fix this $k$ and consider the graph with the elements of $S$ as vertices. The problem condition tells us that if we have edges $ab$ and $bc$, we also have edge $ac$. Since $y$ has infinite degree, we can use this rule to deduce that it is part of an infinite complete component of the graph. Call this component $T$. For the sake of contradiction, assume there is another component in this graph and let $v$ be a vertex of this component. Then, by pigeonhole, there exist distinct $t_1, t_2 \in T$ for which $\gcd(v,t_1) = \gcd(v,t_2)$. Since there is no edge between $v$ and $t_1$ or $t_2$, this GCD is not equal to $k$. But then, the problem condition tells us that $\gcd(t_1, t_2) \neq k$, giving us a contradiction. So, $T=S$ and $\gcd(a,b) = \gcd(c,d) = k$ for all $(a,b,c,d)$ satisfying $a \neq b$ and $c \neq d$.

We rename variables in the problem statement so that they don't coincide with variables used in my solution: Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a_1, a_2, a_3, a_4 \in S$ with $\gcd(a_1, a_2) \neq \gcd(a_3, a_4)$. Prove that there exist three pairwise distinct $x_1, x_2, x_3 \in S$ such that $\gcd(x_1, x_2)=\gcd(x_2, x_3) \neq \gcd(x_3, x_1)$. Suppose this was not the case. Let $P(x_1, x_2, x_3)$ for pairwise distinct $x_1, x_2, x_3 \in S$ denote the assertion that $\gcd(x_1, x_2), \gcd(x_2, x_3), \gcd(x_3, x_1)$ are either all equal or pairwise distinct. Fix an $a\in S$. Notice that are only finitely many possible gcds of $a$ and another element in $S$, so let $d$ be a positive integer so that infinitely many $x\in S$ satisfy $\gcd(a,x) = d$. Now let $T$ be the subset of $S$ that is the set of all $x \in S$ not equal to $a$ so that $\gcd(a,x) = d$. Claim: For all $x\in S$, we have $\gcd(a,x) = d$. Proof: Suppose not and there was some $b \in S$ with $\gcd(a,b) \ne d$. Firstly, for any different $x,y \in T$, $P(a,x,y)$ gives that $\gcd(x,y) = d$ since $\gcd(a,x) = \gcd(a,y) = d$. Consider distinct $x,y \in T$ so that $x \equiv y \pmod b$ (these must exist by infinite pigeonhole). Note that $\gcd(b,x) = \gcd(b,y)$, so $P(b,x,y)$ gives that $\gcd(b,x) = \gcd(b,y) = \gcd(x,y) = d$. Now, since $\gcd(a,x) = \gcd(b,x) = d$, $P(a,b,c)$ gives $\gcd(a,b) = d$ also, a contradiction. $\square$ This means that $T = S \setminus \{a\}$. Claim: For any different $m,n \in S$, we have $\gcd(m,n) = d$. Proof: If one of $m,n$ equals $a$, the result is already shown. Assume that neither of $m,n$ are equal to $a$. Since $\gcd(a,m) = \gcd(a,n) = d$, $P(a,m,n)$ gives $\gcd(m,n) = d$, as desired. $\square$ Now, for any pairwise distinct $a_1, a_2, a_3, a_4 \in S$, we have $\gcd(a_1, a_2) = \gcd(a_3, a_4) = d$, a contradiction.

Okay this is insanely cool i guess. We try to prove a statement implying the contrapositive instead: Quote: Suppose we have that $g = \gcd(x,y)=\gcd(y,z) \implies g = \gcd(z,x)$. Then $gcd(x, y)$ is the same over all pairs $x \ne y \in S$. For each $k \in \mathbb{N}$, we draw the graph $G_k$ with vertex set $S$ such that $x-y \iff gcd(x, y) = k$. | Claim 1: It suffices to show $G_k$ is connected for some $k$. Proof: Then we just take an (infinite!) spanning tree and induct to show that all edges must be present by semi-induction. $\square$ Claim 2: There exists a $G_k$ with an infinite connected component. Proof: Assume FtSoC that all $G_i$ are composed of finite connected components. Then the degree of any vertex is finite in each component. Thus the vertex must have nonzero degree in infinitely many of these graphs, implying it must have infinitely many divisors, contradiction. $\square$ Now we consider this $G_k$ and this infinite connected component $T = \{ka_1, ka_2, \dots \}$ (here the set shows the vertices of $T$). We claim that $T = S$. Indeed, assume that $T \subsetneq S$, and consider some $v \in S \setminus T$. Let $\gcd(v, k) = d$. Then $u = \frac{v}{d}$ shares a common factor with each of $a_1, a_2, \dots$. But as the $a_i$ are pairwise coprime, this quantity$u$ has infinitely many factors, which is a contradiction. $\square$ This completes the proof of the statement, as desired. $\square$ Remark: If I'm not wrong, the statement I've mentioned at the start is in fact equivalent to the problem statement.

Assume FTSOC not. Fix $d$. Notice \[ T = \{ \gcd(x, d) : x \in S \} \]is finite. By PHP, then there exists $M \in T$ such that \[ A = \{ x : \gcd(x, d) = M, x \in S \} \]is infinite. Then Claim: We have $x, y \in A \implies \gcd(x, y) = M$. Proof. This is seen because \[ x, y \in A \implies M = \gcd(x, d) = \gcd(y, d) = \gcd(x, y) \]$\blacksquare$ Now, I claim Claim: For all $x \in S$, actually $x \in A$. Proof. Pick some $z \in S$. Since \[ V = \{ \gcd(x, z) : x \in A \} \]is finite, then there is a $K \in V$ such that \[ B = \{ x : \gcd(x, z) = K, x \in A \} \]is infinite. Moreover, then \[ x, y \in B \implies K = \gcd(x, z) = \gcd(y, z) = \gcd(x, y) \]but $x, y \in A$ by definition, so $\gcd(x, y) = M$. Thus we find that $K = M$. Then, \[ x \in B \implies \gcd(x, z) = M = \gcd(x, d) \]\[ \implies \gcd(z, d) = M \]But then by definition, we must have $z \in A$, as needed. $\blacksquare$ It follows that $x, y \in S \implies \gcd(x, y) = M$, which is clearly a contradiction. $\blacksquare$

claim 1:for each $X_i$ chosen $K$=$gcd(X_i , Z_k)=gcd(X_i,Y_k)$: proof: it's quite straightforward by the $pigeonhole$ $principle$ since the divisors of $X_i$ are finite so suppose FSOC that if $gcd(X_i , Z_k)=gcd(X_i,Y_k)$ then$gcd(X_i , Z_k)=gcd(X_i,Y_k) =gcd(Z_k,Y_k)$ and call such numbers $clikets$ , then by the exercice's condition we have at least $2 $$cliquets $ and note also that the intersection of 2 cliquets cannot exceed 1 element but then we would have at least $2$ members from one cliket with one from another $cliket$ such that $gcd(Y_1,T_1)$=$1$ and $gcd(Y_2,T_1)$=$1$ then $gcd(Y_1,Y_2)$=$1$ .contardiction $\blacksquare$