nyuuzyou/wikis huggingface dataset:
Erdős-Straus Conjecture/Sierpiński Variant

== Unproven Hypothesis ==
Let $n$ be an integer.
It is conjectured that $\dfrac 5 n$ can always be expressed as the sum of $3$ unit fractions.
 
== Sources ==
* 
* : $2 / 3$
* 
* : $2 / 3$
Category:Unit Fractions
Category:Unproven Hypotheses
Ergodicity/Examples/Boolean Markov Chain

== Example of Ergodicity ==
Let $M := \sequence {X_n}_{n \mathop \ge 0}$ be a Markov chain whose state space $S$ is a Boolean domain:
:$S = \set {0, 1}$
Let $M$ be such that all the entries of the transition matrix are non-zero.
Then $M$ achieves ergodicity at the point where:
:$M$ has a probability $\dfrac {p_{10} } {p_{01} + p_{10} }$ of being in state $0$ 
:$M$ has a probability $\dfrac {p_{01} } {p_{01} + p_{10} }$ of being in state $1$.
== Sources ==
* 
* 
Category:Examples of Ergodicity
Category:Markov Chains
Error Correction Capability of Linear Code

== Theorem ==
Let $C$ be a linear code.
Let $C$ have a minimum distance $d$.
Then $C$ corrects $e$ transmission errors for all $e$ such that $2 e + 1 \le d$.
== Proof ==
Let $C$ be a linear code whose master code is $V$.
Let $c \in C$ be a transmitted codeword.
Let $v$ be the received word from $c$.
By definition, $v$ is an element of $V$.
Let $v$ have a Hamming distance $e$ from $c$, where $2 e + 1 \le d$.
Thus there have been $e$ transmission errors.
 $c_1$ is a codeword of $C$, distinct from $c$, such that $\map d {v, c_1} \le e$.
Then:
So $c_1$ has a Hamming distance from $c$ less than $d$.
But $C$ has a minimum distance $d$.
Thus $c_1$ cannot be a codeword of $C$.
From this contradiction it follows that there is no codeword of $C$ closer to $v$ than $c$.
Hence there is a unique codeword of $C$ which has the smallest Hamming distance from $v$.
Hence it can be understood that $C$ has corrected the transmission errors of $v$.
== Sources ==
* : Chapter $6$: Error-correcting codes: Proposition $6.10$
* 
Category:Linear Codes
Error Detection Capability of Linear Code

== Theorem ==
Let $C$ be a linear code.
Let $C$ have a minimum distance $d$.
Then $C$ detects $d - 1$ or fewer transmission errors.
== Proof ==
Let $C$ be a linear code whose master code is $V$.
Let $c \in C$ be a transmitted codeword.
Let $v$ be the received word from $c$.
By definition, $v$ is an element of $V$.
Let $v$ have a Hamming distance $f$ from $c$, where $f \le d - 1$.
Thus there have been $f$ transmission errors.
As $d$ is the minimum distance it is clear that $v$ cannot be a codeword of $C$.
Hence it can be understood that $C$ has detected that $v$ has as many as $d - 1$ transmission errors.
== Sources ==
* : Chapter $6$: Error-correcting codes: Proposition $6.10$
Category:Linear Codes
Error Function is Odd

== Theorem ==
:$\map \erf {-x} = -\map \erf x$
where:
:$\erf$ denotes the error function
:$x$ is a real number.
== Proof ==
== Sources ==
* : $\S 35$: Error Function $\ds \map \erf x = \frac 2 {\sqrt \pi} \int_0^x e^{-u^2} \rd u$: $35.3$
Category:Error Function
Category:Examples of Odd Functions
Error Function of Zero

