nyuuzyou/wikis huggingface dataset:
GCD from Generator of Ideal

== Theorem ==
Let $m, n \in \Z$, with either $m \ne 0$ or $n \ne 0$.
Let $I = \ideal {m, n}$ be the ideal generated by $m$ and $n$.
Let $d$ be a non-negative generator for the principal ideal $I$.
Then:
:$\gcd \set {m, n} = d$
where $\gcd \set {m, n}$ denotes the greatest common divisor of $m$ and $n$.
== Proof ==
First we show that such an element $d$ exists.
By Ring of Integers is Principal Ideal Domain there exists a generator $e$ of $I$.
If $e < 0$, then since the units of $\Z$ are $\set {\pm 1}$, we have by definition that $-e$ is an associate of $e$.
Therefore by $(3)$ of Principal Ideals in Integral Domain $-e > 0$ is also a generator of $I$.
In particular setting $d = \max \set {e, -e}$, $d$ is a non-negative generator of $I$.
By Bézout's Identity, we are required to show that $d$ is the smallest positive integer combination of $m$ and $n$.
By definition:
:$I = \set {a m + b n: a, b \in \Z}$
Thus we are required to show that $d$ is the smallest positive element of $I$.
Suppose that $d' \le d$ is a positive element of $I$, not larger than $d$.
By hypothesis $d$ generates $I$, so there exists $a \in \Z$ such that $d' = ad$.
Since $d > 0$, we can therefore write $a = \dfrac {d'} d \in \Q$.
Moreover, because $d' > 0$, by $(6)$ of Properties of Ordered Ring we have:
:$0 = \dfrac 0 d < \dfrac {d'} d$
Using the hypothesis that $d' \le d$, we have the pair of inequalities:
:$0 < a = \dfrac {d'} d \le 1$
By the definition we have $a \in \Z$, so this shows that $\dfrac {d'} d = 1$.
It follows that $d' = d$.
Therefore there is no positive element of $I$ smaller than $d$.
Category:Greatest Common Divisor
GCD from Prime Decomposition

== Theorem ==
Let $a, b \in \Z$.
From Expression for Integers as Powers of Same Primes, let:
That is, the primes given in these prime decompositions may be divisors of either of the numbers $a$ or $b$.
Then:
:$\gcd \set {a, b} = p_1^{\min \set {k_1, l_1} } p_2^{\min \set {k_2, l_2} } \ldots p_r^{\min \set {k_r, l_r} }$
where $\gcd \set {a, b}$ denotes the greatest common divisor of $a$ and $b$.
=== General Result ===
== Proof ==
Note that if one of the primes $p_i$ does not appear in the prime decompositions of either one of $a$ or $b$, then its corresponding index $k_i$ or $l_i$ will be zero.
Let $d \divides a$.
Then:
:$d$ is of the form $p_1^{h_1} p_2^{h_2} \ldots p_r^{h_r}, \forall i: 1 \le i \le r, 0 \le h_i \le k_i$
:$d \divides a \iff \forall i: 1 \le i \le r, 0 \le h_i \le l_i$
So:
:$d \divides a \land d \divides b \iff \forall i: 1 \le i \le r, 0 \le h_i \le \min \set {k_i, l_i}$
For $d$ to be at its greatest, we want the largest possible exponent for each of these primes.
So for each $i \in \closedint 1 r$, $h_i$ needs to equal $\min \set {k_i, l_i}$.
Hence the result:
:$\gcd \set {a, b} = p_1^{\min \set {k_1, l_1} } p_2^{\min \set {k_2, l_2} } \ldots p_r^{\min \set {k_r, l_r} }$
== Examples ==
== Also see ==
* LCM from Prime Decomposition
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $5$
* : Chapter $1$: Properties of the Natural Numbers: $\S 24 \alpha$
Category:Greatest Common Divisor
Category:Prime Decompositions
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples

== Examples of Use of GCD from Prime Decomposition ==
=== $121$ and $66$ ===
=== $169$ and $273$ ===
=== $51$ and $87$ ===
=== $2187$ and $999$ ===
=== $64$ and $81$ ===
=== $39$, $102$ and $75$ ===
=== $p^2 q$ and $p q r$ ===
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples/121 and 66

== Example of Use of GCD from Prime Decomposition ==
The greatest common divisor of $121$ and $66$ is:
:$\gcd \set {121, 66} = 11$
== Proof ==
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(a)}$
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples/169 and 273

== Example of Use of GCD from Prime Decomposition ==
The greatest common divisor of $169$ and $273$ is:
:$\gcd \set {169, 273} = 13$
== Proof ==
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(b)}$
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples/2187 and 999

== Example of Use of GCD from Prime Decomposition ==
The greatest common divisor of $2187$ and $999$ is:
:$\gcd \set {2187, 999} = 27$
== Proof ==
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(d)}$
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples/39, 102 and 75

== Example of Use of GCD from Prime Decomposition ==
The greatest common divisor of $39$, $102$ and $75$ is:
:$\gcd \set {39, 102, 75} = 3$
== Proof ==
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $11$
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples/51 and 87

== Example of Use of GCD from Prime Decomposition ==
The greatest common divisor of $51$ and $87$ is:
:$\gcd \set {51, 87} = 3$
== Proof ==
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(c)}$
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples/64 and 81

