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

  • 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
    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