== Theorem ==
:$\map \erf 0 = 0$
where $\erf$ denotes the error function. 
== Proof ==
By Error Function is Odd, $\erf$ is a odd function. 
Therefore, by Odd Function of Zero is Zero:
:$\map \erf 0 = 0$
== Sources ==
* : $\S 35$: Error Function $\ds \map \erf x = \frac 2 {\sqrt \pi} \int_0^x e^{-u^2} \rd u$: $35.3$
Category:Error Function
Escape Velocity in terms of Gravitational Constant

== Theorem ==
Let $P$ be a planet.
Let $P$ have:
:a mass of $M$
:a radius of $R$.
Then the escape velocity of $P$ is given by:
:$V = \sqrt {\dfrac {2 M G} R}$
where $G$ is the gravitational constant.
== Proof ==
Let $b$ be a particle with mass $m$. 
Let $K_i$ be the kinetic energy of $b$ at the surface of $P$. 
Let $U_i$ be the potential energy of $b$ at the surface of $P$. 
Let $K_f$ be the limit of the kinetic energy of $b$ as it leaves $P$. 
Let $U_f$ be the limit of the potential energy of $b$ as it leaves $P$. 
Let $v_f$ be the limit of the speed of $b$ as it leaves $P$. 
Let $r_f$ be the limit of the distance of $b$ from the center of $P$ as $b$ leaves $P$. 
Let $v_e$ be the speed of $b$ at the surface of $P$. 
The speed of $b$ becomes arbitarily small as it leaves $P$.
Thus:
:$v_f = 0$
The distance of $b$ to the center of $P$ becomes arbitarily large as it leaves $P$.
Thus:
:$r_f = \infty$
By Kinetic Energy of Motion: 
By Gravitational Potential Energy of Position for Bodies Far From Center:
Now:
== Sources ==
* 
* 
Category:Escape Velocity
Escape Velocity of Projectile fired Upwards

== Theorem ==
Let $P$ be a planet.
Let $P$ have an Acceleration Due to Gravity at its surface of $g$.
Let $P$ have a radius of $R$.
Then the escape velocity of $P$ is given by:
:$V = \sqrt {2 g R}$
== Proof ==
== Sources ==
* : $1$: The Nature of Differential Equations: $\S 5$: Falling Bodies and Other Rate Problems: Problem $3$
Category:Escape Velocity
Escape Velocity of Projectile fired Upwards/Proof 1

== Theorem ==
== Proof ==
Let a projectile $B$ of mass $m$ be fired vertically upwards from the surface of $P$ at such a speed that it escapes the gravitational field of $P$ completely.
$F$ be the force exerted on the projectile by the gravitational field of $P$.
Let $x$ be the distance of $B$ from the surface of $P$ at time $t$.
We have:
:$F = -\dfrac k {x^2}$
where $k$ can be calculated at the surface of $P$ as:
Thus:
:$F = -\dfrac {m g R^2} {x^2}$
Let the $B$ be travelling away from $P$ with speed $v$ at time $t$.
Thus:
So:
:$\ds -\int \frac {R^2 g} {x^2} \rd x = \int v \rd v$
This gives:
:$\dfrac {R^2 g} x = \dfrac {v^2} 2 + C$
Now when $x = R$, $v = v_0$, the launch velocity, which leads to:
:$C = R g - \dfrac {v_0^2} 2$
and so:
:$\dfrac {v^2} 2 = \dfrac {R^2 g} x - R g + \dfrac {v_0^2} 2$
For $\dfrac {v^2} 2 > 0$ we need:
:$\dfrac {v_0^2} 2 > R g \paren {1 - \dfrac R x}$
whatever $x$ may be.
So when $x \to \infty$ we have:
:$\dfrac {v_0^2} 2 > R g$
Hence:
:$v_0 > \sqrt {2 R g}$
Category:Mechanics
Estimation Lemma for Contour Integrals

