Show that the set of primes that do not divide any element of $S$ is finite.

contest-mathnumber theory

Let $S$ be a nonempty set of positive integers such that, for any (not necessarily distinct) integers $a$ and $b$ in $S$, the number $ab+1$ is also in $S$. Show that the set of primes that do not divide any element of $S$ is finite.

This looks very interesting. But I wans't able to proceed. It's from Modular arithmetic chapters. So I tried Mods but failed.

Best Answer

Let $p$ be a prime. Henceforth, work modulo $p$. Consider $ P = \{ s \pmod{p} | s \in S \}$.

Hint: Show that $P$ is either a singleton, or the entire residue class.
Looking at $P$ is very natural, and the result is reasonably easy to guess by looking at small cases of $p$.
EG For $ p = 7$, try the cases where we have seeds $\{1\}, \{2\}, \{3\}$ and see what you get. These cases are somewhat distinct, have a lot to offer, and might suggest ways to prove the hint.

This takes some work. If you're stuck, show what you've tried.

If $ 0 \in P$, then $ 1 \in P$ and by induction $P = \{ 0, 1, \ldots, p-1 \}$.

Suppose we have distinct non-zero elements $s_1, s_2 \in P$. Consider the map $P \rightarrow P$ with $ s \rightarrow s_1 s + 1 $.
Verify that the map is a bijection.
Hence, conclude that $\sum s_i \equiv s_ 1 ( \sum s_i) + |P|$
If $ \sum s_i \equiv 0$, then $|P| = p$ as desired.
Otherwise, if $ S = \sum s_i \not \equiv 0$, conclude that $ s_1 \equiv 1 - \frac{|P|}{S} \equiv s_2 $, which is a contradiction.

Corollary: For any $ a \in S$, given any prime $p$ that doesn't divide $ a^2 - a + 1 $, then $ a^2 + 1 \not \equiv a \pmod{p}$, so $P$ has at least 2 elements thus is the entire residue class, and thus there exists some element of $S$ that is a multiple of $p$.
Hence, the set of primes that does not divide any element of $S$, is a subset of the prime factors of $a^2 - a + 1$ (and thus is finite).

Notes:

  • With the seed $ a = 1$, we get $ S = \mathbb{N}$. This isn't that useful, but it does suggest the "entire residue class".
  • With the seed $ a = 2$, we get a subset of $ \{ 3k+2 \}$, and we see that $ 3 = a^2 -a + 1$ is the only prime that doesn't divide any term of this larger set.
  • If $ 1 \in P$, we can likewise show that by induction that $2, 3, \ldots p-1, 0 \in P$. Also, the map $ s\rightarrow 1\times s + 1 $ gives us the result.
    • Clearly the only way to show $ ab+1 = 1 \in P$ is that there exists an $ab \equiv 0 \in P$, which then requires an $ a\equiv 0 \in P$.
    • By using $ ab + 1 = 0 \in P$, this opens us a lot of possibilities. In particular, if $ |P| > p/2$, then we can conclude $ 0 \in P$ and hence the result.
    • I'd love to see a solution along these lines.
  • Some sequences to naturally consider are:
    • $a_{i+1} = a_i ^2 + 1, a_ 1 = a $
    • $ b_{i+1} = a \times b_i + 1, b_ 1 = a$.
    • $c_{i+2} = c_{i+1} \times c_i + 1 , c_1 = c_2 = a$.
    • I'm interested in any solution using this, but TBH I doubt a solution exists (some details below).
  • For $ p = 7$, starting with seed $2$,
    • if you use the sequence $a_i$, you get $ 2, 5 , 5, 5, \ldots$ so are stuck. It is when you use $ 2 \times 5 + 1 \equiv 4$ that breaks you out.
    • If you use the sequence $b_i$, then you get $2, 5, 4, 2, 5, 4, \ldots$ and are stuck, so we need $ 5\times 4 + 1 \equiv 0$.
    • If you use $c_i$, then you'd get $2, 2, 5, 4, 0, 1, 1, 2, 3, 0, 1, 1, 2, 3, \ldots $ and are stuck (no 6).
    • This explains why I doubt there exists a solution via considering $a_i$ / $b_i$ / $c_i$ only.
  • The singleton case arises when we have $ a^2 + 1 \equiv a $ EG $a=2, p = 3$, or $ a = 3, p = 7$.
Related Question