nyuuzyou/wikis huggingface dataset:
Prime Number Theorem/Historical Note

== Historical Note on Prime Number Theorem ==
The Prime Number Theorem (PNT) was first conjectured by when he was $14$ or $15$, but he was never able to prove it.
He also posited the suggestion that it could be approximated by the Eulerian logarithmic integral $\ds \map \Li x = \int_2^x \frac {\d t} {\map \ln t}$.
It took another century before a proof was found.
Legendre conjectured in $1796$ that there exists a constant $B$ such that $\map \pi n$ satisfies:
:$\ds \lim_{n \mathop \to \infty} \map \pi n - \frac n {\map \ln n} = B$
If such a number $B$ exists, then this implies the Prime Number Theorem.
Legendre's guess for $B$ was about $1 \cdotp 08366$, now a historical curiosity known as Legendre's constant.
 was the first one to provide any support for 's conjecture when he proved in $1850$ that:
:$\dfrac 7 8 < \dfrac {\map \pi x} {x / \ln x} < \dfrac 9 8$
for all sufficiently large $x$.
He also proved that if the limit of the expression in question does exist, then its value must be $1$.
In $1891$, and showed that for sufficiently large $x$, there exists at least one prime number $p$ satisfying:
:$x < p < \paren {1 + \alpha} x$
where $\alpha = 0 \cdotp 092 \ldots$
Again, since the Prime Number Theorem implies that the above inequality is true for all $\alpha > 0$ for sufficiently large $x$, this constant is also of historical interest only.
Since then, several complete proofs have been discovered.
The first proofs were given independently by and in $1896$.
They relied on the theory of functions of a complex variable.
The original theorem of used in that proof is given on as Ingham's Theorem on Convergent Dirichlet Series, which is used in Order of Möbius Function, an essential part of the above proof.
 and would later give an elementary proof of the PNT, in $1948$.
Their proof did not make use of any analytic function theory, and relied entirely on basic properties of logarithms.
Dispute over whether to publish their results jointly or separately created a life-long feud between the two mathematicians. 
== Sources ==
* : $-1$ and $i$
* 
* : Chapter $\text {A}.25$: Gauss ()
* : Chapter $\text {A}.31$: Chebyshev ()
* : Chapter $\text {A}.32$: Riemann (): Footnote $6$
* : Chapter $\text {B}.16$: The Sequence of Primes
* : $-1$ and $i$
* 
* 
* 
* 
* 
Category:Historical Notes
Prime Number Theorem/Interpretation

== Interpretation of Prime Number Theorem ==
The Prime Number Theorem can also be rendered as:
:$\ds \lim_{x \mathop \to \infty} \dfrac {\map \pi x / x} {1 / \ln x} = 1$
where $\dfrac {\map \pi n} n$ can be interpreted as the probability that a number chosen at random will be prime.
Thus, for large $n$, that probability is approximately equal to $\dfrac 1 {\ln n}$.
== Sources ==
* : Chapter $\text {B}.16$: The Sequence of Primes
Category:Prime Number Theorem
Prime Number Theorem in Eulerian Logarithmic Integral Form

== Theorem ==
The Prime Number Theorem is equivalent to:
:$\ds \lim_{x \mathop \to \infty} \frac {\map \pi x} {\map \Li x} = 1$
where:
:$\map \pi x$ is the prime-counting function
:$\map \Li x$ is the Eulerian logarithmic integral:
::$\ds \map \Li x := \int_2^x \dfrac {\d t} {\ln t}$
== Proof ==
Using Integration by Parts:
We have that $\dfrac 1 {\paren {\ln t}^2}$ is positive and decreasing for $t > 1$.
Let $x \ge 4$.
Then:
Then:
Then:
== Sources ==
* : Chapter $\text {B}.16$: The Sequence of Primes
Category:Prime Number Theorem
Category:Analytic Number Theory
Prime Number divides Fibonacci Number

