Playing with Prime Numbers


Eureka! Eureka!


…was just playing around with prime numbers and look what I have found. I have no idea whether this type of definition for prime numbers already exists in number theory. And I have never seen any algorithm used in computer science to detect prime number using this technique.


Theorem             Suppose P is an odd number represented by 2n+1. Then P is prime iff there exist no x, y Î Z+ such that n equals 2xy+x+y.


The proof is pretty simple, just couple of lines.  

My big question is, does this new definition has any significance ? And does this  theorem/def. already exists ?


Some comments I have received about this new theorem from my friends

If we try to see the relation among n, x and y.  n=(1+2x)(1+2y). Also note that x,y>0 and are integers. This only makes the given theorem equivalent to “A odd number P is prime iff it can’t be expressed as product of two odd numbers greater than 1”. This gives no extra information and can be derived from the definition of a prime number. What do you say?

My reply:

Exactly. It doesn’t give more information than that. But what’s interests me really is … does it reduce the complexity of algorithm in time?  It’s just an attempt…  and I am yet to frame an algorithm which can work out as per this theorem.

Another comment:

I can provide a more simple criteria:

 Theorem            P is prime iff there exist no x, y Î Z+ with x<p and y<p, such that xy = n.


My Theorem is so trivial, because it’s just the definition of prime. But, it has the same computability with your theorem. Because my equation (xy = n) is just has the same order with yours (2xy+x+y = n). To solve such a two-variable integer equation, you have to search in the 2-dimension integer plane. That leads to a O(n^2) complexity.


Overall, I think your theorem is trivial, and there is no new discovery in it.

Probably, I was over excited about this one as it turns out to be just a very simple thing. But somehow it still attracts me. 2xy + x + y, this equation has something in it. I really need to spend sometime on this.