Let $n \in \mathbb{Z}$ be a semi-prime with unknown factorization, $n = pq$, where $p, q \in \mathbb{P}$, the set of primes. Without loss of generality, let $p \lt q$.
Say we have done trial division and determined that $2, 3, 5, ..., p_{\beta} \in \mathbb{P}$ where $p_{\beta} < \beta$, a smooth bound, do not divide $n$.
If $\exists r,t \in \mathbb{Z}$ such that $q = p_{\beta} + rt$ and $q - p_{\beta} \gt p$ then $\exists r \in \mathbb{P}$ by the prime factorization theorem. We know that for sufficiently large $\beta$, $r = 2$ is possible since the difference of primes is even.
Q1: Is it true that $\exists r > p_{\beta}, r \in \mathbb{P}$?
Example: Let $q = 73$ and $2, 3, 5, p_{\beta} = 7$. We have $q = 73 = 7 + 11 \times 6$ and $r = 11, t = 6$.
Dirichlet's prime number theorem states that there are infinitely many primes in any arithmetic progression $a + nd$ with $a, d$ coprime.
My question could alternatively be stated as:
Q2: whether a specific prime greater than $p_{\beta}$ occurs in a any arithmetic progression with initial term $p_{\beta}$? (Edit: @abiessu's comment answers this affirmatively)
The motivation for this question is to build a factoring sieve. After exhausting trial division up to the bound $p_{\beta}$, we want to switch to arithmetic progressions to search for primes up to $\sqrt n$. I suppose there exist effective arithmetic progressions with large $r$ that can yield $p$ or $q$ in very few steps (i.e., small $t$).