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

$\endgroup$
16
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 20, 2012 at 23:02
  • 2
    $\begingroup$ 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... $\endgroup$
    – anon
    Apr 20, 2012 at 23:04
  • 7
    $\begingroup$ 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. $\endgroup$ Apr 20, 2012 at 23:49
  • 2
    $\begingroup$ Hopefully the question will be reopened. See the meta thread. $\endgroup$ Apr 21, 2012 at 0:18
  • 4
    $\begingroup$ @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). $\endgroup$ Apr 21, 2012 at 4:03

3 Answers 3

9
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ A litle huge, but very interesting. Thx. $\endgroup$
    – Fenri
    Apr 21, 2012 at 13:51
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Lovre Pesut posted his answer first, while I was typing mine... but I wanted to make the point about the deterministic primality test anyways. $\endgroup$ Apr 21, 2012 at 4:55
  • $\begingroup$ Thx about your comment too. $\endgroup$
    – Fenri
    Apr 21, 2012 at 13:51
4
$\begingroup$
  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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Fenri
    Apr 21, 2012 at 13:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .