6
$\begingroup$

Let $\mathbb{P}$ be the primes set.

We know from Wilson's Theorem that $$(p-1)!\equiv-1 \pmod p \iff p \in \mathbb{P}$$

What another formulas we have with an if and only if ($\iff$) statement to characterize primes, not equivalent or derived from Wilson's Theorem?

(I'm not asking about algorithms to primality tests, but rather expressions that hold exactly for primes using algebra, modulus, integrals and another things).

Or expressions like: $p \in \mathbb{P} \iff$ Expression using p

  • 0
    Search on "primality test".2012-04-20
  • 0
    I will change a little. I'm not looking for primality tests, but about iff expressions, that holds in all primes.2012-04-20
  • 3
    Such statements usually yield primality tests (though possibly inefficient). Why are folks voting to close this question as nonconstructive or not a real question? The question might be better received if it were better motivated.2012-04-20
  • 2
    What's the difference? A deterministic primality test involves testing the truth value of a set of conditions that is logically equivalent to being prime, ie an iff equivalence...2012-04-20
  • 1
    Well, this is a soft-question. And I'm new here. And I really think this question is constructive, at least for me^^. I would like know new things about this to investigate the primes myself.2012-04-20
  • 0
    anon, yes but. How can I say^^, I would like answers in this way, not about algorithms. I'm not implement algorithms for a while. And maybe I'll return with a question relating this.2012-04-20
  • 5
    You may be interested in Giuga's conjecture to the effect that $n$ is prime if and only if $1^{n-1}+2^{n-1}+\cdots+(n-1)^{n-1}\equiv-1\pmod n$. Verified up to some enormous number, but as yet unproved.2012-04-20
  • 0
    Gerry Myerson. Very interesting. Nice conjecture. This is the kind of thing I'm looking for. Thx.2012-04-20
  • 2
    Hopefully the question will be reopened. See the [meta thread.](http://meta.math.stackexchange.com/q/4017/242)2012-04-21
  • 0
    Thx so much Bill.Appreciate a lot your help.2012-04-21
  • 0
    If someone thinks will be better rewrite the text, it's ok to me. I just want the spirit of the question maintains.2012-04-21
  • 4
    @Fenri: The main problem, as I (and possibly others) see it is that the question is just too broad. There are literally whole chapters in many books addressing this question. As the FAQ states, "Your questions should be reasonably scoped. If you can imagine an entire book that answers your question, you’re asking too much." You may want to cut back on it somehow. But I've cast the fifth vote to re-open, so that these issues may be addressed (perhaps, also, someone can post an answer pointing out *why* what you ask **is** equivalent to a deterministic primality test).2012-04-21
  • 1
    @Arturo But there are plenty of other questions here that have entire chapters - if not entire books - devoted to them, e.g. [What is a universal property?](http://math.stackexchange.com/questions/63150/what-is-a-universal-property) No doubt the question could be greatly improved. But the reasons given so far for closure are inconsistent with other questions not closed.2012-04-21
  • 2
    @Bill: Which is *why* I voted to re-open, and why I am asking the OP to try to try to improve it somehow. I did *not* vote to close it, did I? And I *did* vote to reopen, didn't I? Sigh.2012-04-21
  • 0
    I ask sorry about the problems. Anyway I'm very happy because my question was reopened. I will try write specific questions (not soft-questions) next time. Thx a lot.2012-04-21
  • 1
    I would like to say thanks to all people that helped me.2012-04-21

3 Answers 3

8

A natural number $\theta$ is a prime number if and only if the equation

$ (k+2) (1 - [wz + h + j - q]^2 - [(gk + 2g + k + 1)(h + j) + h - z]^2 - [16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2]^2 - [2n + p + q + z - e]^2 - [e^3(e + 2)(a + 1)^2 + 1 - o^2]^2 - [(a^2 - 1)y^2 + 1 - x^2]^2 - [16r^2y^4(a^2 - 1) + 1 - u^2]^2 - [n + l + v - y]^2 - [(a^2 - 1)l^2 + 1 - m^2]^2 - [ai + k + 1 - l - i]^2 - [((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2]^2 - [p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m]^2 - [q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x]^2 - [z + pl(a - p) + t(2ap - p^2 - 1) - pm]^2) - \theta = 0$

has a solution where $a,b,c,...,z$ are nonnegative integers. (source)

  • 0
    A litle huge, but very interesting. Thx.2012-04-21
4

There exists a polynomial of degree $25$ in $26$ variables with integer coefficients such that the set of prime numbers is identical with the set of positive values taken on by the polynomial as the variables range over the non-negative integers. (The polynomial can be found here.)

In other words, there is a polynomial $h(a,b,c,\ldots,z)\in \mathbb{Z}[a,b,c,\ldots,z]$ such that a natural number $p\in\mathbb{N}$ is prime if and only if there are $a_0,b_0,c_0,\ldots,z_0\geq 0$ such that $p=h(a_0,b_0,c_0,\ldots,z_0)$.

Note: this statement cannot be used as a deterministic primality test. If $p>0$ is composite, then an algorithm based on this statement (that would check whether $p=h(a_0,b_0,c_0,\ldots,z_0)$ for some $a_0,b_0,c_0,\ldots,z_0\geq 0$), would never terminate since there is no (known) way to bound the size of the possible $26$-tuples that would give the desired equality.

  • 0
    Lovre Pesut posted his answer first, while I was typing mine... but I wanted to make the point about the deterministic primality test anyways.2012-04-21
  • 0
    Thx about your comment too.2012-04-21
4
  1. Very simple, but included for the sake of completeness: ($n$ is prime) if and only if ([$n\gt1$] and [{if $n$ divides $ab$} then {<$n$ divides $a$> or <$n$ divides $b$>}]).

  2. Elevated from a comment, since OP has indicated it's the kind of thing wanted: Giuga's conjecture states that $n$ is prime if and only if $1^{n-1}+2^{n-1}+\cdots+(n-1)^{n-1}\equiv-1\pmod n$.

  • 0
    This is a very interesting conjecture. Thx a lot Gerry. I just not embrace it because we don't know if it is a true statement. Thx a lot again.2012-04-21