== Theorem ==
Let $C$ be a contour.
Let $f: \Img C \to \C$ be a continuous complex function, where $\Img C$ denotes the image of $C$.
Then:
:$\ds \size {\int_C \map f z \rd z} \le \max_{z \mathop \in \Img C} \size {\map f z} \map L C$
where $\map L C$ denotes the length of $C$.
== Proof ==
By definition of contour, $C$ is a concatenation of a finite sequence $C_1, \ldots, C_n$ of directed smooth curves.
Let $C_k$ be parameterized by the smooth path $\gamma_k: \closedint {a_k} {b_k} \to \C$ for all $k \in \set {1, \ldots, n}$.
Then:
== Also known as ==
Some sources give this as Triangle Inequality for Contour Integrals.
Both names are used on in order to enhance accessibility.
== Sources ==
* : $\S 2.2$
Category:Complex Contour Integrals
Category:Named Theorems
Category:Triangle Inequality
Category:Inequalities
Euclid's Lemma

== Theorem ==
Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.
== Proof 1 ==
== Proof 2 ==
== Also see ==
* Euclid's Lemma for Prime Divisors
== Sources ==
* : Chapter $2$: Some Properties of $\Z$: Exercise $2.5$
Category:Euclid's Lemma
Category:Divisors
Category:Coprime Integers
Euclid's Lemma/Proof 2

== Theorem ==
== Proof ==
Let $a, b, c \in \Z$.
We have that $a \perp b$.
That is:
:$\gcd \set {a, b} = 1$
where $\gcd$ denotes greatest common divisor.
From Bézout's Identity, we may write:
:$a x + b y = 1$
for some $x, y \in \Z$.
Upon multiplication by $c$, we see that:
:$c = c \paren {a x + b y} = c a x + c b y$
Now note that $c a x + c b y$ is an integer combination of $a c$ and $b c$.
So, since:
:$a \divides a c$
and:
:$a \divides b c$
it follows from Common Divisor Divides Integer Combination that:
:$a \divides \paren {c a x + c b y}$
However:
: $c a x + c b y = c \paren {a x + b y} = c \cdot 1 = c$
Therefore:
: $a \divides c$
== Also see ==
* Euclid's Lemma for Prime Divisors
== Sources ==
* : Chapter $3$: The Integers: $\S 12$. Primes: Theorem $20$
* : $\text {2-2}$ Divisibility: Theorem $\text {2-3}$
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Theorem $2 \text{-} 5$
Category:Euclid's Lemma
Euclid's Lemma for Euclidean Domains

== Theorem ==
Let $\struct {D, +, \times}$ be a Euclidean domain whose unity is $1$.
Let $a, b, c \in D$.
Let $a \divides b \times c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.
== Proof ==
== Also see ==
* Euclid's Lemma for Irreducible Elements
* Euclid's Lemma, for the usual statement of this result, which is this lemma as applied specifically to the integers.
== Sources ==
* : Chapter $6$: Polynomials and Euclidean Rings: $\S 29$. Irreducible elements: Theorem $55$
Category:Euclidean Domains
Category:Euclid's Lemma
Euclid's Lemma for Irreducible Elements

== Lemma ==
Let $\struct {D, +, \times}$ be a Euclidean domain whose unity is $1$.
Let $p$ be an irreducible element of $D$.
Let $a, b \in D$ such that:
:$p \divides a \times b$
where $\divides$ means is a divisor of.
Then $p \divides a$ or $p \divides b$.
=== General Result ===
== Proof ==
Let $p \divides a \times b$.
Suppose $p \nmid a$.
Then from the definition of irreducible:
: $p \perp a$
Thus from Euclid's Lemma for Euclidean Domains:
:$p \divides b$
Similarly, if $p \nmid b$:
:$p \divides a$
So:
:$p \divides a b \implies p \divides a$
or:
:$p \divides b$
as we needed to show.
== Also see ==
* Euclid's Lemma for Prime Divisors, for the usual statement of this result, which is this lemma as applied specifically to the integers.
== Sources ==
* : Chapter $6$: Polynomials and Euclidean Rings: $\S 29$. Irreducible elements: Theorem $56 \ \text{(i)}$
Category:Euclidean Domains
Category:Euclid's Lemma
Euclid's Lemma for Irreducible Elements/General Result

