Generating Prime Numbers From Composite Numbers

126 Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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 $$

0
On

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.

[edit] 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:

714, 870, 1155, 1190, 1254, 1330, 1365, 1518, 1590, 1770, 1785, 1794, 1806, 1938, 1995, 2046, 2145, 2170, 2190, 2210, 2226, 2262