-2
$\begingroup$

I apparently need to rephrase the question(s), so here goes:

I'm an amateur mathematician, and I have been working for quite some time on finding a more efficient way of factoring large semiprime numbers, with little to show for it. However, I did discover and intriguing relationship between the prime numbers through the addition and subtraction of relatively prime numbers which must meet certain condition. The first condition is of course that the two numbers must actually be relatively prime. The second condition is that when these two numbers are multiplied together, their product must contain every prime number up to an arbitrary prime number p(n-1). Third and lastly, the resulting sum or difference must not be 1 and it must be less than the square of the next prime number, i.e. $p(n)^2$. If these conditions are met, the resulting sums and differences will be prime. My question is this:although this is provable, is it original, and is it efficient?

Improve this question
$\endgroup$
6
  • $\begingroup$ For my way to generate all primes recursively, see mathoverflow.net/questions/328086. $\endgroup$
    – Zhi-Wei Sun
    Apr 15, 2019 at 0:51
  • $\begingroup$ An unfortunate side effect of the edit is that the comment and answers previously posted are now non-responsive. $\endgroup$
    – Gerry Myerson
    Apr 15, 2019 at 5:04
  • 1
    $\begingroup$ Anyway, kudos to you on your discovery, but I'm afraid it's at the level of a homework problem in an introductory Number Theory class. It doesn't strike me as an efficient way to generate primes, either. To find a prime exceeding, say, $1000$, consider how big that product $P$ of primes up to $1000$ is, then consider how much work you have to do to find $r,s$ such that $rs=P$ and $r-s$ is small enough. There are easier ways to find primes. But you might do a search for a paper called "Primes at a glance". $\endgroup$
    – Gerry Myerson
    Apr 15, 2019 at 5:11
  • $\begingroup$ Here's a link to Primes at a glance: ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866108-3/… $\endgroup$
    – Gerry Myerson
    Apr 15, 2019 at 8:30
  • 1
    $\begingroup$ To answer the revised questions: yes it is provable, and no it is neither original nor efficient. Gerry Myerson's suggestion of reading "Primes At A Glance" is good; you might consider showing a number is prime by looking at its remainder modulo smaller primes. You may find a brief speedup over trial division, but I doubt that such a method is asymptotically faster than trial division. Gerhard "Products Grow Large Pretty Fast" Paseman, 2019.04.15. $\endgroup$
    – Gerhard Paseman
    Apr 15, 2019 at 16:25

2 Answers 2

Reset to default
3
$\begingroup$

This question is not of research level, but I felt like answering it.

It is not clear what you mean by "divisibility testing". Fermat's little theorem says that if $p$ is prime, then $x^p-x$ is divisible by $p$ for any integer $x$. Modern primality tests (hence also the reliable methods for generating primes) are ultimately based on this principle, with elaborate modifications of course. The point is that, in testing whether $n$ is a prime, we do not test if potential smaller $m$'s divide it. Instead, we test if $n$ divides certain quantities depending on $n$.

Improve this answer
$\endgroup$
1
$\begingroup$

Interpreting the question literally, yes! See Formula for primes on Wikipedia, especially the section on Diophantine representation. The set of primes is exactly the set of positive values of a certain explicitly given polynomial. This method is reliable, in that it will eventually generate all primes below any given bound, but is not efficient (even the classical sieve of Eratosthenes is faster for generating prime tables).

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.