== Theorem ==
For $n \in \Z$, let $F_n$ denote the $n$th Fibonacci number.
Let $p$ be a prime number.
Then:
:$p \equiv \pm 1 \pmod 5 \implies p \divides F_{p - 1}$
:$p \equiv \pm 2 \pmod 5 \implies p \divides F_{p + 1}$
where $\divides$ denotes divisibility.
Thus in all cases, except where $p = 5$ itself:
:$p \divides F_{p \pm 1}$
== Proof ==
It is worth noting the one case where $p = 5$:
:$5 \divides F_5 = 5$
== Sources ==
* : $5$
* : $5$
Category:Fibonacci Numbers
Category:Divisors
Prime Number divides Infinite Number of Fibonacci Numbers

== Theorem ==
Let $p$ be a prime number.
Then there exist an infinite number of Fibonacci numbers which are divisible by $p$.
== Proof ==
From Prime Number divides Fibonacci Number, either $F_{p - 1}$ or $F_{p + 1}$ is divisible by $p$.
Thus:
== Sources ==
* : $5$
* : $5$
Category:Fibonacci Numbers
Category:Divisors
Prime Number has 4 Integral Divisors

== Theorem ==
Let $p$ be an integer.
Then $p$ is a prime number $p$ has exactly four integral divisors: $1, -1, p, -p$.
== Proof ==
=== Necessary Condition ===
Let $p$ be a prime number from the definition that $p$ has exactly $2$ divisors which are positive integers.
From One Divides all Integers and Integer Divides Itself those positive integers are $1$ and $p$.
Also, we have $-1 \divides p$ and $-p \divides p$ from One Divides all Integers and Integer Divides its Negative.
:
: $\exists x < 0: x \divides p$
where $x \ne -1$ and $x \ne -p$.
Then:
: $\size x \divides x \divides p$
and so $\size x$ is therefore a positive integer other than $1$ and $p$ that divides $p$.
This is a contradiction of the condition for $p$ to be prime.
So $-1$ and $-p$ are the only negative integers that divide $p$.
It follows that $p$ has exactly those four divisors.
=== Sufficient Condition ===
Suppose $p$ has the divisors $1, -1, p, -p$.
It follows that $1$ and $p$ are the only positive integers that divide $p$.
Thus $p$ has exactly two divisors which are positive integers.
== Also see ==
* Definition:Negative Prime
Category:Prime Numbers
Prime Number iff Generates Principal Maximal Ideal

== Theorem ==
Let $\Z_{>0}$ be the set of strictly positive integers.
Let $p \in \Z_{>0}$.
Let $\ideal p$ be the principal ideal of $\Z$ generated by $p$. 
Then $p$ is prime $\ideal p$ is a maximal ideal of $\Z$.
== Proof ==
First, note that $\Z$ is a principal ideal domain, so all ideals are principal.
=== Sufficient Condition ===
Suppose $p$ is prime.
From Integer Divisor is Equivalent to Subset of Ideal, $m \divides n \iff \ideal n \subseteq \ideal m$.
But as $p$ is prime, the only divisors of $p$ are $1$ and $p$ itself.
By Natural Numbers Set Equivalent to Ideals of Integers, it follows that if $p$ is prime, then $\ideal p$ must be a maximal ideal.
=== Necessary Condition ===
Let $p \in \Z_{>0}$ such that $\ideal p$ is maximal.
Let $q \in \Z_{>0}$ be a divisor of $p$.
Then:
Thus $p$ is prime.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $24$. The Division Algorithm: Theorem $24.5$
* : Chapter $5$: Rings: $\S 23$. Maximal Ideals: Example $41$
* : $\S 1.8$ Algebraic properties of $p$-adic integers
Category:Ideal Theory
Prime Number is Deficient/Proof 2

== Theorem ==
== Proof ==
Let $p$ be a prime number.
From Divisor Sum of Prime Number:
:$\map {\sigma_1} p = p + 1$
and so:
:$\dfrac {\map {\sigma_1} p} p = \dfrac {p + 1} p = 1 + \dfrac 1 p$
As $p > 1$ it follows that $\dfrac 1 p < 1$.
Hence:
:$\dfrac {\map {\sigma_1} p} p < 2$
The result follows by definition of deficient.
Category:Prime Number is Deficient
Prime Numbers Composed of Strings of Consecutive Ascending Digits

