Prime number
Builds on Divisibility
Definition
A prime number is a natural number such that and the only positive divisors of are and .
Remarks
The first prime numbers are . The number is the only even prime. The number is not prime by this definition. This choice makes the prime factorization of each integer unique. A natural number that is not prime is a composite number. An equivalent property for is Euclid's lemma: if , then or .
Reading path
To understand this page from the ground up, read these 2 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Divisibility definition
- Prime number definition
Where this leads
95 pages build on this one.
- Square-free integer
- −1 is a square modulo p if and only if p is not 3 modulo 4
- Divergence of the sum of the reciprocals of the primes
- Hensel's lemma
- Legendre symbol
- Legendre's formula
- Existence of prime factorization
- Euclid's theorem
- Fermat pseudoprime
- Gauss's lemma on quadratic residues
- Wilson's theorem
- Fermat's theorem on sums of two squares
- Sum of two squares theorem
- P-adic valuation
- Existence of primitive roots modulo a prime
- Euclid's lemma
- Groups of prime order are cyclic
- Mersenne prime
- Converse of Wilson's theorem
- If 2^p − 1 is prime then p is prime
- Möbius inversion formula
- Every integer is a square times a square-free integer
- Number of prime factors counted with multiplicity
- Fundamental theorem of arithmetic
- P-adic valuation of a product
- Law of quadratic reciprocity
- von Mangoldt function
- Liouville function
- Prime factorization
- The Möbius function is the inverse of the constant function 1
- Totient of a prime power
- Fermat's little theorem in the form a^p = a
- Euler product formula
- Möbius function
- Primitive root theorem
- A composite number has a prime factor at most its square root
- Primality test
- Prime number theorem
- Bertrand's postulate
- Dirichlet's theorem on arithmetic progressions
- Totient of a prime
- Lifting-the-exponent lemma
- Fermat's little theorem
- Euler's criterion
- Irrationality of square roots of non-squares
- Composite number
- Fermat prime
- Multiplicativity of the Legendre symbol
- First supplement to quadratic reciprocity
- Integers modulo a prime form a field
- Lucas's theorem
- Smallest prime factor
- Existence of a prime divisor
- Miller–Rabin primality test
- Infinitely many primes congruent to 1 modulo n
- Carmichael number
- Multiplicativity of the Möbius function
- Kummer's theorem
- If 2^n + 1 is prime then n is a power of 2
- Euclid–Euler theorem
- A prime is a Gaussian prime if and only if it is 3 modulo 4
- Jacobi symbol
- Prime-counting function
- Eisenstein's lemma
- The order modulo p divides p − 1
- Number of distinct prime factors
- Quadratic reciprocity for the Jacobi symbol
- Second supplement to quadratic reciprocity
- Lambert series
- Cohn's irreducibility criterion
- Galois group of a prime degree polynomial with two nonreal roots
- Norm residue isomorphism theorem
- Artin reciprocity law
- Euclid's Elements
- Divisibility poset
- Bombieri–Vinogradov theorem
- Euler product for multiplicative functions
- Vinogradov's theorem
- Non-vanishing of the zeta function on the line Re s = 1
- Cubic reciprocity
- Proof that groups of prime order are cyclic
- Hilbert class field
- Wiener–Ikehara theorem
- Ax–Kochen theorem
- Hasse–Minkowski theorem
- Hardy–Littlewood circle method
- Quartic reciprocity
- Chen's theorem
- Chebotarev's density theorem
- Siegel–Walfisz theorem
- Cohomological dimension of a field
- AKS primality test
- Bounded gaps between primes
- Integer factorization
- Lambert summation
Further reading
- Web https://en.wikipedia.org/wiki/Prime_number, Definition and examples
About this page
| Tag | 0SN0MAEKYX |
|---|---|
| URI | m2://0SN0MAEKYX |
| Aliases | prime |
| Kind | definition |
| Writing | W1 stated |
| MSC | 11A41 |
| Defines | Prime number |
| Uses | Divisibility |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Square-free integer
- −1 is a square modulo p if and only if p is not 3 modulo 4
- Divergence of the sum of the reciprocals of the primes
- Hensel's lemma
- Legendre symbol
- Euclid's theorem
- Wilson's theorem
- Fermat's theorem on sums of two squares
- P-adic valuation
- Existence of primitive roots modulo a prime
- Euclid's lemma
- Mersenne prime
- Converse of Wilson's theorem
- If 2^p − 1 is prime then p is prime
- von Mangoldt function
- Prime factorization
- Totient of a prime power
- Euler product formula
- Primality test
- Bertrand's postulate
- Dirichlet's theorem on arithmetic progressions
- Totient of a prime
- Fermat's little theorem
- Composite number
- Fermat prime
- Integers modulo a prime form a field
- Lucas's theorem
- Smallest prime factor
- Existence of a prime divisor
- Infinitely many primes congruent to 1 modulo n
- If 2^n + 1 is prime then n is a power of 2
- A prime is a Gaussian prime if and only if it is 3 modulo 4
- Prime-counting function
- Number of distinct prime factors
- Cohn's irreducibility criterion
- Galois group of a prime degree polynomial with two nonreal roots
- Norm residue isomorphism theorem
- Euler product for multiplicative functions
- Proof that groups of prime order are cyclic
- Ax–Kochen theorem
- Cohomological dimension of a field