# What are the properties of a prime number?

For instance, we know that odd numbers behave like:

$$x = 2y + 1 \quad\text{where}\quad x,y\in\mathbb Z$$

For even numbers:

$$a = 2b \quad\text{where}\quad a,b\in\mathbb Z$$

-
Clearly all primes other than $2$ must be of the form $2k + 1$ for some integer $k$ (else it is divisible by $2$). This is the same as saying all primes (other than 2) are congruent to 1 (mod 2). Similarly, all primes are congruent to 1 or 2 (mod 3). And all primes are congruent to 1 or 3 (mod 4)... etc. What exactly are you looking for? There is no 'general' form of a prime number, if that's what you're asking. –  Daniel Freedman Dec 29 '11 at 0:26
There is no comparably simple rule for prime numbers. But google the term "sieve of Eratosthenes". So much has been written about their properties that brilliant people spend their lives studying them without reading most of what's been published. In around 300 BC, Euclid proved that infinitely many of them exist. Maybe that's the most interesting result that can be presented at an elementary level. –  Michael Hardy Dec 29 '11 at 0:28
@Daniel, that answer my question. I am indeed looking for a "general" form. Almost like a formula with what I have. –  jak Dec 29 '11 at 0:32
There are polynomials in several variables that produce all of the prime numbers when the input variables are restricted to be nonnegative. See this for an example of a polynomial in $26$ variables that does the job. It is known that there is also such a polynomial in $10$ variables. –  alex.jordan Dec 29 '11 at 0:32
@jak, would "Is there a general formula for prime numbers?" be a more accurate title for your question? –  Rahul Dec 29 '11 at 10:01

$p \not = ab$ when $a,b > 1 \in \mathbb N$.

-

There's no nice, algebraic formula for primes; there are some examples at the Wikipedia article on the subject, but they are all ugly and impractical. Overall, the simplest way to define the primes is as numbers with only 2 divisors.

You can, of course, say things such as "all primes except 2 are odd numbers", which follows from the definition, but this doesn't tell you anything about which odd numbers are prime, and there are not clear patterns.

-
Re "the simplest way to define the primes is as numbers with only 2 divisors": AFAIK that's usual the definition of irreducible. AFAIK the usual definition of prime is that a number is prime iff its being a divisor of $ab$ implies it's a divisor of $a$ or of $b$. (That is, however, equivalent to primality.) –  msh210 Dec 29 '11 at 1:02
@msh210: Your "usual definition" leads to $1$ being a prime, which is not a commonly held meaning. –  Henning Makholm Dec 29 '11 at 1:12
@HenningMakholm, yes, I didn't state I was talking about integers $>1$. I also didn't state I was talking about integers at all. But I was, and I was. (More generally, a nonzero non-unit is prime if....) –  msh210 Dec 29 '11 at 1:14
@msh210: Any reference in support of the usual in the usual definition? –  Did Dec 29 '11 at 9:29
@DidierPiau, not really: it'd require a survey of all sources of definitions for the terms. However, I strongly suspect most elementary abstract algebra books agree on this. –  msh210 Dec 29 '11 at 17:42

Here's another property somewhat related to primes that I studied in the morning:

For any given integer $m$,there is no polynomial $p(x)$ with integer coefficients such that $p(n)$ is prime for all integers $n\ge m$.

by Titu Andreescu, Dorin Adrica and Zuming Feng.

Edit: I was browsing through the internet when I stumbled upon this book dedicated to primes.(I am unable to comment on it as I have no background in advanced maths)

-
I am sure there are many other properties and I guess they are too many to list. –  Eisen Dec 29 '11 at 8:17

To add to the fact there is no general formula for primes, it may help to trace back history of prime number. Euclid defined primes in Elements, Book VII, Definition 11 as:

A prime number is that which is measured by a unit alone.

which in turn relies on definitions of number and unit.

Definition 1 from the same book:

A unit is that by virtue of which each of the things that exist is called one.

Definition 2:

A number is a multitude composed of units.

As far as formal definition, Metamath Proof Explorer defines it as such: primes.

As a sidenote, although it is not a property of prime numbers, Goldbach's conjecture states that:

Every even integer greater than 2 can be expressed as the sum of two primes.

Edit: There are forms of primes. Here is the entire list:

https://en.wikipedia.org/wiki/List_of_prime_numbers

-

Wilson's theorem: a natural number $n > 1$ is a prime number iff $(n-1)!\ \equiv\ -1 \pmod n$

-

A formula might be created using the$\mod(\cdot)$ function.

$\mod({\rm PrimeNumber}/n) > 0$ for all $n \in \mathbb{N}$ and $n > 1$ other than PrimeNumber

-

In a way there are more prime numbers than there are a square numbers, this is not an exact statement but the sum over all prime numbers diverges where as the sum over square of all numbers converges.

-

Since people are talking about "formulas for primes" and someone mentioned polynomials, it's amusing to mention this fact: There actually is a 4th- (if I recall correctly) -degree polynomial in 14 (if I recall correctly) variables, with integer coefficients---let us call it $f(p,x_1,\ldots,x_{13})$---such that $$p\text{ is prime if and only if }\exists x_1\ \cdots\ \exists x_{13}\ f(p,x_1,\ldots,x_{13})=0.$$ (Or maybe I should have "$14$" where "$13$" appears?)

The polynomial, in all its splendor, is too long to write in this margin. But if you read about Hilbert's 10th problem you'll probably come across it.

Later note: That such a polynomial exists is what is expressed by saying that the set of all prime numbers is a "Diophantine set".

-
For reference: The table displayed in this question (taken from Ribenboim's The New Book of Prime Number Records) lists a few known facts on such polynomials. In particular, there are a polynomial in $12$ variables of degree $13697$ and a (not explicitly written) polynomial in $42$ variables of degree $5$ representing the primes. –  t.b. Dec 30 '11 at 5:18

I strongly recommend that you take a look at Zagier's paper on first 50 million Prime Numbers to learn about some other characterizations of the notion of "prime number".

As to congruences that characterize primality, Wilson's theorem provides you with one of the most-well known (as the fact that it's already been mentioned above/below testifies). Nonetheless, there is an interesting near-miss by M. V. Subbarao. You can read about this in one of those volumes by Ross Honsberger. Furthermore, if you are curious enough you may want to call on Scott Kominers' homepage: there is a generalization of the said criterion by Subbarao in a note of him that was recently published in INTEGERS.

Here you have some other equivalences of the definition of prime number:

A. $p$ is a positive prime number iff $\phi(p) = p-1$.

B. $p$ is a positive prime number iff $p$ is the least factor $>1$ of some natural number.