Prove that for any positive integers $a$ and $b$ there exist infinitely many prime numbers $p$ such that $ap+b$ is a composite number. (Using Dirichlet's theorem is not allowed.)
Problem
Source: 2017 Belarus Team Selection Test 4.3
Tags: number theory, prime numbers
01.04.2019 03:46
Dirichlet may not be allowed, but Kobayashi is . Assume, for contradiction, that there are only finitely many primes $p$ for which $ap+b$ is composite. In other words, $ap+b$ is prime for all primes $p \ge C$ for some $C.$ Let's define the sequence $\{x_i\}$ by $x_0 = 0, x_1 = b,$ and $x_{i+1} = ax_i+b$ for $i \ge 1.$ $\mathbf{Claim.}$ There are infinitely many primes which divide at least one of the terms of $\{x_i\}$. $\mathbf{Proof.}$ Let $y_i = (a-1)x_i + b, \forall i \in \mathbb{N}_{\ge 0}.$ Then, it's easy to see that $y_i \equiv ba^i$, and so hence by Kobayashi, since $\{y_i\}$ is a sequence with finitely many prime divisors, we know that $\{(a-1)x_i\}$ is a sequence with infinitely many prime divisors. Therefore, as there are only finitely many divisors of $a-1,$ $\{x_i\}$ also has infinitely many prime divisors. $\blacksquare$ By the claim, we may consider some $p > C, i \in \mathbb{N}$ for which $p | x_i.$ Define the sequence $\{z_i\}$ by $z_0 = p$, and $z_i = az_{i-1}+b$ for all $i \in \mathbb{N}.$ Since $p > C,$ we know that $\{z_i\}$ consists only of primes. Obviously $\{z_i\}$ is increasing. By looking at $\{z_i\}$ in modulo $p$, we know that $z_i \equiv x_i$ (mod $p$). Therefore, as $p|x_i,$ we have that $p |z_i,$ contradicting the fact that $z_i$ is prime. $\square$
01.04.2019 04:18
Suppose not. Then for every prime $p>N$ we have $ap+b$ also prime. So $a(ap+b)+b, a(a(ap+b)+b)+b, \dots$ are primes, that is, $a^tp+b \frac{a^t-1}{a-1}=P_t$ is prime for every $t \in \mathbb{N}.$ But taking $t=ap+b$ implies $ap+b \mid P_t$, a contradiction.
03.06.2019 10:31
After claiming that for any prime $p$ large enough and any $n\in \mathbb{Z}^+$ $$P(p,n)=a^np+\frac{b(a^n-1)}{a-1}$$is prime, we could proceed with the following lemma. Lemma. For a fixed $a\in \mathbb{Z}^+$ and variable $n\in \mathbb{Z}^+$ numbers of the form $\frac{a^n-1}{a-1}$ have arbitrarily large prime divisors. Proof. Assume on the contrary there are only finitely many such primes. Call them $q_1, q_2, \dots, q_M$. Consider $$n=\prod^{M}_{i=1}q_i(q_i-1)+1$$It is easy to check that then $q_i \nmid a^n-1$ for any $q_i \nmid a-1$ and that for any $q_i \mid a-1$ by LTE we have $v_{q_i}(a^n-1)=v_{q_i}(a-1)$, so $\frac{a^n-1}{a-1}$ has a prime divisor distinct from $q_i$, and thus we have achieved a contradiction $\square$ Now we can take $p$ large enough and $n$ such that $p \mid \frac{a^n-1}{a-1}$ and thus have $p \mid P(p,n)$, but clearly $P(p,n)>p$. A contradiction $\blacksquare$
24.06.2019 18:20
Take a prime $q$ dividing $a+b$.It is well-known(And easy to prove of course the proof is an immediate application of cyclotomic polynomial.) that there exist infinity many primes $p$ with $p \equiv 1 \pmod q$ then $ap+b \equiv a+b \equiv 0 \pmod q$.but $ap+1>a+b \ge q$ so $ap+b$ will be composite.