== Lemma ==
Let $\struct {D, +, \times}$ be a Euclidean domain whose unity is $1$.
Let $p$ be an irreducible element of $D$.
Let $n \in D$ such that:
:$\ds n = \prod_{i \mathop = 1}^r a_i$
where $a_i \in D$ for all $i: 1 \le i \le r$.
If $p$ divides $n$, then $p$ divides $a_i$ for some $i$.
That is:
:$p \divides a_1 a_2 \ldots a_n \implies p \divides a_1 \lor p \divides a_2 \lor \cdots \lor p \divides a_n$
== Proof ==
Proof by induction:
For all $r \in \N_{>0}$, let $\map P r$ be the proposition:
:$\ds p \divides \prod_{i \mathop = 1}^r a_i \implies \exists i \in \closedint 1 r: p \divides a_i$
$\map P 1$ is true, as this just says $p \divides a_1 \implies p \divides a_1$.
=== Basis for the Induction ===
$\map P 2$ is the case:
:$p \divides a_1 a_2 \implies p \divides a_2$ or $p \divides a_2$
which is proved in Euclid's Lemma for Irreducible Elements.
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:
:$\ds p \divides \prod_{i \mathop = 1}^k a_i \implies \exists i \in \closedint 1 k: p \divides a_i$
Then we need to show:
:$\ds p \divides \prod_{i \mathop = 1}^{k + 1} a_i \implies \exists i \in \closedint 1 {k + 1}: p \divides a_i$
=== 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:
:$\ds \forall r \in \N: p \divides \prod_{i \mathop = 1}^r a_i \implies \exists i \in \closedint 1 r: p \divides a_i$
== Also see ==
* Euclid's Lemma for Prime Divisors, for the usual statement of this result, which is this lemma as applied specifically to the integers.
== Sources ==
* : Chapter $6$: Polynomials and Euclidean Rings: $\S 29$. Irreducible elements: Theorem $56 \ \text{(ii)}$
Category:Euclidean Domains
Category:Euclid's Lemma
Euclid's Lemma for Prime Divisors

== Lemma ==
Let $p$ be a prime number.
Let $a$ and $b$ be integers such that:
: $p \divides a b$
where $\divides$ means is a divisor of.
Then $p \divides a$ or $p \divides b$.
=== General Result ===
=== Corollary ===
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Examples ==
== Also presented as ==
== Also known as ==
== Also see ==
* Euclid's Lemma
== Historical Note ==
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $24$. The Division Algorithm: Exercise $24.8 \ \text{(a)}$
* : $\text I$: The Series of Primes: $1.3$ Statement of the fundamental theorem of arithmetic: Theorem $3$
* 
* 
Category:Euclid's Lemma for Prime Divisors
Category:Euclid's Lemma
Category:Prime Numbers
Euclid's Lemma for Prime Divisors/Also known as

== Euclid's Lemma for Prime Divisors: Also known as == 
Some sources give the name of Euclid's Lemma for Prime Divisors as Euclid's First Theorem.
== Sources ==
* : $\text I$: The Series of Primes: $1.3$ Statement of the fundamental theorem of arithmetic: Theorem $3$
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Prime Divisors/Also presented as

== Euclid's Lemma for Prime Divisors: Also presented as == 
Some sources present Euclid's Lemma for Prime Divisors as:
Let $p$ be a prime number.
Let $a$ and $b$ be integers such that:
:$a b \equiv 0 \pmod p$
Then either $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$.
Some sources use this property to define a prime number.
== Sources ==
* : Chapter $2$. Equivalence Relations: Exercise $7$
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Prime Divisors/Corollary