== Sequence ==
The sequence of prime numbers consisting of strings of consecutive ascending digits (allowing $0$ to follow $9$) begins:
:$2, 3, 5, 7, 23, 67, 89, 4567, 78 \, 901, 678 \, 901, 23 \, 456 \, 789, 45 \, 678 \, 901, $
::$9 \, 012 \, 345 \, 678 \, 901, 789 \, 012 \, 345 \, 678 \, 901, $
::$56 \, 789 \, 012 \, 345 \, 678 \, 901 \, 234 \, 567 \, 890 \, 123, $
::$90 \, 123 \, 456 \, 789 \, 012 \, 345 \, 678 \, 901 \, 234 \, 567, $
::$678 \, 901 \, 234 \, 567 \, 890 \, 123 \, 456 \, 789 \, 012 \, 345 \, 678 \, 901$
It is not known whether there exist any more.
== Sources ==
* 
* : $23,456,789$
Category:Prime Numbers
Prime Numbers Embedded in Digits of Pi

== Theorem ==
The sequence of prime numbers that can be found starting from the beginning of the decimal expansion of $\pi$ (pi) begins:
:$3, 31, 314 \, 159, 31 \, 415 \, 926 \, 535 \, 897 \, 932 \, 384 \, 626 \, 433 \, 832 \, 795 \, 028 \, 841, \ldots$
== Proof ==
By inspection.
== Sources ==
* : $314,159$
Category:Pi
Category:Prime Numbers
Prime Numbers which Divide Sum of All Lesser Primes

== Theorem ==
The following sequence of prime numbers has the property that each is a divisor of the sum of all primes smaller than them:
:$2, 5, 71, 369 \, 119, 415 \, 074 \, 643$
As of time of writing (April $2020$), no others are known.
== Proof ==
Verified by calculation.
== Examples ==
== Sources ==
* 
* 
* : $71$
* : $369,119$
* : $71$
* : $369,119$
Category:Prime Numbers
Prime Numbers which Divide Sum of All Lesser Primes/Mistake/First Edition

== Source Work ==
:
:The Dictionary
::$71$
== Mistake ==
:The numbers $5$, $71$ and $369119$ are the only known numbers less than $2,000,000$ that divide the sum of the primes less than them.
== Correction ==
There are three problems here:
:$(1): \quad 2$ is missing.
:$(2): \quad$ At the time of writing, a further term in this sequence had been discovered, that is, $415 \, 074 \, 643$, but appears to have failed to notice it.
Both the above issues were corrected for .
:$(3): \quad$ Note that the sentence itself should have read:
::The numbers $5$, $71$ and $369119$ are the only known prime numbers less than $2,000,000$ that divide the sum of the primes less than them.
:(emphasis added)
== Sources ==
* : $71$
Category:Mistakes/Curious and Interesting Numbers
Prime Numbers which Divide Sum of All Lesser Primes/Mistake/Second Edition

== Source Work ==
:
:The Dictionary
::$71$
== Mistake ==
:The numbers $2$, $5$, $71$, $369,119$ and $415,074,643$ are the only known numbers that divide the sum of all the primes less than them.
== Correction ==
This should read:
:The numbers $2$, $5$, $71$, $369,119$ and $415,074,643$ are the only known prime numbers that divide the sum of all the primes less than them.
(emphasis added)
== Sources ==
* : $71$
Category:Mistakes/Curious and Interesting Numbers
Prime Power Group has Non-Trivial Proper Normal Subgroup

== Theorem ==
Let $G$ be a group, whose identity is $e$, such that $\order G = p^n: n > 1, p \in \mathbb P$.
Then $G$ has a proper normal subgroup which is non-trivial.
== Proof ==
From Center of Group is Normal Subgroup, $\map Z G \lhd G$.
By Center of Group of Prime Power Order is Non-Trivial, $\map Z G$ is non-trivial.
If $\map Z G$ is a proper subgroup, the proof is finished.
Otherwise, $\map Z G = G$.
Then $G$ is abelian by definition.
However, then any $a \in G: a \ne e$ generates a non-trivial normal subgroup $\gen a$, as Subgroup of Abelian Group is Normal.
If $\order a = \order {\gen a} < \order G$, the proof is complete.
Otherwise:
:$\order a = \order G = p^n$
Then $\order {a^p} = p^{n - 1}$ from Subgroup of Finite Cyclic Group is Determined by Order, so $a^p$ generates that non-trivial normal subgroup.
== Sources ==
* : Conjugacy, Normal Subgroups, and Quotient Groups: $\S 52$ Lemma $2$
Category:Normal Subgroups
Category:P-Groups
Prime Power Mapping on Galois Field is Automorphism

