Define S as a set of primes such that if a, b are in S, ab+4 is in S. Show that S must be empty.

Question

Define $S$ as a set of primes such that $(a \in S) \land (b \in S) \implies (ab + 4) \in S$ [$a$ and $b$ can be the same number]. Show that $S$ must be empty.

A hint is given ... "work modulo 7."

Attempted solutions: Assume $S$ is nonempty i.e. it contains at least one prime integer $a$. $S$ must therefore contain infinite integers derived from $a$. I aim to find at least one integer in $S$ which isn't prime.

$a \in S$

$\therefore a^2 +4 \in S$

$\therefore a^3 +4a+4 \in S$

In general, $a^n + 4\sum_0^{n-2} a^k \in S$. Is it possible to prove that for any $a$, one of the numbers in this sequence is composite? That's as far as I've gotten. I can't figure out how to use the modulo 7 hint.

Answer 1

Mod $7$, the operation $x\mapsto x^2+4$ maps $2\rightarrow1\leftrightarrow5\leftarrow6\leftarrow3,4\leftarrow0$. It always generates $1$. Then, the operation $x\mapsto 1x+4$ maps $1\rightarrow5\rightarrow2\rightarrow6\rightarrow3\rightarrow0$.

Edit: Okay, I can tell you why we should try $7$. The strategy for a prime $p$ requires that the operation $x\mapsto x^2+4$ does not have a (nonzero) fixed point in the field of integers modulo $p$. It's easy to see that there are solutions mod $2$, so that prime is useless. Next, if $p$ is odd, then we can complete the square: $(2x-1)^2=-15$. Just reading the factorization $15=3\times5$ gives us solutions modulo those primes, so they're also useless. The smallest prime that we haven't ruled out is $7$, and it works.

Someone better at number theory would find it easy to give you exact criteria for when $-15$ is a quadratic residue modulo $p$, and they might even be able to come up with criteria for when the strategy as a whole will succeed and when it will fail.

Answer 2

I have another one.Let a prime $p\in S$ which is not of the form $2^k+1$ then iterating the given expression we see all numbers of the form $k_n=p^{n+2}+4(p^n+...+p+1)\in S \forall n\in\mathbb{N}$.Now consider an odd prime $q\mid p-1$ then see that $k_n\equiv 4n+5\pmod{q}$ hence $q$ has a multiple of the form $4n_0+5$ for some $n_0\in \mathbb{N}$.Hence we see $q\mid k_{n_0}$contradicting its primality.Hence all elements of the set must be of the form $2^k+1$.So let $p=2^k+1$ then $p^2+4\in S$ but $p^2+4=1+4(2^{2k-2}+2^{k-1}+1)$ which cannot be of the form $2^k+1$.So contradiction.

Answer 3

$\>\>\>\>$ Suppose $a \in S$.

$\>\>\>\>$ If $a=7$, then (the composite) 375 = $7(7^2+4)+4 \in S$. Thus, $7=a \notin S$.

$\>\>\>\>$ Suppose $a \equiv 1$(mod 7). Then, $b = (a^2+4)(a(a^2+4)+4)+4 \in S$. But, $b \equiv -2(1(-2)+4)+4 = 0$(mod 7). Therefore, $a \notin S$.

$\>\>\>\>$ Suppose $a \equiv -1$(mod 7). Then, $b=(a^2+4)^2+4\in S$. But, $\>\>b \equiv ((-1)^2+4)^2+4 \equiv 1$(mod 7). Hence, $a \notin S$.

$\>\>\>\>$ Suppose $a \equiv \pm 2$(mod 7). Then, $b=a^2+4 \in S$. But, $b \equiv (\pm2)^2+4 \equiv 1$(mod 7). So, $a \notin S$.

$\>\>\>\>$ Suppose $a \equiv \pm 3$(mod 7). Then, $b=a^2+4 \in S$. But, $b \equiv (\pm3)^2+4 \equiv -1$(mod 7). Thus, $a \notin S$.