# Definition:Prime Number

## Definition

### Definition 1

A **prime number** $p$ is a positive integer that has exactly two divisors which are themselves positive integers.

### Definition 2

Let $p$ be a positive integer.

Then $p$ is a prime number if and only if $p$ has exactly four integral divisors: $\pm 1$ and $\pm p$.

### Definition 3

Let $p$ be a positive integer.

Then $p$ is a prime number if and only if:

- $\map \tau p = 2$

where $\map \tau p$ denotes the divisor counting function of $p$.

### Definition 4

A **prime number** $p$ is an integer greater than $1$ that has no positive integer divisors other than $1$ and $p$.

### Definition 5

A **prime number** $p$ is an integer greater than $1$ that has no (positive) divisors less than itself other than $1$.

### Definition 6

Let $p \in \N$ be an integer such that $p \ne 0$ and $p \ne \pm 1$.

Then $p$ is a **prime number** if and only if

- $\forall a, b \in \Z: p \divides a b \implies p \divides a$ or $p \divides b$

where $\divides$ means **is a divisor of**.

### Definition 7

A **prime number** $p$ is an integer greater than $1$ which cannot be written in the form:

- $p = a b$

where $a$ and $b$ are both positive integers less than $p$.

### Euclid's Definition

In the words of Euclid:

*A***prime number**is that which is measured by an unit alone.

(*The Elements*: Book $\text{VII}$: Definition $11$)

## Sequence of Prime Numbers

The sequence of prime numbers starts:

- $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, \ldots$

This sequence is A000040 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

## Odd Prime

Every even integer is divisible by $2$ (because this is the definition of **even**).

Therefore, apart from $2$ itself, all primes are odd.

So, referring to an **odd prime** is a convenient way of specifying that a number is a prime number, but not equal to $2$.

## Composite

A **composite number** $c$ is a positive integer that has more than two positive divisors.

That is, an integer greater than $1$ which is not prime is defined as composite.

## Extension to Negative Numbers

The concept of primality can be applied to negative numbers as follows:

A **negative prime** is an integer of the form $-p$ where $p$ is a (positive) prime number.

## Notation

Some authors use the symbol $\Bbb P$ to denote the set of all primes. This notation is not standard (but perhaps it ought to be).

The letter $p$ is often used to denote a general element of $\Bbb P$, in the same way that $n$ is often used to denote a general element of $\N$.

1978: John S. Rose: *A Course on Group Theory* uses $\varpi$ (a variant of $\pi$, despite its appearance) to denote a general set of primes.

## Also defined as

Some treatments of number theory define a **prime** as being either positive or negative, by specifying that a **prime number** is an integer with exactly $4$ integer divisors.

By this definition, a composite number is defined as an integer (positive or negative) which is not prime and not equal to $\pm 1$.

There are advantages to this approach, because then special provision does not need to be made for negative integers.

Some sources implement this notion by introducing the concept of a **prime integer**.

## Also see

- Definition:Titanic Prime: a prime number with $1000$ digits or more
- Definition:Gigantic Prime: a prime number with $10 \, 000$ digits or more

- Results about
**prime numbers**can be found here.

### Generalizations

## Historical Note

The concept of classifying numbers as **prime** or **composite** appears to have originated with the Pythagoreans.

The seemingly random and irregular distribution of the primes has challenged mathematicians since ancient times.

*Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate.*- -- Leonhard Paul Euler, $1751$

## Sources

- 1978: John S. Rose:
*A Course on Group Theory*... (previous) ... (next): $0$: Some Conventions and some Basic Facts - 1989: Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*... (previous) ... (next): Entry:**prime**:**1 b.** - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction