Putnam 1999, Problem B-6

Let \(S\) be a finite set of integers, each greater than 1. Suppose that for each integer \(n\) there is some \(s \in S\) such that \(\gcd(s,n) = 1\) or \(\gcd(s,n) = s\). Show that there exist \(s, t \in S\) such that \(\gcd(s,t)\) is prime.


Solution:
First solution: Choose a sequence $p_1, p_2, \ldots$ of primes as follows. Let $p_1$ be any prime dividing an element of $S$. To define $p_{j+1}$ given $p_1, \ldots, p_j$, choose an integer $N_j \in S$ relatively prime to $p_1 \cdots p_j$ and let $p_{j+1}$ be a prime divisor of $N_j$, or stop if no such $N_j$ exists.

Since $S$ is finite, the above algorithm eventually terminates in a finite sequence $p_1, \ldots, p_k$. Let $m$ be the smallest integer such that $p_1 \cdots p_m$ has a divisor in $S$. (By the assumption on $S$ with $n = p_1 \cdots p_k$, $m = k$ has this property, so $m$ is well-defined.) If $m = 1$, then $p_1 \in S$, and we are done, so assume $m \geq 2$. Any divisor $d$ of $p_1 \cdots p_m$ in $S$ must be a multiple of $p_m$, or else it would also be a divisor of $p_1 \cdots p_{m-1}$, contradicting the choice of $m$. But now $\gcd(d, N_{m-1}) = p_m$, as desired.

Second solution (from sci.math): Let $n$ be the smallest integer such that $\gcd(s,n) > 1$ for all $s$ in $n$; note that $n$ obviously has no repeated prime factors. By the condition on $S$, there exists $s \in S$ which divides $n$.

On the other hand, if $p$ is a prime divisor of $s$, then by the choice of $n$, $n/p$ is relatively prime to some element $t$ of $S$. Since $n$ cannot be relatively prime to $t$, $t$ is divisible by $p$, but not by any other prime divisor of $n$ (as those primes divide $n/p$). Thus $\gcd(s,t) = p$, as desired.