== Example of Use of GCD from Prime Decomposition ==
The greatest common divisor of $64$ and $81$ is:
:$\gcd \set {64, 81} = 1$
== Proof ==
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(e)}$
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/Examples/p^2 q and p q r

== Example of Use of GCD from Prime Decomposition ==
The greatest common divisor of $p^2 q$ and $p q r$, where $p$, $q$ and $r$ are all primes, is:
:$\gcd \set {p^2 q, p q r} = p q$
== Proof ==
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(f)}$
Category:GCD from Prime Decomposition
GCD from Prime Decomposition/General Result

== Theorem ==
Let $n \in \N$ be a natural number such that $n \ge 2$.
Let $\N_n$ be defined as:
:$\N_n := \set {1, 2, \dotsc, n}$
Let $A_n = \set {a_1, a_2, \dotsc, a_n} \subseteq \Z$ be a set of $n$ integers.
From Expression for Integers as Powers of Same Primes, let:
:$\ds \forall i \in \N_n: a_i = \prod_{p_j \mathop \in T} {p_j}^{e_{i j} }$
where:
:$T = \set {p_j: j \in \N_r}$
such that:
:$\forall j \in \N_{r - 1}: p_j < p_{j - 1}$
:$\forall j \in \N_r: \exists i \in \N_n: p_j \divides a_i$
where $\divides$ denotes divisibility.
Then:
:$\ds \map \gcd {A_n} = \prod_{j \mathop \in \N_r} {p_j}^{\min \set {e_{i j}: \, i \in \N_n} }$
where $\map \gcd {A_n}$ denotes the greatest common divisor of $A_n$.
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds \map \gcd {A_n} = \prod_{j \mathop \in \N_r} {p_j}^{\min \set {e_{i j}: \, i \in \N_n} }$
=== Basis for the Induction ===
$\map P 2$ is the case:
:$\ds \gcd \set {a_1, a_2} = \prod_{j \mathop \in \N_r} {p_j}^{\min \set {e_{1 j}, e_{2 j} } }$
This is GCD from Prime Decomposition.
Thus $\map P 2$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown 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 the induction hypothesis:
:$\ds \map \gcd {A_k} = \prod_{j \mathop \in \N_r} {p_j}^{\min \set {e_{i j}: \, i \in \N_k} }$
from which it is to be shown that:
:$\ds \map \gcd {A_{k + 1} } = \prod_{j \mathop \in \N_r} {p_j}^{\min \set {e_{i j}: \, i \in \N_{k + 1} } }$
=== Induction Step ===
This is the 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 \Z_{\ge 2}: \ds \map \gcd {A_n} = \prod_{j \mathop \in \N_r} {p_j}^{\min \set {e_{i j}: i \in \N_n} }$
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $10$
Category:Greatest Common Divisor
Category:Prime Decompositions
GCD of Consecutive Integers of General Fibonacci Sequence