== Corollary to Euclid's Lemma for Prime Divisors ==
Let $p, p_1, p_2, \ldots, p_n$ be primes such that:
:$p \divides \ds \prod_{i \mathop = 1}^n p_i$
Then:
:$\exists i \in \closedint 1 n: p = p_i$
== Proof==
From Euclid's Lemma for Prime Divisors: General Result, $p \divides p_i$ for some $i$.
But by the definition of a prime number, the only divisors of $p_i$ are $1$ and $p_i$ itself.
As $1$ is not prime, it follows that $p = p_i$.
Hence the result.
Category:Euclid's Lemma
Euclid's Lemma for Prime Divisors/Examples/6

== Example of Use of Euclid's Lemma for Prime Divisors ==
Note that Euclid's Lemma for Prime Divisors does not hold for composite numbers.
For example:
:$6 \divides 12 = 3 \times 4$
but:
:$6 \nmid 3$ and $6 \nmid 4$
== Sources ==
* 
* 
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Prime Divisors/General Result

== Lemma ==
Let $p$ be a prime number.
Let $\ds n = \prod_{i \mathop = 1}^r a_i$.
Then if $p$ divides $n$, it follows that $p$ divides $a_i$ for some $i$ such that $1 \le i \le r$.
That is:
:$p \divides a_1 a_2 \ldots a_n \implies p \divides a_1 \lor p \divides a_2 \lor \cdots \lor p \divides a_n$
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Examples ==
== Also see ==
* Euclid's Lemma
== Historical Note ==
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $24$. The Division Algorithm: Exercise $24.8 \ \text{(a)}$
* : $\text I$: The Series of Primes: $1.3$ Statement of the fundamental theorem of arithmetic
* : Chapter $\text {B}.16$: The Sequence of Primes: Problem $1 \ \text{(b)}$
* 
* 
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Prime Divisors/General Result/Proof 2

== Lemma ==
== Proof ==
Proof by induction:
For all $r \in \N_{>0}$, let $\map P r$ be the proposition:
:$\ds p \divides \prod_{i \mathop = 1}^r a_i \implies \exists i \in \closedint 1 r: p \divides a_i$
$\map P 1$ is true, as this just says $p \divides a_1 \implies p \divides a_1$.
=== Basis for the Induction ===
$\map P 2$ is the case:
:$p \divides a_1 a_2 \implies p \divides a_2$ or $p \divides a_2$
which is proved in Euclid's Lemma for Prime Divisors.
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:
:$\ds p \divides \prod_{i \mathop = 1}^k a_i \implies \exists i \in \closedint 1 k: p \divides a_i$
Then we need to show:
:$\ds p \divides \prod_{i \mathop = 1}^{k + 1} a_i \implies \exists i \in \closedint 1 {k + 1}: p \divides a_i$
=== 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:
:$\ds \forall r \in \N: p \divides \prod_{i \mathop = 1}^r a_i \implies \exists i \in \closedint 1 r: p \divides a_i$
== Sources ==
* : Chapter $3$: The Integers: $\S 12$. Primes: Theorem $21 \ \text{(ii)}$
* : $\text {2-2}$ Divisibility: Corollary $\text {2-4}$
* : $\S 12.6$: Highest common factors and Euclid's algorithm
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Corollary $9$
Category:Euclid's Lemma for Prime Divisors
Category:Proofs by Induction
Euclid's Lemma for Prime Divisors/General Result/Proof 3

== Lemma ==
== Proof ==
Let $p \divides n$.
:
:$\forall i \in \set {1, 2, \ldots, r}: p \nmid a_i$
By Prime not Divisor implies Coprime:
:$\forall i \in \set {1, 2, \ldots, r}: p \perp a_i$
By Integer Coprime to all Factors is Coprime to Whole:
:$p \perp n$
By definition of coprime:
:$p \nmid n$
The result follows by Proof by Contradiction.
== Sources ==
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Proposition $3 \ \text{(ii)}$
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Prime Divisors/Proof 1

