Definition:Prime Number

From ProofWiki
Jump to navigation Jump to search

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 {\sigma_0} p = 2$

where $\map {\sigma_0} p$ denotes the divisor count 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 $p$ 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 strictly 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

  • 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