== Theorem ==
Let $\FF = \sequence {a_n}$ be a general Fibonacci sequence generated by the parameters $r, s, t, u$:
:$a_n = \begin{cases}
r & : n = 0 \\
s & : n = 1 \\
t a_{n - 2} + u a_{n - 1} & : n > 1
\end{cases}$
Let:
:$d = \gcd \set {r, s}$
where $\gcd$ denotes greatest common divisor.
Let $f = \gcd \set {a_m, a_{m - 1} }$ for some $m \in \N$.
Let $\gcd \set {f, t} = 1$.
Then:
:$f \divides d$
== Proof ==
Proof by induction:
Let $\map P m$ be the proposition:
:$\gcd \set {f_m, t} = 1 \implies f_m = d$
where $f_m = \gcd \set {a_m, a_{m - 1} }$.
For clarity, we have indexed $f$.
=== Basis for the Induction ===
For $m = 1$:
:$f_1 = \gcd \set {a_1, a_0} = \gcd \set {s, r} = d$
This is the basis for the induction.
=== Induction Hypothesis ===
Now we assume that $\map P k$ is true for some $k \in \N$.
In other words, this is our induction hypothesis:
:$\gcd \set {f_k, t} = 1 \implies f_k = d$
where $f_k = \gcd \set {a_k, a_{k - 1} }$.
Now we need to show that $\map P {k + 1}$ is true, that is:
:$\gcd \set {f_{k + 1}, t} = 1 \implies f_{k + 1} = d$
where $f_{k + 1} = \gcd \set {a_{k + 1}, a_k}$.
=== Induction Step ===
This is our induction step:
Suppose that $\gcd \set {f_{k + 1}, t} = 1$.
Then:
By the two results above, we have:
:$f_{k + 1} = \gcd \set {t, a_k} f_k = f_k$
so we have $\gcd \set {f_k, t} = \gcd \set {f_{k + 1}, t} = 1$ as well.
By the induction hypothesis and Modus Ponendo Ponens:
:$f_k = d$
and thus:
:$f_{k + 1} = f_k = d$
so $\map P {k + 1}$ is true.
By the Principle of Mathematical Induction, $\map P m$ is true for all $m \in \N$.
Hence the result.
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $12 \ \text{(b)}$
Category:Greatest Common Divisor
Category:Fibonacci Numbers
GCD of Fibonacci Numbers

== Theorem ==
Let $F_k$ be the $k$th Fibonacci number.
Then:
:$\forall m, n \in \Z_{> 2}: \gcd \set {F_m, F_n} = F_{\gcd \set {m, n} }$
where $\gcd \set {a, b}$ denotes the greatest common divisor of $a$ and $b$.
== Proof ==
From the initial definition of Fibonacci numbers, we have:
:$F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3$
, let $m \le n$.
Let $h$ be $\gcd \set {m, n}$.
Let $a$ and $b$ be integers such that $m = h a$ and $n = \map h {a + b}$.
$a$ and $a + b$ are coprime by Integers Divided by GCD are Coprime.
Therefore, $a$ and $b$ are coprime by Integer Combination of Coprime Integers.
Let $u$ and $v$ be integers such that $F_{h a} = u F_h$ and $F_{h b} = v F_h$, whose existence is proved by Divisibility of Fibonacci Number.
We have that $F_{h a}$ and $F_{h a - 1}$ are coprime by Consecutive Fibonacci Numbers are Coprime.
Therefore, $u$ and $F_{h a - 1}$ are coprime by Divisor of One of Coprime Numbers is Coprime to Other.
Therefore:
:$\forall m, n \in \Z_{>2} : \gcd \set {F_m, F_n} = \gcd \set {F_m, F_{n - m} }$
This can be done recurrently to produce the result, in a fashion similar to the Euclidean Algorithm. 
Since $a$ and $b$ are coprime, the result would be $\gcd \set {F_h, F_h}$.
Therefore:
:$\forall m, n > 2 : \gcd \set {F_m, F_n} = F_{\gcd \set {m, n} }$
== Historical Note ==
== Sources ==
* : $5$
* : $\S 1.2.8$: Fibonacci Numbers: $(7)$
* : $5$
Category:Fibonacci Numbers
Category:Greatest Common Divisor
GCD of Generators of General Fibonacci Sequence is Divisor of All Terms