== Theorem ==
Let $\GF$ be a Galois field whose zero is $0_\GF$ and whose characteristic is $p$.
Let $\sigma: \GF \to \GF$ be defined as:
:$\forall x \in \GF: \map \sigma x = x^p$
Then $\sigma$ is an automorphism of $\GF$.
== Proof ==
Let $x, y \in \GF$.
Then:
and:
Thus it has been demonstrated that $\sigma$ is a homomorphism.
Then we have:
From Kernel is Trivial iff Monomorphism, $\sigma$ is a monomorphism.
That is, $\sigma$ is an injection.
Then from Injection from Finite Set to Itself is Surjection, $\sigma$ is a surjection.
Thus $\sigma$ is a bijective homomorphism to itself.
The result follows by definition of automorphism.
== Sources ==
* : Chapter $3$: Field Theory: Definition and Examples of Field Structure: $\S 89 \gamma$
* : Chapter $9$: Rings: Exercise $15$
Category:Galois Fields
Category:Field Isomorphisms
Prime Power of Sum Modulo Prime

== Theorem ==
Let $p$ be a prime number.
Then:
:$\forall n \in \N_{> 0}: \paren {a + b}^{p^n} \equiv a^{p^n} + b^{p^n} \pmod p$
=== Corollary ===
== Proof ==
Proof by induction:
For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:
:$\paren {a + b}^{p^n} \equiv a^{p^n} + b^{p^n} \pmod p$
=== Basis for the Induction ===
First from Power of Sum Modulo Prime we have that $\map P 1$ is true:
:$\paren {a + b}^p \equiv a^p + b^p \pmod p$
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\paren {a + b}^{p^k} \equiv a^{p^k} + b^{p^k} \pmod p$
Then we need to show:
:$\paren {a + b}^{p^{k + 1} } \equiv a^{p^{k + 1} } + b^{p^{k + 1} } \pmod p$
=== Induction Step ===
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \N_{> 0}: \paren {a + b}^{p^n} \equiv a^{p^n} + b^{p^n} \pmod p$
== Also see ==
* Power of Sum Modulo Prime
Category:Number Theory
Category:Combinatorics
Category:Prime Numbers
Category:Proofs by Induction
Prime Power of Sum Modulo Prime/Corollary

== Corollary to Prime Power of Sum Modulo Prime==
Let $p$ be a prime number.
Then:
:$\forall n \in \N_{> 0}: \paren {1 + b}^{p^n} \equiv 1 + b^{p^n} \pmod p$
== Proof ==
Follows immediately from Prime Power of Sum Modulo Prime by putting $a = 1$.
== Sources ==
* : $\S 2.6$. Algebra of congruences: Example $42 \ (4)$
Category:Number Theory
Category:Combinatorics
Category:Prime Numbers
Prime Powers Differing by One

== Theorem ==
$8$ and $9$ are the only powers of prime numbers which differ by exactly $1$:
:$2^3 + 1 = 3^2$
== Proof ==
This is a direct consequence of 1 plus Perfect Power is not Prime Power except for 9.
== Sources ==
* : $8$
* : $9$
* : $8$
* : $9$
Category:8
Category:9
Category:Powers
Prime Repdigit Number is Repunit

