Alternate definition of prime numbers

Question

The prime numbers are usually defined to be positive integers with exactly two distinct divisors—one and the number itself. There are plenty of variations on this definition.

Just out of sheer curiosity, is there some alternative definition of prime numbers? I mean something like: The $p$ is a prime number iff it can be expressed as (some expression), or iff some identity involving $p$ holds.

Does the knowledge that some number is a prime number imply that the other number $p$ must be a prime? In other words, the $p$ is a prime iff (some expression involving $p$) is a prime. For example, if $2^n - 1$ is prime then also the $n$ must be a prime. Can a similar property be used to define all prime numbers?

Unproven conjectures are also welcome.

Answer 1

There are many theorems of the form "such and such is true if and only if $p$ is prime." Every one of these theorms make a perfectly okay definition of the prime numbers, but they wouldn't motivate the definition at all; why would we want to study these objects that seem to be so arbitrary? Examples are Wilson's Theorem ($(p-1)!=-1$ in $\mathbb Z_p$ iff $p$ is prime), $\phi(p)=p-1$ if and only if $p$ is prime ($\phi$ is Euler's totient function), et cetera. I think the only example which does actually make a lot of sense as alternative definition of primes is this: $p$ is prime iff $p\mid ab$ implies $p\mid a$ or $p\mid b$. Indeed, in general rings, this is taken to be the definition of a prime element.

Answer 2

Wilson's theorem:

$p\in \mathbb N_{>1}$ is a prime number if and only if $$(p-1)!\equiv -1 \mod p$$

Alternatively

$p\in \mathbb N_{>1}$ is a prime number if and only if $$\pi(p)=\pi(p-1)+1$$ Where $\pi(n)$ is the prime counting function, i.e. the function counting the number of prime numbers less than or equal to some real number $n$.

Answer 3

See here : http://mathworld.wolfram.com/PrimeDiophantineEquations.html for a theoretical very powerful, but in practice unfortunately not very useful method to decide whether a given number is prime. $k+2$ is prime if and only if the given diophantine equation system is solvable with the corresponding $k$.