== Theorem ==
Let $\FF = \sequence {a_n}$ be a general Fibonacci sequence generated by the parameters $r, s, t, u$:
:$a_n = \begin{cases}
r & : n = 0 \\
s & : n = 1 \\
t a_{n - 2} + u a_{n - 1} & : n > 1
\end{cases}$
Let:
:$d = \gcd \set {r, s}$
where $\gcd$ denotes greatest common divisor.
Then:
:$\forall n \in \Z_{>0}: d \divides a_n$
== Proof ==
From the construction of a general Fibonacci sequence, $a_n$ is an integer combination of $r$ and $s$.
From Set of Integer Combinations equals Set of Multiples of GCD, $a_n$ is divisible by $\gcd \set {r, s}$.
Hence the result.
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $12 \ \text{(a)}$
Category:Greatest Common Divisor
Category:Fibonacci Numbers
GCD of Integer and Divisor

== Theorem ==
Let $a, b \in \Z_{>0}$ be strictly positive integers.
Then:
:$a \divides b \implies \gcd \set {a, b} = a$
== Proof ==
We have:
:$a \divides b$ 
:$a \divides a$ from Integer Divides Itself.
Thus $a$ is a common divisor of $a$ and $b$.
Then from Absolute Value of Integer is not less than Divisors:
:$\forall x \in \Z: x \divides a \implies x \le \size a$
As $a$ and $b$ are both positive, the result follows.
== Sources ==
* : $\text {2-2}$ Divisibility: Example $\text {2-6}$
Category:Greatest Common Divisor
GCD of Integer and its Negative

== Theorem ==
Let $a \in \Z$ be an integer.
Then:
:$\gcd \set {a, -a} = \size a$
where:
:$\gcd$ denotes greatest common divisor
:$\size a$ denotes the absolute value of $a$.
== Proof ==
From Integer Divisor Results, the divisors of $a$ include $a$ itself.
From Integer Divides its Negative, $a \divides \paren {-a}$.
Thus we have:
:$a \divides a$
and:
:$a \divides -a$
and so:
:$\gcd \set {a, -a} \ge \size a$
From Absolute Value of Integer is not less than Divisors, there is no divisor of $a$ which is greater than $a$.
That is:
:$\gcd \set {a, -a} \le \size a$
Hence the result.
Category:Greatest Common Divisor
GCD of Integer with Integer + n

== Theorem ==
Let $a \in \Z$ be an integer.
Let $n \in \Z_{\ge 0}$ be a positive integer.
Then:
:$\gcd \set {a, a + n} \divides n$
where:
:$\gcd$ denotes the greatest common divisor
:$\divides$ denotes divisibility.
== Proof ==
Let $g = \gcd \set {a, a + n}$.
By definition of $\gcd$, there exist $b, b' \in \Z$ such that:
:$a = g b$
:$a + n = g b'$
Therefore:
Since $b' - b \in \Z$, it follows by definition of divisibility that:
:$g \divides n$
as desired.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $12$
Category:Greatest Common Divisor
GCD of Integers with Common Divisor