== Lemma ==
== Proof ==
We have that the integers form a Euclidean domain.
Then from Irreducible Elements of Ring of Integers we have that the irreducible elements of $\Z$ are the primes and their negatives.
The result then follows directly from Euclid's Lemma for Irreducible Elements.
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Prime Divisors/Proof 2

== Lemma ==
== Proof ==
Let $p \divides a b$.
Suppose $p \nmid a$.
Then from the definition of prime:
:$p \perp a$
where $\perp$ indicates that $p$ and $a$ are coprime.
Thus from Euclid's Lemma it follows that:
:$p \divides b$
Similarly, if $p \nmid b$ it follows that $p \divides a$.
So:
:$p \divides a b \implies p \divides a$ or $p \divides b$
as we needed to show.
== Sources ==
* : Chapter $3$: The Integers: $\S 12$. Primes: Theorem $21 \ \text{(i)}$
* : $\text {2-2}$ Divisibility: Corollary $\text {2-3}$
* : Chapter $1$: Properties of the Natural Numbers: $\S 23$
* : $\S 12.5$: Highest common factors and Euclid's algorithm
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $8$
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Prime Divisors/Proof 3

== Lemma ==
== Proof ==
Let $p \divides a b$.
Suppose $p \nmid a$.
Then by :
:$p \perp a$
As $p \divides a b$, it follows by definition of divisor:
:$\exists e \in \Z: e p = a b$
So by :
:$p : a = b : e$
But as $p \perp a$, by:
:
and: 
:
it follows that:
:$p \divides b$
Similarly, if $p \perp b$ then $p \divides a$.
Hence the result.
== Sources ==
* : Book $\text{VII}$. Propositions
* : Chapter $\text {A}.4$: Euclid (flourished ca. $300$ B.C.)
* : Chapter $7$: Patterns in Numbers: Euclid
Category:Euclid's Lemma for Prime Divisors
Euclid's Lemma for Unique Factorization Domain

== Lemma ==
Let $\struct {D, +, \times}$ be a unique factorization domain.
Let $p$ be an irreducible element of $D$.
Let $a, b \in D$ such that:
:$p \divides a \times b$
where $\divides$ means is a divisor of.
Then $p \divides a$ or $p \divides b$.
=== General Result ===
== Proof ==
The elements $a$ and $b$ have complete factorizations:
:$a = u \times x_1 \times x_2 \times \cdots \times x_n$
and
:$b = v \times y_1 \times y_2 \times \cdots \times y_m$
where $u$ and $v$ are units of $D$ and $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_m$ are irreducible elements.
Then the unique complete factorization of $a \times b$ into irreducible elements is:
:$(1): \quad a \times b = \paren {u \times v} \times x_1 \times x_2 \times \cdots \times x_n \times y_1 \times y_2 \times \cdots \times y_m$
If $p$ is an associate of $x_i$ for some $i$ then we will have $p \divides a$.
Similarly, if $p$ is an associate of $y_i$ for some $i$ then $p \divides b$. 
 that $p$ is not an associate of $x_i$ or $y_i$ for all $i$.
Since $p \divides a \times b$, there is a $c \in D$ such that $p \times c = a \times b$.
This element $c$ has the unique complete factorization:
:$c = w \times z_1 \times z_2 \times \cdots \times z_l$
where $w$ is a unit of $D$ and $z_1, z_2, \ldots, z_l$ are irreducible elements.
This gives us another complete factorization:
:$a \times b = w \times p \times z_1 \times z_2 \times \cdots \times z_l$
But the complete factorization $(1)$ contains no irreducible element that is an associate of $p$.
This contradicts the unique factorization of $a \times b$.
We conclude that $p$ is an associate of $x_i$ or $y_i$ for some $i$.
Therefore, $p \divides a$ or $p \divides b$.
== Also see ==
* Euclid's Lemma for Prime Divisors, for the usual statement of this result, which is this lemma as applied specifically to the integers.
* Euclid's Lemma for Irreducible Elements is the same result when $D$ is a Euclidean Domain.
Category:Unique Factorization Domains
Category:Euclid's Lemma
Euclid's Lemma for Unique Factorization Domain/General Result

