Prime number

Prime number
Tag	`0SN0MAEKYX`
URI	`m2://0SN0MAEKYX`
Aliases	`prime`
Kind	definition
Writing	W1 stated
MSC	11A41
Defines	Prime number
Uses	Divisibility

Markdown · JSON · Edit

Definition

A prime number is a natural number $p$ such that $p > 1$ and the only positive divisors of $p$ are $1$ and $p$ .

Remarks

The first prime numbers are $2, 3, 5, 7, 11, 13$ . The number $2$ is the only even prime. The number $1$ is not prime by this definition. This choice makes the prime factorization of each integer unique. A natural number $n > 1$ that is not prime is a composite number. An equivalent property for $p > 1$ is Euclid's lemma: if $p \mid a b$ , then $p \mid a$ or $p \mid b$ .

Explanations

L1 human

A prime number is a number greater than $1$ that you cannot split as a product of two smaller natural numbers. For example, $7$ is prime, but $6 = 2 \cdot 3$ is not. The primes are the building blocks of the natural numbers under multiplication.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 2 nodes in this order. The foundations come first, and the list ends with this node.

Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.

no evidence level

Divisibility definition
Prime number definition

What depends on this

67 nodes use this node, directly or through other nodes.

Square-free integer 004JW7A2N5
−1 is a square modulo p if and only if p is not 3 modulo 4 00DW862T78
Divergence of the sum of the reciprocals of the primes 00RA98X2CP
Hensel's lemma 010QVB71T2
Legendre symbol 01J8AMV9RS
Legendre's formula 01WPV9PHN7
Existence of prime factorization 020K0X7HVR
Euclid's theorem 0292EPPPT0
Fermat pseudoprime 02M2K4QH9P
Gauss's lemma on quadratic residues 037ACYXB5Z
Wilson's theorem 03KGGKTB2E
Fermat's theorem on sums of two squares 043B3ENSTY
Sum of two squares theorem 04NPWJMA6H
P-adic valuation 04VCPS30ZE
Existence of primitive roots modulo a prime 04XGKK8WQW
Euclid's lemma 051VYKA1EX
Mersenne prime 06GPJF9V7M
Converse of Wilson's theorem 06WRV8HFDY
If 2^p − 1 is prime then p is prime 07MMWAXMYD
Möbius inversion formula 07Q4TBTFVB
Every integer is a square times a square-free integer 080Q3RPKY6
Number of prime factors counted with multiplicity 08420828EY
Fundamental theorem of arithmetic 084HH1NDCB
P-adic valuation of a product 0850JJMJYZ
Law of quadratic reciprocity 085MJS6907
von Mangoldt function 087EMZTHWN
Liouville function 08RQAPXF1T
Prime factorization 0AEKDFCYFA
The Möbius function is the inverse of the constant function 1 0ASC73QEQT
Totient of a prime power 0AVY8HKBGD
Fermat's little theorem in the form a^p = a 0BMXWXDVJZ
Euler product formula 0C3PN4075R
Möbius function 0C8QENHYZW
Primitive root theorem 0E0DNQK22P
A composite number has a prime factor at most its square root 0EB6BBMQMC
Primality test 0EGJZHZ02C
Prime number theorem 0EHBY5Y84N
Bertrand's postulate 0FJTGZA4GS
Dirichlet's theorem on arithmetic progressions 0GNVN3CA2P
Totient of a prime 0HY1MXMEN9
Lifting-the-exponent lemma 0JYF6PTKEW
Fermat's little theorem 0M25PRN3WQ
Euler's criterion 0M7DEDKSYB
Irrationality of square roots of non-squares 0N10YRNNWV
Composite number 0N3ADXHNTQ
Fermat prime 0N9E4G2P97
Multiplicativity of the Legendre symbol 0NW1JP7TBR
First supplement to quadratic reciprocity 0PHBS78HKT
Integers modulo a prime form a field 0R8YXRC9AJ
Lucas's theorem 0RY4GGMEQG
Smallest prime factor 0S2SYHTWPY
Existence of a prime divisor 0SPBEDVNW1
Miller–Rabin primality test 0SZCSYHW60
Infinitely many primes congruent to 1 modulo n 0T1BSD7H3M
Carmichael number 0TA7WT68RK
Multiplicativity of the Möbius function 0VB9G5B034
Kummer's theorem 0VBWK9XYDG
If 2^n + 1 is prime then n is a power of 2 0VN4H8M12X
Euclid–Euler theorem 0WETJCKNRG
A prime is a Gaussian prime if and only if it is 3 modulo 4 0WMJSEFYFE
Jacobi symbol 0XDB5AW7M1
Prime-counting function 0XRJB5SSNE
Eisenstein's lemma 0XSDBCP4RZ
The order modulo p divides p − 1 0Y4B7P0GS8
Number of distinct prime factors 0YVVXT3A0B
Quadratic reciprocity for the Jacobi symbol 0YY06KP3ZQ
Second supplement to quadratic reciprocity 0ZXW95S44M

Sources

Web https://en.wikipedia.org/wiki/Prime_number, Definition and examples

What links here

Used by

Square-free integer 004JW7A2N5
−1 is a square modulo p if and only if p is not 3 modulo 4 00DW862T78
Divergence of the sum of the reciprocals of the primes 00RA98X2CP
Hensel's lemma 010QVB71T2
Legendre symbol 01J8AMV9RS
Euclid's theorem 0292EPPPT0
Wilson's theorem 03KGGKTB2E
Fermat's theorem on sums of two squares 043B3ENSTY
P-adic valuation 04VCPS30ZE
Existence of primitive roots modulo a prime 04XGKK8WQW
Euclid's lemma 051VYKA1EX
Mersenne prime 06GPJF9V7M
Converse of Wilson's theorem 06WRV8HFDY
If 2^p − 1 is prime then p is prime 07MMWAXMYD
von Mangoldt function 087EMZTHWN
Prime factorization 0AEKDFCYFA
Totient of a prime power 0AVY8HKBGD
Euler product formula 0C3PN4075R
Primality test 0EGJZHZ02C
Bertrand's postulate 0FJTGZA4GS
Dirichlet's theorem on arithmetic progressions 0GNVN3CA2P
Totient of a prime 0HY1MXMEN9
Fermat's little theorem 0M25PRN3WQ
Composite number 0N3ADXHNTQ
Fermat prime 0N9E4G2P97
Integers modulo a prime form a field 0R8YXRC9AJ
Lucas's theorem 0RY4GGMEQG
Smallest prime factor 0S2SYHTWPY
Existence of a prime divisor 0SPBEDVNW1
Infinitely many primes congruent to 1 modulo n 0T1BSD7H3M
If 2^n + 1 is prime then n is a power of 2 0VN4H8M12X
A prime is a Gaussian prime if and only if it is 3 modulo 4 0WMJSEFYFE
Prime-counting function 0XRJB5SSNE
Number of distinct prime factors 0YVVXT3A0B