== Theorem ==
Let $a, b \in \Z$ be integers such that not both $a = 0$ and $b = 0$.
Let $k \in \Z_{>0}$ be a strictly positive integer.
Then:
:$\gcd \set {k a, k b} = k \gcd \set {a, b}$
where $\gcd$ denotes the greatest common divisor.
=== Corollary ===
== Proof 1 ==
== Proof 2 ==
== Examples ==
Category:GCD of Integers with Common Divisor
Category:Greatest Common Divisor
GCD of Integers with Common Divisor/Corollary

== Theorem ==
Let $a, b \in \Z$ be integers such that not both $a = 0$ and $b = 0$.
Let $k \in \Z_{\ne 0}$ be a non-zero integer.
Then:
:$\gcd \set {k a, k b} = \size k \gcd \set {a, b}$
where $\gcd$ denotes the greatest common divisor.
== Proof ==
From GCD of Integers with Common Divisor the case where $k > 0$ has been demonstrated.
It remains to demonstrate the case where $k < 0$.
Indeed:
:$-k = \size k > 0$
and so:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:GCD of Integers with Common Divisor
GCD of Integers with Common Divisor/Proof 1

== Theorem ==
== Proof ==
Consider the demonstration of the operation of the Euclidean Algorithm applied to $a$ and $b$.
Let each equation be multiplied by $k$.
We have:
This is the operation of the Euclidean Algorithm applied to $k a$ and $k b$.
Hence the greatest common divisor is the last non-zero remainder $r_n k$.
That is:
:$\gcd \set {k a, k b} = k \gcd \set {a, b}$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Theorem $2 \text - 7$
Category:GCD of Integers with Common Divisor
GCD of Polynomials does not depend on Base Field

== Theorem ==
Let $E / F$ be a field extension.
Let $P, Q \in F \sqbrk X$ be polynomials.
Let:
:$\gcd \set {P, Q} = R$ in $F \sqbrk X$
:$\gcd \set {P, Q} = S$ in $E \sqbrk X$.
Then $R = S$.
In particular, $S \in F \sqbrk X$.
== Proof ==
By definition of greatest common divisor:
:$R \divides S$ in $E \sqbrk X$
By Polynomial Forms over Field is Euclidean Domain, there exist $A, B \in F \sqbrk X$ such that:
:$A P + B Q = R$
Because $S \divides P, Q$:
:$S \divides R$ in $E \sqbrk X$
By $R \divides S$ and $S \divides R$:
:$R = S$
Category:Field Theory
Category:Polynomial Theory
Category:Greatest Common Divisor
GCD of Sum and Difference of Coprime Integers

== Theorem ==
Let $a, b \in \Z$ be coprime integers.
Then:
:$\gcd \set {a + b, a - b} = 1 \text { or } 2$
where:
:$\gcd$ denotes greatest common divisor.
== Proof ==
Let:
:$d = \gcd \set {a + b, a - b}$
We have:
Hence:
:$1 \le d \le 2$
and the result follows.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $4 \ \text {(a)}$
Category:Greatest Common Divisor
Category:Coprime Integers
GCD of Sum and Difference of Integers

== Theorem ==
:$\gcd \set {a + b, a - b} \ge \gcd \set {a, b}$
== Proof ==
Let $d = \gcd \set {a, b}$.
Then by definition of greatest common divisor:
:$d \divides a \land d \divides b$
From Common Divisor Divides Integer Combination:
:$d \divides \paren {a + b} \land d \divides \paren {a - b}$
By definition of common divisor:
:$d \divides \gcd \set {a + b, a - b}$
Hence from Absolute Value of Integer is not less than Divisors:
:$d \le \gcd \set{a + b, a - b}$
== Sources ==
* : $\text {2-2}$ Divisibility: Exercise $8$
Category:Greatest Common Divisor
GCD with One Fixed Argument is Multiplicative Function