== Theorem ==
Let $b \in \Z_{>0}$ be an integer greater than $1$.
Let $n \in \Z$ expressed in base $b$ be a repdigit number with more than $1$ digit.
Let $n$ be prime.
Then $n$ is a repunit (in base $b$).
== Proof ==
Let $n$ be a repdigit number with $k$ digits.
Then by the Basis Representation Theorem:
:$\ds n = \sum_{j \mathop = 0}^k m b^j$
for some $m$ such that $1 \le m < b$.
Let $m \ge 2$.
Then:
:$\ds n = m \sum_{j \mathop = 0}^k b^j$
and so has $m$ as a divisor.
Hence $n$ is not prime.
The result follows by the Rule of Transposition.
Category:Repdigit Numbers
Category:Repunits
Category:Repunit Primes
Prime Sierpiński Numbers of the First Kind

== Open Question ==
The only known prime Sierpiński numbers of the first kind are:
It is an open question as to whether there are any more.
== Progress ==
Let $S_n$ be the $n$th Sierpiński number of the first kind:
:$S_n = n^n + 1$
From Form of Prime Sierpiński Number of the First Kind, it is known that if $S_n$ is prime, then:
:$n = 2^{2^k}$
for some integer $k$.
Thus
Thus a prime $S_n$ is a Fermat number $F_m$ where $m = k + 2^k$.
The sequence of $m$ begins:
:$1, 3, 6, 11, 20, 37, 70, 135, 264, 521, 1034, 2059, 4108, 8205, \ldots$
Thus it remains to investigate the following Sierpiński numbers of the first kind for primality:
:
$k$ 	$m = k + 2^k$	$n = 2^{2^k}$ 	Status of $S_n = n^n + 1 = 2^{2^m} + 1 = F_m$
$0$ 	$1$ 	$2$ 	Prime ($S_2 = F_1 = 5$)
$1$ 	$3$ 	$4$ 	Prime ($S_4 = F_3 = 257$)
$2$ 	$6$ 	$16$ 	Composite with factor $1071 \times 2^8 + 1$
$3$ 	$11$ 	$256$ 	Composite with factor $39 \times 2^{13} + 1$
$4$ 	$20$ 	$65 \, 536$ 	Composite with no factor known
$5$ 	$37$ 	$4 \, 294 \, 967 \, 296$	Composite with factor $1 \, 275 \, 438 \, 465 \times 2^{39} + 1$
$6$ 	$70$ 	too large 	unknown
$7$ 	$135$ 	 	unknown
$8$ 	$264$ 	 	unknown
$9$ 	$521$ 	 	unknown
$10$	$1034$ 	 	unknown
$11$	$2059$ 	 	Composite with factor $591 \, 909 \times 2^{2063} + 1$
$12$	$4108$ 	 	unknown
$13$	$8205$ 	 	unknown
$14$	$16 \, 398$ 	 	unknown
$15$	$32 \, 783$ 	 	unknown
$16$	$65 \, 552$ 	 	unknown
$17$	$131 \, 089$ 	 	unknown
== Sources ==
* 
* : $257$
* : $257$
* 
Category:Sierpiński Numbers of the First Kind
Prime Sum of Squares of 3 Prime Numbers

== Theorem ==
Let $a$, $b$ and $c$ be prime numbers with the property that:
:$a^2 + b^2 + c^2 = p$
where $p$ is a prime number.
Then either $1$ or $2$ of $a$, $b$ and $c$ is equal to $3$.
== Proof ==
First we note that sets of $3$ prime numbers with this property are plentiful.
For example, these are all such sets for $a, b, c < 20$:
And indeed, the number of instances of $3$ in all the above is either $1$ or $2$.
First we note that if $a = b = c = 3$ then $a^2 + b^2 + c^2 = 27$ which is not prime.
It remains to demonstrate that if none of $a$, $b$ and $c$ are equal to $3$, then $a^2 + b^2 + c^2$ is not prime.
Let $q$ be a prime number such that $q \ne 3$.
Then by definition of prime number:
:$3 \nmid q$
where $\nmid$ denotes non-divisibility.
Then from Square Modulo 3:
:$q^2 \pmod 3 = 1$
Suppose none of $a$, $b$ and $c$ is equal to $3$.
Then:
That is:
:$3 \divides a^2 + b^2 + c^2$
where $\divides$ denotes divisibility.
Hence if none of $a$, $b$ and $c$ is equal to $3$, $a^2 + b^2 + c^2$ is not prime number.
The result follows.
Category:Prime Numbers
Category:3
Prime Triplet Conjecture