== Lemma ==
Let $\struct {D, +, \times}$ be a unique factorization domain.
Let $p$ be an irreducible element of $D$.
Let $n \in D$ such that:
:$\ds n = \prod_{i \mathop = 1}^r a_i$
where $a_i \in D$ for all $i: 1 \le i \le r$.
Then if $p$ divides $n$, it follows that $p$ divides $a_i$ for some $i$.
That is:
:$p \divides a_1 a_2 \ldots a_n \implies p \divides a_1 \lor p \divides a_2 \lor \cdots \lor p \divides a_n$
== Proof ==
Identical to the proof of Euclid's Lemma for Irreducible Elements: General Result.
Category:Unique Factorization Domains
Category:Euclid's Lemma
Euclid's Theorem

== Theorem ==
For any finite set of prime numbers, there exists a prime number not in that set.
=== Corollary 1 ===
=== Corollary 2 ===
== Proof ==
Let $\mathbb P$ be a finite set of prime numbers.
Consider the number:
:$\ds n_p = \paren {\prod_{p \mathop \in \mathbb P} p} + 1$
Take any $p_j \in \mathbb P$.
We have that:
:$\ds p_j \divides \prod_{p \mathop \in \mathbb P} p$
Hence:
:$\ds \exists q \in \Z: \prod_{p \mathop \in \mathbb P} p = q p_j$
So:
So $p_j \nmid n_p$.
There are two possibilities:
:$(1): \quad n_p$ is prime, which is not in $\mathbb P$. 
:$(2): \quad n_p$ is composite.
But from Positive Integer Greater than 1 has Prime Divisor‎, it must be divisible by some prime.
That means it is divisible by a prime which is not in $\mathbb P$.
So, in either case, there exists at least one prime which is not in the original set $\mathbb P$ we created.
== Fallacy ==
== Also see ==
* Furstenberg's Proof of Infinitude of Primes
* Definition:Euclid Number
== Sources ==
* : Book $\text{IX}$. Propositions
* : Chapter $1$: Properties of the Natural Numbers: $\S 22 \beta$
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Theorem $5$
* : $1$
* : Chapter $\text {A}.4$: Euclid (flourished ca. $300$ B.C.)
* : Chapter $\text {B}.16$: The Sequence of Primes: Theorem $2$
* : Chapter $\text {B}.19$: The Series $\sum 1/ p_n$ of the Reciprocals of the Primes
* : $1$
* 
* 
* : Chapter $7$: Patterns in Numbers: Euclid
Category:Prime Numbers
Category:Euclid's Theorem
Euclid's Theorem/Corollary 1

== Corollary to Euclid's Theorem ==
There are infinitely many prime numbers.
== Proof 1 ==
== Proof 2 ==
== Also known as ==
This result is often referred to as Euclid's Theorem.
But himself did not explicitly state that there is an infinite number of primes, just that it was impossible to create a list containing them all.
Some sources refer to it as Euclid's second theorem, his first being Euclid's Lemma for Prime Divisors.
== Sources ==
* : Chapter $1$: Properties of the Natural Numbers: $\S 22 \gamma$
* : $\text I$: The Series of Primes: $1.4$ The sequence of primes
* 
Category:Euclid's Theorem
Euclid's Theorem/Corollary 1/Historical Note

== Historical Note on Corollary 1 to Euclid's Theorem ==
This Corollary 1 to Euclid's Theorem is itself often referred to as Euclid's Theorem, although himself never raised the concept of infinity.
Strictly speaking, Euclid's Theorem merely states that from any finite set of prime numbers, it is always possible to demonstrate that there exists another not in that list.
Category:Historical Notes