== Theorem ==
Let:
:$a, b, c \in \Z: b \perp c$
where $b \perp c$ denotes that $b$ is coprime to $c$.
Then:
:$\gcd \set {a, b} \gcd \set {a, c} = \gcd \set {a, b c}$
That is, GCD is multiplicative.
== Proof ==
Category:Greatest Common Divisor
Category:Examples of Multiplicative Functions
GCD with Prime

== Theorem ==
Let $p$ be a prime number.
Then:
$\quad \forall n \in \Z: \gcd \set {n, p} = \begin {cases}
p & : p \divides n \\
1 & : p \nmid n
\end {cases}$
== Proof ==
The only divisors of $p$ are $1$ and $p$ itself by definition.
$\gcd \set {n, p} = p$ $p$ divides $n$.
Hence the result.
Category:Greatest Common Divisor
Category:Prime Numbers
GCD with Remainder

== Theorem ==
Let $a, b \in \Z$.
Let $q, r \in \Z$ such that $a = q b + r$.
Then:
:$\gcd \set {a, b} = \gcd \set {b, r}$
where $\gcd \set {a, b}$ is the greatest common divisor of $a$ and $b$.
== Proof ==
The argument works the other way about:
Thus:
:$\gcd \set {a, b} = \gcd \set {b, r}$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm
Category:Greatest Common Divisor
GCD with Self

== Theorem ==
Let $a \in \Z$ be an integer such that $a \ne 0$.
Then:
:$\gcd \set {a, a} = \size a$
where $\gcd$ denotes greatest common divisor (GCD).
== Proof ==
From Integer Divides its Absolute Value:
:$\size a \divides a$
Then from Absolute Value of Integer is not less than Divisors:
:$\forall x \in \Z: x \divides a \implies x \le \size a$
The result follows by definition of GCD.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $10$
Category:Greatest Common Divisor
GCD with Zero

== Theorem ==
Let $a \in \Z$ be an integer such that $a \ne 0$.
Then:
:$\gcd \set {a, 0} = \size a$
where $\gcd$ denotes greatest common divisor (GCD).
== Proof ==
Follows from:
:Integer Divides Zero
and:
:GCD for Negative Integers.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $10$
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $13$
Category:Greatest Common Divisor
GM-HM Inequality

== Theorem ==
Let $x_1, x_2, \ldots, x_n \in \R_{> 0}$ be strictly positive real numbers.
Let $G_n$ be the geometric mean of $x_1, x_2, \ldots, x_n$.
Let $H_n$ be the harmonic mean of $x_1, x_2, \ldots, x_n$.
Then:
:$G_n \ge H_n$
== Proof 1 ==
== Proof 2 ==
== Also see ==
* AM-HM Inequality
* Cauchy's Mean Theorem
== Sources ==
* : $3$: Elementary Analytic Methods: $3.2$ Inequalities: Relation Between Arithmetic, Geometric, Harmonic and Generalized Means: $3.2.1$
* : $\S 36$: Inequalities: Inequalities involving Arithmetic, Geometric and Harmonic Means: $36.4$
* 
* 
* 
Category:GM-HM Inequality
Category:Inequalities
Category:Geometric Mean
Category:Harmonic Mean
GM-HM Inequality/Proof 1

== Theorem ==
== Proof ==
Let ${G_n}'$ denotes the geometric mean of the reciprocals of $x_1, x_2, \ldots, x_n$.
By definition of harmonic mean, we have that:
:$\ds \dfrac 1 {H_n} := \frac 1 n \paren {\sum_{k \mathop = 1}^n \frac 1 {x_k} }$
That is, $\dfrac 1 {H_n}$ is the arithmetic mean of the reciprocals of $x_1, x_2, \ldots, x_n$.
Then:
Category:GM-HM Inequality
GM-HM Inequality/Proof 2