== Conjecture ==
It is conjectured that there exist infinitely many prime triplets: that is, sets of three (positive) prime numbers either:
:$\set {n, n + 2, n + 6}$
or:
:$\set {n, n + 4, n + 6}$.
== Historical Note ==
== Sources ==
* : $\text I$: The Series of Primes: $1.4$ The sequence of primes
Category:Unproven Hypotheses
Category:Prime Triplets
Prime Triplet Conjecture/Historical Note

== Historical Note on Prime Triplet Conjecture ==
 (we presume) announces the following in $1938$ or thereabouts:
:Such conjectures, with larger sets of primes, may be multiplied, but their proof or disproof is at present beyond the resources of mathematicians.
Research into this subject is ongoing at time of writing in the early $2020$'s, and greatly aided by the efforts of silicon-based lifeforms.
== Sources ==
* : $\text I$: The Series of Primes: $1.4$ The sequence of primes
Category:Historical Notes
Prime Values of Double Factorial plus 1

== Theorem ==
Let $n!!$ denote the double factorial function.
The sequence of positive integers $n$ such that $n!! + 1$ is prime begins:
:$0, 1, 2, 518, 33 \, 416, 37 \, 310, 52 \, 608, 123 \, 998, 220 \, 502, \ldots$
== Proof ==
We have that:
== Sources ==
* 
* : $518$
Category:Double Factorials
Prime between n and 9 n divided by 8

== Theorem ==
Let $n \in \Z$ be an integer such that $n \ge 48$.
Then there exists a prime number $p$ such that $n < p < \dfrac {9 n} 8$.
== Proof ==
Let $\map P n$ be the property:
:there exists a prime number $p$ such that $n \le p \le \dfrac {9 n} 8$.
First note that $\map P n$ does not hold for the following $n < 48$:
:$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 19, 21, 23, 24, 25, 31, 32, 47$
Taking $47$ as an example:
We have that:
: $\dfrac {9 \times 47} 8 = 52 \cdotp 875$
and so it is seen that $\map P {47}$ does not hold.
== Sources ==
* : $48$
* : $48$
Category:Prime Numbers
Prime between n and 9 n divided by 8/Mistake

== Source Work ==
:
:The Dictionary
::$48$
:
:The Dictionary
::$48$
== Mistake ==
:If $n$ is greater than $48$, then there is a prime between $n$ and $9 n / 8$, inclusive.
== Correction ==
While this is in fact true, the statement as it stands actually holds for $n = 32$.
What is more probably what is required here is the statement:
:If $n$ is greater than or equal to $48$, then there is a prime between $n$ and $9 n / 8$, exclusive.
With this latter statement, when $n = 47$, $n$ itself is prime and so there exists such a prime.
Also note that if $9 n / 8$ is an integer, then it is not a prime as it has $9$ as a divisor.
Thus whether this upper bound is exclusive or inclusive is immaterial.
== Sources ==
* : $48$
* : $48$
Category:Mistakes/Curious and Interesting Numbers
Prime equals Plus or Minus One modulo 6

== Theorem ==
Let $p$ be a prime number greater than $3$.
Then $p$ is either of the form:
:$p = 6 n + 1$
or:
:$p = 6 n - 1$
That is:
:$p = \pm 1 \pmod 6$
== Proof ==
To demonstrate that there are prime numbers of either form, note:
:$5 = 6 \times 1 - 1$
:$7 = 6 \times 1 + 1$
The only other possibilities for $p$ are:
:$p = 6 n$, in which case $6 \divides p$ and so $p$ is not prime
:$p = 6 n + 2$, in which case $2 \divides p$ and so $p$ is not prime
:$p = 6 n + 3$, in which case $3 \divides p$ and so $p$ is not prime
:$p = 6 n + 4$, in which case $2 \divides p$ and so $p$ is not prime
:$p = 6 n + 5$, which is the same as $p = 6 \paren {n + 1} - 1$, which is covered above.
Hence the result.
== Sources ==
* : $5$
* : $6$
* : $5$
* : $6$
Category:Prime Numbers
Category:6
Prime iff Coprime to all Smaller Positive Integers

