nyuuzyou/wikis huggingface dataset:
Futurama Theorem/Historical Note

== Historical Note on Futurama Theorem ==
This theorem was developed and proved by American comedian for an episode of the television show titled .
In the episode, there exists a device which can switch any two peoples minds.
However, it is discovered that no two bodies can be switched more than once.
The question is asked:
:Once a switch has happened, can all the minds be returned to their proper bodies?
In the episode, it is claimed that no matter how permuted a group becomes, all minds can be returned to their proper bodies with at most two additional individuals.
Category:Historical Notes
Fuzzy Intersection is Commutative

== Theorem ==
Fuzzy intersection is commutative.
== Proof ==
Let $\textbf A = \struct{A, \mu_A}$ and $\textbf B = \struct{B, \mu_B}$ be fuzzy sets.
=== Proving Domain Equality ===
By the definition of fuzzy intersection the domain of $\textbf A \cap \textbf B$ is:
:$A \cap B$
Similarly the domain of $\textbf B \cap \textbf A$ is:
:$B \cap A$
By Intersection is Commutative:
:$A \cap B = B \cap A$
Hence their domains are equal.
=== Proving Membership Function Equality ===
==== Proving Form Equality ====
By the definition of fuzzy intersection the membership function of $\textbf A \cap \textbf B$ is of the form:
:$\mu:A \cap B \to \closedint {0} {1}$
Similarly, the membership function of $\textbf B \cap \textbf A$ is of the form:
:$\mu:B \cap A \to \closedint {0} {1}$
By Intersection is Commutative this is the same as:
:$\mu:A \cap B \to \closedint {0} {1}$
Hence the membership functions are of the same form.
==== Proving Rule Equality ====
Hence the membership functions have the same rule.
Category:Fuzzy Set Theory
G-Delta Set is not necessarily Open Set

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Let $X$ be a $G_\delta$ set of $T$.
Then it is not necessarily the case that $X$ is a open set of $T$.
== Proof ==
Let $T = \struct {S, \tau}$ be a finite complement topology on an uncountable set $S$.
Let $X \subseteq S$ be a $G_\delta$ set of $T$.
From $F_\sigma$ and $G_\delta$ Subsets of Uncountable Finite Complement Space:
:$X$ is neither open nor closed in $T$.
Hence the result.
== Sources ==
* : Part $\text I$: Basic Definitions: Section $1$: General Introduction
Category:G-Delta Sets
Category:Open Sets
G-Delta Sets Closed under Intersection

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Let $G, G'$ be $G_\delta$ sets of $T$.
Then their intersection $G \cap G'$ is also a $G_\delta$ set of $T$.
== Proof ==
By definition of $G_\delta$ set, there exist sequences $\sequence {U_n}_{n \mathop \in \N}$ and $\sequence {U'_n}_{n \mathop \in \N}$ of open sets of $T$ such that:
:$G = \ds \bigcap_{n \mathop \in \N} U_n$
:$G' = \ds \bigcap_{n \mathop \in \N} U'_n$
By General Self-Distributivity of Intersection, we have:
:$G \cap G' = \ds \bigcap_{n \mathop \in \N} \paren {U_n \cap U'_n}$
By Intersection of Closed Sets is Closed in Topological Space, $U_n \cap U'_m$ is closed, for all $n, m \in \N$.
Thus $G \cap G'$ is seen to be a $G_\delta$ set.
== Also see ==
* $G_\delta$ Sets Closed under Union
* $F_\sigma$ Sets Closed under Intersection
Category:G-Delta Sets
G-Delta Sets Closed under Union

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Let $G, G'$ be $G_\delta$ sets of $T$.
Then their union $G \cup G'$ is also a $G_\delta$ set of $T$.
== Proof ==
By definition of $G_\delta$ set, there exist sequences $\sequence {U_n}_{n \mathop \in \N}$ and $\sequence {U'_n}_{n \mathop \in \N}$ of open sets of $T$ such that:
:$G = \ds \bigcap_{n \mathop \in \N} U_n$
:$G' = \ds \bigcap_{n \mathop \in \N} U'_n$
Now compute:
By axiom $(1)$ of a topology, $U_n \cup U'_m$ is open, for all $n, m \in \N$.
By Cartesian Product of Countable Sets is Countable, $\N \times \N$ is countable.
Thus $G \cup G'$ is seen to be a $G_\delta$ set.
== Also see ==
* $G_\delta$ Sets Closed under Intersection
* $F_\sigma$ Sets Closed under Union
Category:G-Delta Sets
G-Delta Sets form Lattice

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Let $\GG$ be the collection of all $G_\delta$ sets of $T$.
Then $\struct {\GG, \subseteq}$ is a lattice, where $\subseteq$ denotes the subset relation.
== Proof ==
From Subset Relation is Ordering, $\subseteq$ is an ordering on $\GG$.
Let $G, G'$ be $G_\delta$ sets of $T$.
We have $G_\delta$ Sets Closed under Union, so that $G \cup G' \in \GG$.
From Union is Smallest Superset and Subset of Union, it follows that $G \cup G'$ is the supremum of $G$ and $G'$.
Similarly, we have $G_\delta$ Sets Closed under Intersection, and so $G \cap G' \in \GG$.
From Intersection is Largest Subset and Intersection is Subset, it follows that $G \cap G'$ is the infimum of $G$ and $G'$.
Thus any two elements of $\GG$ are seen to have both a supremum and an infimum in $\GG$.
Hence $\struct {\GG, \subseteq}$ is a lattice.
== Also see ==
* $F_\sigma$ Sets form Lattice
Category:G-Delta Sets
Category:Lattice Theory
G-Delta Sets in Indiscrete Topology

== Theorem ==
Let $T = \struct {S, \set {\O, S} }$ be an indiscrete topological space.
Let $H \subseteq S$.
$H$ is a $G_\delta$ ($G$-delta) set of $T$ either $H = S$ or $H = \O$.
== Proof ==
A $G_\delta$ set is a set which can be written as a countable intersection of open sets of $S$.
Hence the only $G_\delta$ sets of $T$ are made from intersections of $T$ and $\O$.
So $T$ and $\O$ are the only $G_\delta$ sets of $T$.
== Sources ==
* : Part $\text {II}$: Counterexamples: $4$. Indiscrete Topology: $2$
Category:Indiscrete Topology
Category:G-Delta Sets
G-Module is Irreducible iff no Non-Trivial Proper Submodules

== Theorem ==
Let $\struct {G, \circ}$ be a finite group.
Let $\struct {V, \phi}$ be a $G$-module.
Then $V$ is an irreducible $G$-module $V$ has no non-trivial proper $G$-submodules.
== Proof ==
=== Necessary Condition ===
 that $V$ is an irreducible $G$-module, but it has a non-trivial proper $G$-submodule.
By the definition irreducible, its associated representation is irreducible.
Let this representation be denoted:
:$\tilde \phi = \rho: G \to \GL V$
In Correspondence between Linear Group Actions and Linear Representations it is defined as:
:$\map {\map \rho g} v = \map \phi {g, v}$
where $g \in G$ and $v \in V$.
Since $V$ has a proper $G$-submodule, there exists $W$ a non-trivial proper vector subspace such that:
:$\phi \sqbrk {G, W} \subseteq W$ 
and so:
$\rho \sqbrk G W \subseteq W$
Hence $W$ is invariant by every linear operators in $\set {\map \rho g: g \in G}$.
By definition, $\rho$ cannot be irreducible.
Thus we have reached a contradiction, and $V$ has then no non-trivial proper $G$-submodules.
=== Sufficient Condition ===
 now that $V$ has no proper $G$-submodules, but it is a reducible $G$-module.
By the definition of reducible $G$-module, it follow that its associated representation is reducible.
Let this representation be denoted:
:$\tilde \phi = \rho: G \to \GL V$
From the definition of reducible representation, it follows that there exists a vector space $W$ of $V$.
This is invariant under all the linear operators in $\set {\map \rho g: g \in G}$.
Then:
:$\phi \sqbrk {G, W} = \rho \sqbrk G W \subseteq W$
which is the definition of a $G$-submodule of $V$.
By our assumption, $V$ has no non-trivial proper $G$-submodules.
Thus we have reached a contradiction and $V$ must be then an irreducible $G$-module.
Category:Representation Theory
G-Submodule Test

== Theorem ==
Let $\struct {V, \phi}$ be a $G$-module over a field $k$.
Let $W$ be a vector subspace of $V$.
Let $\phi_W: G \times W \to V$ denote the restriction of $\phi$ to $G \times W$.
Then:
:$\struct {W, \phi_W}$ is a $G$-submodule of $V$
:
:$\map \phi {G, W} \subseteq W$
== Proof ==
=== Necessary Condition ===
Let $W$ be a $G$-submodule of $V$.
Hence by definition $\phi_W: G \times W \to W$ is a linear action on $W$.
Also by definition:
:$\map {\phi_W} {G, W} = \map \phi {G, W} \subseteq W$
=== Sufficient Condition ===
Let:
:$\map \phi {G, W} = \map {\phi_W} {G, W} \subseteq W$
We have that $\phi_W: G \times W \to W$ is a well-defined mapping.
We need to check if $\phi_W$ is a linear action on $W$:
Assume $a, b \in W$ and $g \in G$.
In particular:
:$a, b \in V$
and so:
Further, let $\lambda \in k$ and $g \in G$.
Then:
Thus $W$ is a $G$-submodule of $V$.
Category:Representation Theory
G-Tower is Closed under Chain Unions

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Then $M$ is closed under chain unions.
== Proof ==
By definition:
:a $g$-tower is a class which is minimally superinductive under $g$
:a class which is minimally superinductive under $g$ is superinductive under $g$
:a superinductive class is closed under chain unions.
Hence the result.
Category:G-Towers
Category:Closure under Chain Unions
G-Tower is Closed under Mapping

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Then $M$ is closed under $g$:
:$\forall x: \paren {x \in M \implies \map g x \in M}$
== Proof ==
By definition:
:a $g$-tower is a class which is minimally superinductive under $g$
:a class which is minimally superinductive under $g$ is superinductive under $g$
:a superinductive class is inductive under $g$
:an inductive class under $g$ is closed under $g$.
Hence the result.
Category:G-Towers
Category:Closedness under Mappings
G-Tower is G-Ordered

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Then $M$ is $g$-ordered.
== Proof ==
Recall the definition of a $g$-ordered class:
$M$ is a $g$-ordered class $M$ is well-ordered by the subset relation such that:
So, let $M$ be a $g$-tower.
From $g$-Tower is Well-Ordered under Subset Relation:
:$M$ is well-ordered under the subset relation.
From $g$-Tower is Well-Ordered under Subset Relation: Empty Set:
:$\O$ is the smallest element of $M$.
From $g$-Tower is Well-Ordered under Subset Relation: Successor of Non-Greatest Element:
:Let $x \in M$ such that $x$ is not the greatest element of $M$.
:Then the immediate successor of $x$ is $\map g x$.
From $g$-Tower is Well-Ordered under Subset Relation: Union of Limit Elements:
:Let $x \in M$ be a limit element of $M$.
:Then:
::$x = \bigcup x^\subset$
:where $\bigcup x^\subset$ denotes the union of the lower section of $x$.
The result follows.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {III}$ -- The existence of minimally superinductive classes: $\S 8$ Another characterization of $g$-sets
Category:G-Towers
Category:G-Ordered Classes
G-Tower is Nest

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Then $M$ is a nest.
== Proof ==
We need to show that:
:$\forall x, y \in M: x \subseteq y$ or $y \subseteq x$
First some lemmata:
=== Lemma 1 ===
That is:
=== Lemma 2 ===
But as $g: M \to M$ is a progressing mapping:
:$\forall x \in M: x \subseteq \map g x$
The result follows by Subset Relation is Transitive.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 2$ Superinduction and double superinduction: Theorem $2.3$
Category:G-Tower is Nest
Category:G-Towers
Category:Nests
G-Tower is Nest/Lemma 1

== Lemma for $g$-Tower is Nest ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $\RR$ be a relation defined as:
:$\forall x, y \in M: \tuple {x, y} \in \RR \iff \map g x \subseteq y \lor y \subseteq x$
where $\lor$ denotes disjunction (inclusive "or").
Then $\RR$ satisfies the $3$ conditions $\text D_1$, $\text D_2$ and $\text D_3$ of the Double Superinduction Principle.
== Proof ==
Conditions $\text D_1$ and $\text D_2$ are proven by the Progressing Function Lemma.
It remains to demonstrate that $\text D_3$ is satisfied.
Let $C$ be a chain (or any set, for that matter) such that $\tuple {x, y} \in \RR$ for every $y \in C$.
Thus, for every $y \in C$, either $\map g x \subseteq y$ or $y \subseteq x$.
If $y \subseteq x$ holds for every $y \in C$ then $\ds \bigcup C \subseteq x$.
Hence $\tuple {x, \ds \bigcup C} \in \RR$.
If it is not the case that $y \subseteq x$ holds for every $y \in C$, then there exists at least one $y \in C$ such that $\map g x \subseteq y$.
Hence as $y \subseteq \ds \bigcup C$ it follows that $\map g x \subseteq \ds \bigcup C$.
Hence again $\tuple {x, \ds \bigcup C} \in \RR$.
The result follows.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 2$ Superinduction and double superinduction: Lemma $2.2$
Category:G-Tower is Nest
G-Tower is Nest/Lemma 2

== Lemma for $g$-Tower is Nest ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Then:
:$\forall x, y \in M: \map g x \subseteq y \lor y \subseteq x$
== Proof ==
First a lemma:
=== Lemma 1 ===
That is:
By definition of $g$-tower:
:$M$ is minimally superinductive under $g$.
Hence by the Principle of Superinduction:
:$\forall x, y \in M: \tuple {x, y} \in \RR$
That is:
:$\forall x, y \in M: \map g x \subseteq y \lor y \subseteq x$
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 2$ Superinduction and double superinduction: Theorem $2.3$
Category:G-Tower is Nest
G-Tower is Properly Well-Ordered under Subset Relation

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Then $M$ is properly well-ordered under the subset relation.
== Proof ==
From $g$-Tower is Well-Ordered under Subset Relation, $\subseteq$ is a well-ordering on $M$.
Let $L$ be a proper lower section of $M$.
From Proper Lower Section under Well-Ordering is Initial Segment, $L$ is an initial segment $x^\subset$ of $M$ for some $x \in M$.
By the definition of the structure of a $g$-tower, each element of $x$ is a subset of $x$.
Hence:
:$x^\subset \subseteq \powerset x$
From the Axiom of Powers, $\powerset x$ is a set.
Hence from Subclass of Set is Set, $x^\subset$ is also a set.
The result follows from the definition of properly well-ordered.
== Sources ==
* : Chapter $6$: Order Isomorphism and Transfinite Recursion: $\S 1$ A few preliminaries: Proposition $1.3$
Category:Proper Well-Orderings
Category:G-Towers
G-Tower is Well-Ordered under Subset Relation/Corollary

== Corollary to $g$-Tower is Well-Ordered under Subset Relation ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Let $y \in M$ other than $\O$.
Then the strict lower closure $y^\subset$ of $y$ is non-empty and exactly one of the following conditions holds:
:$(\text C 1): \quad y^\subset$ has a greatest element $x$ and $\map g x = y$
:$(\text C 2): \quad y^\subset$ has no greatest element $x$ and $\bigcup y^\subset = y$
== Proof ==
We have $y \ne \O$.
Then $y$ is not the smallest element of $M$.
Hence $\O \in y^\subset$ and $y^\subset$ is non-empty.
The result follows from $g$-Tower is Well-Ordered under Subset Relation, taking $A = \set y$.
The smallest element of $\set y$ is of course $y$ itself.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 3$ The well ordering of $g$-towers: Corollary $3.2$
Category:Lower Closures
Category:G-Tower is Well-Ordered under Subset Relation
G-Tower is Well-Ordered under Subset Relation/Empty Set

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
$\O$ is the smallest element of $M$.
== Proof ==
Follows directly from $g$-Tower is Well-Ordered under Subset Relation.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 3$ The well ordering of $g$-towers: Theorem $3.3 \ (1)$
Category:G-Tower is Well-Ordered under Subset Relation
G-Tower is Well-Ordered under Subset Relation/Successor of Non-Greatest Element

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Let $x \in M$ such that $x$ is not the greatest element of $M$.
Then the immediate successor of $x$ is $\map g x$.
== Proof ==
We have that $g$-Tower is Well-Ordered under Subset Relation.
Let $x \in M$ such that $x$ is not the greatest element of $M$.
Then from Fixed Point of $g$-Tower is Greatest Element:
:$x \ne \map g x$
Hence:
:$x \subsetneqq \map g x$
Hence by the Sandwich Principle for $g$-Towers, there is no $y \in M$ such that:
:$x \subsetneqq y \subsetneqq \map g x$
Hence $\map g x$ is the immediate successor of $x$.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 3$ The well ordering of $g$-towers: Theorem $3.3 \ (2)$
Category:G-Tower is Well-Ordered under Subset Relation
G-Tower is Well-Ordered under Subset Relation/Union of Limit Elements

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a progressing mapping on $M$.
Let $M$ be a $g$-tower.
Let $x \in M$ be a limit element of $M$.
Then:
:$x = \bigcup x^\subset$
where $\bigcup x^\subset$ denotes the union of the lower section of $x$.
== Proof ==
We have that $g$-Tower is Well-Ordered under Subset Relation.
Let $x \in M$ be a limit element of $M$.
Then by definition $x$ is not an immediate successor element.
Hence by $g$-Tower is Well-Ordered under Subset Relation: Successor of Non-Greatest Element:
:there exists no $y \in M$ such that $x = \map g y$
otherwise $x$ would be the immediate successor of $y$.
Hence there is no $y \in x^\subset$ such that $x = \map g y$.
Thus condition $(\text C 1)$ of $g$-Tower is Well-Ordered under Subset Relation: Corollary does not hold.
Hence condition $(\text C 2)$ of $g$-Tower is Well-Ordered under Subset Relation: Corollary does hold.
That is:
:$\bigcup x^\subset = x$
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 3$ The well ordering of $g$-towers: Theorem $3.3 \ (3)$
Category:G-Tower is Well-Ordered under Subset Relation
GCD and LCM Distribute Over Each Other

== Theorem ==
Let $a, b, c \in \Z$.
Then:
: $\lcm \set {a, \gcd \set {b, c} } = \gcd \set {\lcm \set {a, b}, \lcm \set {a, c} }$
: $\gcd \set {a, \lcm \set {b, c} } = \lcm \set {\gcd \set {a, b}, \gcd \set {a, c} }$
That is, greatest common divisor and lowest common multiple are distributive over each other.
== Proof ==
=== LCM Distributive over GCD ===
Let $p_s$ be any of the prime divisors of $a, b$ or $c$, and let $s_a, s_b$ and $s_c$ be its exponent in each of those numbers.
Let $x = \lcm \set {a, \gcd \set {b, c} }$.
Then from GCD and LCM from Prime Decomposition, the exponent of $p_s$ in $x$ is $\max \set {s_a, \min \set {s_b, s_c} }$.
From Max and Min Operations are Distributive over Each Other, $\max$ distributes over $\min$.
Therefore:
: $\max \set {s_a, \min \set {s_b, s_c} } = \min \set {\max \set {s_a, s_b}, \max \set {s_a, s_c} }$
Hence it follows that LCM is distributive over GCD.
=== GCD Distributive over LCM ===
Let $p_s$ be any of the prime divisors of $a, b$ or $c$, and let $s_a, s_b$ and $s_c$ be its exponent in each of those numbers.
Let $x = \gcd \set {a, \lcm \set {b, c} }$.
Then from GCD and LCM from Prime Decomposition, the exponent of $p_s$ in $x$ is $\min \set {s_a, \max \set {s_b, s_c} }$.
From Max and Min Operations are Distributive over Each Other, $\min$ distributes over $\max$.
Therefore:
: $\min \set {s_a, \max \set {s_b, s_c} } = \max \set {\min \set {s_a, s_b}, \min \set {s_a, s_c} }$
and the result follows.
Hence it follows that GCD is distributive over LCM.
== Sources ==
* : Chapter $1$: Properties of the Natural Numbers: $\S 23 \epsilon$
Category:Greatest Common Divisor
Category:Lowest Common Multiple
Category:Examples of Distributive Operations
GCD and LCM from Prime Decomposition

== Theorem ==
Let $m, n \in \Z$.
Let:
:$m = p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r}$
:$n = p_1^{l_1} p_2^{l_2} \dotsm p_r^{l_r}$
:$p_i \divides m \lor p_i \divides n, 1 \le i \le r$.
That is, the primes given in these prime decompositions may be divisors of either of the numbers $m$ or $n$.
Note that if one of the primes $p_i$ does not appear in the prime decompositions of either one of $m$ or $n$, then its corresponding index $k_i$ or $l_i$ will be zero.
Then the following results apply:
:$\gcd \set {m, n} = 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} }$
:$\lcm \set {m, n} = p_1^{\max \set {k_1, l_1} } p_2^{\max \set {k_2, l_2} } \ldots p_r^{\max \set {k_r, l_r} }$
== Proof ==
The proof of these results can be found in:
:GCD from Prime Decomposition
:LCM from Prime Decomposition
Category:Greatest Common Divisor
Category:Lowest Common Multiple
Category:Prime Numbers
GCD equals GCD with Product of Coprime Factor

