# Generating Prime Numbers From Composite Numbers

If $$a$$ and $$b$$ are non-perfect-square composite numbers, and $$\gcd(a,b)=1$$, then at least one element of {$$ab-1,ab+1$$} is a prime number.

For example, if we let $$a=35$$, and $$b=18$$; clearly the are free-square composite numbers, and gcd$$(35,18)=1$$

$$ab-1=35\times18-1=629$$ which is a composite number, and

$$ab+1=35\times18+1=631$$ which is a prime number.

Is the statement true?

• $18 = 3^2\cdot 2$ is not square-free. – Arthur Nov 22 '18 at 14:16
• If you multiply two coprime numbers with lots of small prime factors in them, you're going to get a medium-sized (3-4 digit) number with lots of small prime factors. If you add or subtract $1$ to / from that, you get a new number of the same size with no small prime factors. The odds of that number itself being prime is thus quite high. It's not a guarantee in any way, but it explains why it took me a minute or two of searching to find a counterexample. – Arthur Nov 22 '18 at 14:38

You certainly need at least one of $$a,b$$ to be even to have any hope that one of these is always prime. However, even then it's not true. For example, take $$a=38,b=143$$, so $$ab=5434$$. neither $$5433$$ nor $$5435$$ is prime.
 As Arthur points out my example is rather larger than necessary. $$ab$$ must be a product of at least four distinct primes. If it is a product of more than four primes, it must be at least $$2310$$ (which isn't a counterexample). So we can look at the values in this sequence below $$2310$$ and check whether the neighbouring numbers are composite to find the first (i.e. smallest $$ab$$) few counterexamples. They are:
If both $$a$$ and $$b$$ are odd, then $$ab\pm 1$$ are both even and therefore not prime.
Even if one of them are even, there are counterexamples. For instance, $$a = 34, b = 21$$ gives $$ab + 1 = 715 = 5\cdot 11\cdot 13\\ ab - 1 = 713 = 23\cdot 31$$
• $a$ and $b$ are required to be composite, so $ab$ is not a general square-free number. Any square-free number with at least four prime factors would work though. – Especially Lime Nov 22 '18 at 14:23