…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?
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.
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.