Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

But what about prime numbers?

share|improve this question
3  
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
4  
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
2  
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
1  
@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

12 Answers 12

up vote 20 down vote accepted

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

share|improve this answer

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.

share|improve this answer
1  
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
1  
@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
2  
@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$.

References: 1) 104 Number Theory Problems: From the Training of the USA IMO Team

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)

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

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

I strongly recommend that you take a look at Zagier's paper on the 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$.

When I told Prof. Luca about this finding of mine, he generously told me about Lehmer's totient problem.

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

C. Later...

share|improve this answer
    
I was unable to find such a paper mentioned at Kominers’ site. –  Brian M. Scott Feb 24 '12 at 10:25

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

share|improve this answer

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".

share|improve this answer
2  
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

$ x= \left\{ \begin{array}{lr} Prime & : \left| \prod _{k=2}^{x-1}\sin \left( {\frac {x\pi }{k}} \right) kx \right| > 0\\ Composite & : \left| \prod _{k=2}^{x-1}\sin \left( {\frac {x\pi }{k}} \right) kx \right| = 0 \end{array} \right. $ s.t. $x \in \mathbb{N}$

This is a function I made, it works like the Sieve of Eratosthenes from which I derived it.

share|improve this answer
    
Oh also I came up with a nice Prime counting function utilizing this function. $ Pi(n)= \sum _{x=2}^{n} \left\{ \begin{array}{lr} 1 & : \left| \prod _{k=2}^{x-1}\sin \left( {\frac {x\pi }{k}} \right) kx \right| > 0\\ 0 & : \left| \prod _{k=2}^{x-1}\sin \left( {\frac {x\pi }{k}} \right) kx \right| = 0 \end{array} \right. $ Where Pi(n)==number of primes up till n –  Numoru Jul 17 at 7:57

All the primes are of the form $6k\pm 1,k\in \mathbb{N}$ (but, of course, not all the numbers of this form are prime):

Numbers of the form $6k+2$ or $6k+4$ are even while numbers of the form $6k+3$ are clarly divisible by 3, this leaves only numbers of the form $6k+1$ or $6k+5$ as potential primes

share|improve this answer

Some elementary primality tests may answer your question regarding the properties of prime numbers. See my question on 'Lehmer-Totient-Problem' for more reference. Also you can use the following theorem as a tool for primality test. The theorem sates that- "An integer $n$ is a prime if and only if $n|\phi(n)!+1$."

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.