== Theorem ==
== Proof ==
For $p \in \R$, let $\map {M_p} {x_1, x_2, \ldots, x_n}$ denote the Hölder mean with exponent $p$ of $x_1, x_2, \ldots, x_n$.
By definition of Hölder Mean with $p = 0$:
:$\map {M_0} {x_1, x_2, \ldots, x_n} = \map G {x_1, x_2, \ldots, x_n}$
From Hölder Mean for Exponent -1 is Harmonic Mean:
:$\map {M_{-1} } {x_1, x_2, \ldots, x_n} = \map G {x_1, x_2, \ldots, x_n}$
The result follows from Inequality of Hölder Means:
:$-1 < 0 \implies \map {M_{-1} } {x_1, x_2, \ldots, x_n} < \map {M_0} {x_1, x_2, \ldots, x_n}$
unless $x_k = 0$ for some $k \in \set {1, 2, \ldots, n}$ or $x_1 = x_2 = \cdots = x_n$, in which case:
:$\map {M_{-1} } {x_1, x_2, \ldots, x_n} = \map {M_0} {x_1, x_2, \ldots, x_n}$
Hence the result.
Category:GM-HM Inequality
GO-Space Embeds as Closed Subspace of Linearly Ordered Space

== Theorem ==
Let $\struct {X, \preceq_X, \tau_X}$ be a generalized ordered space.
Then there is a linearly ordered space $\struct {Y, \preceq_Y, \tau_Y}$ and a mapping $\phi: X \to Y$ such that $\phi$ is a topological embedding and an order embedding, and $\phi \sqbrk {X}$ is closed in $Y$.
== Proof ==
By GO-Space Embeds Densely into Linearly Ordered Space, there is a linearly ordered space $\struct {W, \preceq_W, \tau_W}$ and a mapping $\psi:X \to W$ which is an order embedding and a topological embedding.
, assume $X$ is a subspace of $W$.
Let $Y = \set {\tuple {x, 0}: x \in X} \cup \paren {W \setminus X} \times \Z$.
Let $\preceq_Y$ be the restriction to $Y$ of the lexicographic ordering on $W \times \Z$.
Let $\tau_Y$ be the $\preceq_Y$-order topology on $Y$.
Let $\phi: X \to Y$ be given by $\map \phi x = \tuple {x, 0}$.
$\phi$ is clearly an order embedding.
Next, we show that it is a topological embedding:
If $$
Finally, we show that $\phi \sqbrk {X}$ is closed in $Y$:
Category:Generalized Ordered Spaces
Category:Linearly Ordered Spaces
Galileo's Paradox

== Theorem ==
The natural numbers $\N$ are in one-to-one correspondence with their squares:
That is, the mapping:
:$\forall n \in \N: f: n \mapsto n^2$
is a bijection.
Hence the set of square numbers is equinumerous to the set of natural numbers.
That is, a set is equinumerous to one of its proper subsets.
== Resolution ==
This is a veridical paradox.
$\N$ is an infinite set.
A defining property of an infinite set is that it possesses proper subsets with which it is equinumerous.
== Also see ==
* Infinite Set is Equivalent to Proper Subset
== Historical Note ==
== Sources ==
* : Chapter $\text {A}.33$: Weierstrass (): Footnote $5$
Category:Veridical Paradoxes
Galileo's Paradox/Historical Note

== Historical Note on Galileo's Paradox ==
 initially raised this paradox in his (Discourses and Mathematical Demonstrations Relating to Two New Sciences) of $1638$, during his discussions of continuity.
The question was raised again by in his posthumous ($1851$) (The Paradoxes of the Infinite), where he indicated that he was perfectly comfortable with it, and gave many other examples of how an infinite set is equivalent to a proper subset of it.
 and later used this property of an infinite set to actually define the concept.
From this philosophical standpoint, then went on to create his theory of infinite cardinals.
== Sources ==
* : Chapter $\text {A}.33$: Weierstrass (): Footnote $5$
Category:Historical Notes