== Theorem ==
Let $a, b, c \in \Z$ be integers.
Let:
:$a \perp b$
where $\perp$ denotes coprimality.
Then:
:$\gcd \set {a c, b} = \gcd \set {c, b}$
where $\gcd$ denotes greatest common divisor.
== Proof ==
Let $a, b, c \in \Z$ such that $a$ is coprime to $b$.
Let $d = \gcd \set {c, b}$.
We have:
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $16 \ \text {(c)}$
Category:Coprime Integers
Category:Greatest Common Divisor
GCD for Negative Integers

== Theorem ==
Let $a$ and $b$ be integers.
:$\gcd \set {a, b} = \gcd \set {\size a, b} = \gcd \set {a, \size b} = \gcd \set {\size a, \size b}$
where $\gcd$ denotes the greatest common divisor.
Alternatively, this can be put:
:$\gcd \set {a, b} = \gcd \set {-a, b} = \gcd \set {a, -b} = \gcd \set {-a, -b}$
 
which follows directly from the above.
== Proof ==
Note that $\size a = \pm a$.
Suppose that:
:$u \divides a$
where $\divides$ denotes divisibility.
Then:
:$\exists q \in \Z: a = q u$
Then:
:$\size a = \pm q u = \paren {\pm q} u \implies u \divides \size a$
So every divisor of $a$ is a divisor of $\size a$.
Similarly, note that:
:$a = \pm \size a$
so every divisor of $\size a$ is a divisor of $a$.
So it follows that the common divisors of $a$ and $b$ are the same as those of $a$ and $\size b$, and so on.
In particular:
:$\gcd \set {a, b} = \gcd \set {a, \size b}$
and so on.
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $11$
Category:Greatest Common Divisor
GCD from Congruence Modulo m

== Theorem ==
Let $a, b \in \Z, m \in \N$.
 
Let $a$ be congruent to $b$ modulo $m$.
Then the GCD of $a$ and $m$ is equal to the GCD of $b$ and $m$.
That is:
:$a \equiv b \pmod m \implies \gcd \set {a, m} = \gcd \set {b, m}$
== Proof ==
We have:
:$a \equiv b \pmod m \implies \exists k \in \Z: a = b + k m$
Thus:
:$a = b + k m$
and the result follows directly from GCD with Remainder.
== Sources ==
* : Chapter $1$: Properties of the Natural Numbers: $\S 23 \beta$
* : Exercise $2.12$
Category:Modulo Arithmetic
Category:Greatest Common Divisor