If $a$ and $b$ are co-primes, and $p$ is prime, factoring $a \cdot p + b$ will eventually always generate a new larger prime $q$

Question

Let $a$ and $b$ be co-primes, $p$ prime, and $f_0 = p$.

Let $f_{(n+1)} = SPF(a \cdot f_n + b) \cdot f_n $, where $SPF(x)$ is the smallest prime factor of $x$.

Repeat until $SPF(a \cdot f_n + b) = a \cdot f_n + b $, then we have found the new prime $q = a \cdot \prod^n_{j=1} f_n + b$.

Example: \begin{align*} a &=6666 \\ b &=47 \\ f_0 &= 7 \\ 6666 \cdot 7 + 47 &=13 \cdot 3593 \implies f_1 =7 \cdot 13 \\ 6666 \cdot 7 \cdot 13+47 &=606653 \\ SPF(606653) &= 606653 \end{align*} So $q= 606653$ is the new prime!

I've tried this for a lot of different combinations, it always seems to work or leads to a number $f_n$ that I was not able to factor. It's kind of ironical that factoring will lead to a new prime. It's almost as if the composite number "knows" how to find a new prime. Why is this the case? And is it possible to proof that this algorithm will always produce a new prime?

Answer 1

I may be mistaken but I think you are leveraging Drichlet's Theorem in some form. The theorem, as stated here is:

For any two coprime integers $a$ and $b$, there are infinitely many primes of the form $a + nb$ for a non-negative integer $n$. Stated otherwise, there are infinitely many primes in the arithmetic progression $a + nb$.

You pick two coprime integers $a$ and $b$ and the thing you are doing by multiplying $a$ by some primes is essentially just marching through the arithmetic progression of $b + na$ (albeit rather haphazardly). That condition that $SPF(a\cdot f_n + b) = a\cdot f_n + b$ is just a primality test in disguise.

So in essence, a better version of your algorithm would be:

Pick two coprime integers $a$ and $b$ and let $f_0 = 0$. Let $f_{n+1} = f_n + 1$ and repeat until $SPF(a\cdot f_n + b) = a\cdot f_n + b$ or, in other words, until $a\cdot f_n + b$ is prime. Such a number must exist by Drichlet's theorem since there are infinitely many primes in the arithmetic progression $b + na$. Thus we have found a bigger prime.

Because you jump around the arithmetic progression in larger leaps than a linear march, there is a chance that you may "miss" the primes in the sequence. However proving/disproving your way will always find a prime is definitely nontrivial.