== Theorem ==
Let $p$ be a prime number.
Then:
:$\forall x \in \Z, 0 < x < p: x \perp p$
That is, $p$ is relatively prime to all smaller (strictly) positive integers.
== Proof ==
From Prime not Divisor implies Coprime, if $p$ does not divide an integer $x$, it is relatively prime to $x$.
From Absolute Value of Integer is not less than Divisors: Corollary, $p$ does not divide an integer smaller than $p$.
It follows that $p$ is relatively prime to all smaller (strictly) positive integers.
The special case when $x = 0$ is excluded as from Integers Coprime to Zero, $p$ is not relatively prime to $0$.
== Sources ==
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$
Category:Prime Numbers
Category:Coprime Integers
Prime iff Equal to Product

== Theorem ==
Let $p \in \Z$ be an integer such that $p \ne 0$ and $p \ne \pm 1$.
Then $p$ is prime :
:$\forall a, b \in \Z: p = ab \implies p = \pm a \lor p = \pm b$
== Proof ==
=== Necessary Condition ===
Let $p$ be a prime number.
Then by definition, the only divisors of $p$ are $\pm 1$ and $\pm p$.
Thus, if $p = a b$ then either $a = \pm 1$ and $b = \pm p$ or $a = \pm p$ and $b = \pm 1$.
=== Sufficient Condition ===
Suppose that:
:$\forall a, b \in \Z: p = a b \implies p = \pm a \lor p = \pm b$
This means that the only divisors of $p$ are $\pm 1$ and $\pm p$.
That is, that $p$ is a prime number.
== Sources ==
* : $\S 0.1$. Arithmetic: Theorem $3$
Category:Prime Numbers
Prime is Pseudoprime (Order Theory)

== Theorem ==
Let $L = \left({S, \vee, \wedge, \preceq}\right)$ be an up-complete lattice.
Let $p \in S$ be a prime element.
Then $p$ is pseudoprime.
== Proof ==
By Lower Closure is Prime Ideal for Prime Element:
:$p^\preceq$ is prime ideal.
By Supremum of Lower Closure of Element:
:$ \sup \left({ p^\preceq }\right) = p$
Hence $p$ is pseudoprime.
== Sources ==
* 
* 
Category:Prime Elements
Prime not Divisor implies Coprime

== Theorem ==
Let $p, a \in \Z$.
If $p$ is a prime number then:
:$p \nmid a \implies p \perp a$
where:
:$p \nmid a$ denotes that $p$ does not divide $a$
:$p \perp a$ denotes that $p$ and $a$ are coprime.
It follows directly that if $p$ and $q$ are primes, then:
:$p \divides q \implies p = q$
:$p \ne q \implies p \perp q$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\text {2-2}$ Divisibility: Example $\text {2-11}$
* : $\S 12.1$: Highest common factors and Euclid's algorithm
Category:Prime Numbers
Category:Coprime Integers
Category:Prime not Divisor implies Coprime
Prime not Divisor implies Coprime/Proof 1

== Theorem ==
== Proof ==
Let $p \in \Bbb P, p \nmid a$.
We need to show that $\gcd \set {a, p} = 1$.
Let $\gcd \set {a, p} = d$.
As $d \divides p$, we must have $d = 1$ or $d = p$ by GCD with Prime.
But if $d = p$, then $p \divides a$ by definition of greatest common divisor.
So $d \ne p$ and therefore $d = 1$.
Category:Prime not Divisor implies Coprime
Prime not Divisor implies Coprime/Proof 2

== Theorem ==
== Proof ==
Let $p$ be a prime number.
Let $a \in \Z$ be such that $p$ is not a divisor of $a$.
 $p$ and $a$ are not coprime.
Then:
:$\exists c \in \Z_{>1}: c \divides p, c \divides a$
where $\divides$ denotes divisibility.
But then by definition of prime:
:$c = p$
Thus:
:$p \divides a$
The result follows by Proof by Contradiction.
== Sources ==
* : Book $\text{VII}$. Propositions
Category:Prime not Divisor implies Coprime