Putnam 2009, Problem A-4

Let $S$ be a set of rational numbers such that
(a) $0 \in S$;
(b) If $x \in S$ then $x + 1 \in S$ and $x - 1 \in S$; and
(c) If $x \in S$ and $x \notin \{0, 1\}$, then $\frac{1}{x - 1} \in S$.
Must $S$ contain all rational numbers?

Solution:
The answer is no; indeed, \( S = \mathbb{Q} \setminus \{n + 2/5 \mid n \in \mathbb{Z}\} \) satisfies the given conditions. Clearly \( S \) satisfies (a) and (b); we need only check that it satisfies (c). It suffices to show that if \( x = p/q \) is a fraction with \( (p,q) = 1 \) and \( p > 0 \), then we cannot have \( 1/(x(x-1)) = n + 2/5 \) for an integer \( n \). Suppose otherwise; then
\[
(5n + 2)p(p - q) = 5q^2.
\]
Since \( p \) and \( q \) are relatively prime, and \( p \) divides \( 5q^2 \), we must have \( p \mid 5 \), so \( p = 1 \) or \( p = 5 \). On the other hand, \( p - q \) and \( q \) are also relatively prime, so \( p - q \) divides \( 5 \) as well, and \( p - q \) must be \( \pm 1 \) or \( \pm 5 \). This leads to eight possibilities for \( (p,q) \): \( (1,0) \), \( (5,0) \), \( (5,10) \), \( (1,-4) \), \( (1,2) \), \( (1,6) \), \( (5,4) \), \( (5,6) \). The first three are impossible, while the final five lead to \( 5n + 2 = 16, -20, -36, 16, -36 \) respectively, none of which holds for integral \( n \).

**Remark.** More generally, no rational number of the form \( m/n \), where \( m,n \) are relatively prime and neither of \( \pm m \) is a quadratic residue mod \( n \), need be in \( S \). If \( x = p/q \) is in lowest terms and \( 1/(x(x-1)) = m/n + k \) for some integer \( k \), then \( p(p - q) \) is relatively prime to \( q^2 \); \( q^2/(p(p - q)) = (m + kn)/n \) then implies that \( m + kn = \pm q^2 \) and so \( \pm m \) must be a quadratic residue mod \( n \).