nyuuzyou/wikis huggingface dataset:
Chebyshev Distance is Limit of P-Product Metric

== Theorem ==
Let $M_{1'} = \struct {A_{1'}, d_{1'} }$ and $M_{2'} = \struct {A_{2'}, d_{2'} }$ be metric spaces.
Let $\AA = A_{1'} \times A_{2'}$ be the cartesian product of $A_{1'}$ and $A_{2'}$.
Let $p \in \R_{\ge 1}$.
Let $d_p: \AA \times \AA \to \R$ be the $p$-product metric on $\AA$:
:$\map {d_p} {x, y} := \paren {\paren {\map {d_{1'} } {x_1, y_1} }^p + \paren {\map {d_{2'} } {x_2, y_2} }^p}^{1/p}$
and let $d_\infty: \AA \times \AA \to \R$ be the Chebyshev distance on $\AA$:
:$\ds \map {d_\infty} {x, y} := \max \set {\map {d_{1'} } {x_1, y_1}, \map {d_{2'} } {x_2, y_2} }$
where $x = \tuple {x_1, x_2}, y = \tuple {y_1, y_2} \in \AA$.
Then:
:$\ds d_\infty = \lim_{p \mathop \to \infty} d_p$
in the sense that:
:$\ds \max \set {\map {d_{1'} } {x_1, y_1}, \map {d_{2'} } {x_2, y_2} } = \lim_{p \mathop \to \infty} \paren {\paren {\map {d_{1'} } {x_1, y_1} }^p + \paren {\map {d_{2'} } {x_2, y_2} }^p}^{1/p}$
== Proof ==
Let $x$ and $y$ be arbitrary.
Let $a = \map {d_{1'} } {x_1, y_1}, b = \map {d_{2'} } {x_2, y_2}$.
, suppose that $\max \set {a, b} = a$.
Then:
and:
The result follows by the Squeeze Theorem for Functions.
Category:Chebyshev Distance
Category:P-Product Metrics
Chebyshev Distance is Metric

== Theorem ==
Let $M_1 = \struct {A_1, d_1}, M_2 = \struct {A_2, d_2}, \ldots, M_n = \struct {A_n, d_n}$ be metric spaces.
Let $\ds \AA = \prod_{i \mathop = 1}^n A_i$ be the cartesian product of $A_1, A_2, \ldots, A_n$.
Let $d_\infty: \AA \times \AA \to \R$ be the Chebyshev distance on $\AA$:
:$\ds \map {d_\infty} {x, y} = \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, y_i} }$
where $x = \tuple {x_1, x_2, \ldots, x_n}, y = \tuple {y_1, y_2, \ldots, y_n} \in \AA$.
Then $d_\infty$ is a metric.
== Proof ==
=== Proof of ===
So holds for $d_\infty$.
=== Proof of ===
Let $k \in \closedint 1 n$ such that:
Then by application of for metric $d_k$:
:$\map {d_k} {x_k, z_k} \le \map {d_k} {x_k, y_k} + \map {d_k} {y_k, z_k}$
But by the nature of the $\max$ operation:
:$\ds \map {d_k} {x_k, y_k} \le \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, y_i} }$
and:
:$\ds \map {d_k} {y_k, z_k} \le \max_{i \mathop = 1}^n \set {\map {d_i} {y_i, z_i} }$
Thus:
:$\ds \map {d_k} {x_k, y_k} + \map {d_k} {y_k, z_k} \le \max_{i \mathop = 1}^n \set {\map {d_i} {x_i, y_i} } + \max_{i \mathop = 1}^n \set {\map {d_i} {y_i, z_i} }$
Hence:
:$\map {d_\infty} {x, z} \le \map {d_\infty} {x, y} + \map {d_\infty} {y, z}$
So holds for $d_\infty$.
=== Proof of ===
So holds for $d_\infty$.
=== Proof of ===
Let $x = \tuple {x_1, x_2, \ldots, x_n}$ and $y = \tuple {y_1, y_2, \ldots, y_n}$.
So holds for $d_\infty$.
== Sources ==
* : Chapter $2$: Metric Spaces: $\S 2$: Metric Spaces: Theorem $2.3$
* : $2$: Continuity generalized: metric spaces: $2.2$: Examples: Example $2.2.7$
Category:Chebyshev Distance
Chebyshev Distance on Real Number Plane is Translation Invariant

== Theorem ==
Let $\tau_{\mathbf t}: \R^2 \to \R^2$ denote the translation of the Euclidean plane by the vector $\mathbf t = \begin {pmatrix} a \\ b \end {pmatrix}$.
Let $d_\infty$ denote the Chebyshev distance on $\R^2$.
Then $d_1$ is unchanged by application of $\tau$:
:$\forall x, y \in \R^2: \map {d_\infty} {\map \tau x, \map \tau y} = \map {d_\infty} {x, y}$
== Proof ==
Let $x = \tuple {x_1, x_2}$ and $y = \tuple {y_1, y_2}$ be arbitrary points in $\R^2$.
Then:
== Sources ==
* : $2$: Continuity generalized: metric spaces: Exercise $2.6: 22$
Category:Translation Mappings
Category:Chebyshev Distance
Chebyshev Distance on Real Number Plane is not Rotation Invariant

== Theorem ==
Let $r_\alpha: \R^2 \to \R^2$ denote the rotation of the Euclidean plane about the origin through an angle of $\alpha$.
Let $d_\infty$ denote the Chebyshev distance on $\R^2$.
Then it is not necessarily the case that:
:$\forall x, y \in \R^2: \map {d_\infty} {\map {r_\alpha} x, \map {r_\alpha} y} = \map {d_\infty} {x, y}$
== Proof ==
Proof by Counterexample:
Let $x = \tuple {0, 0}$ and $y = \tuple {1, 1}$ be arbitrary points in $\R^2$.
Then:
Now let $\alpha = \dfrac \pi 4 = 45 \degrees$.
== Sources ==
* : $2$: Continuity generalized: metric spaces: Exercise $2.6: 22$
Category:Geometric Rotations
Category:Chebyshev Distance
Chebyshev Distance on Real Vector Space is Metric

== Theorem ==
The Chebyshev distance on $\R^n$:
:$\ds \forall x, y \in \R^n: \map {d_\infty} {x, y}:= \max_{i \mathop = 1}^n {\size {x_i - y_i} }$
is a metric.
== Proof 1 ==
== Proof 2 ==
Category:Chebyshev Distance
Chebyshev Distance on Real Vector Space is Metric/Proof 1

== Theorem ==
== Proof ==
This is an instance of the Chebyshev distance on the cartesian product of metric spaces $A_1, A_2, \ldots, A_3$.
This is proved in Chebyshev Distance is Metric.
== Sources ==
* : Chapter $2$: Metric Spaces: $\S 2$: Metric Spaces: Corollary $2.4$
Category:Chebyshev Distance
Chebyshev Distance on Real Vector Space is Metric/Proof 2

== Theorem ==
== Proof ==
=== Proof of ===
So holds for $d_\infty$.
=== Proof of ===
Let $k \in \closedint 1 n$ such that:
Then by the Triangle Inequality for Real Numbers:
:$\size {x_k - z_k} \le \size {x_k - y_k} + \size {y_k - z_k}$
But by the nature of the $\max$ operation:
:$\ds \size {x_k - y_k} \le \max_{i \mathop = 1}^n \size {x_i - y_i}$
and:
:$\ds \size {y_k - z_k} \le \max_{i \mathop = 1}^n \size {y_i - z_i}$
Thus:
:$\ds \size {x_k - y_k} + \size {y_k - z_k} \le \max_{i \mathop = 1}^n \size {x_i - y_i} + \max_{i \mathop = 1}^n \size {y_i - z_i}$
Hence:
:$\map {d_\infty} {x, z} \le \map {d_\infty} {x, y} + \map {d_\infty} {y, z}$
So holds for $d_\infty$.
=== Proof of ===
So holds for $d_\infty$.
=== Proof of ===
Let $x = \tuple {x_1, x_2, \ldots, x_n}$ and $y = \tuple {y_1, y_2, \ldots, y_n}$.
So holds for $d_\infty$.
== Sources ==
* : $2$: Continuity generalized: metric spaces: $2.2$: Examples: Examples $2.2.3$
Category:Chebyshev Distance
Chebyshev Polynomials of the First Kind are Orthogonal

== Theorem ==
The Chebyshev polynomials of the first kind form a set of orthogonal polynomials :
:the closed real interval $\closedint {-1} 1$
:the weight function $\map w x := \dfrac{1}{\sqrt{1-x^2}}$ on $\closedint {-1} {1}$
== Proof ==
== Sources ==
* 
* 
* 
* 
Category:Chebyshev Polynomials of the First Kind
Category:Examples of Orthogonal Polynomials
Chen's Theorem

== Theorem ==
Every sufficiently large even integer is the sum of either:
:$(1): \quad$ two primes, or 
:$(2): \quad$ a prime and a semiprime.
== Proof ==
== Historical Note ==
== Sources ==
* 
* 
* : Chapter $7$: Patterns in Numbers: Fermat
Category:Prime Numbers
Category:Semiprimes
Category:Number Theory
Chern-Gauss-Bonnet Theorem

== Theorem ==
The Chern-Gauss-Bonnet Theorem is a non-trivial generalization of the Gauss-Bonnet Theorem, as follows:
== Proof ==
== Also see ==
* Gauss-Bonnet Theorem
* Riemann-Roch Theorem
* Atiyah-Singer Index Theorem
* Definition:De Rham Cohomology
== Sources ==
Category:Differential Geometry
Chi-Squared Test for Goodness of Fit/Examples/Cast of Dice

== Example of Use of Chi-Squared Test for Goodness of Fit ==
Let $D$ be a die which we want to determine is fair or not.
Let $D$ be cast $96$ times.
Then:
:$x_i \in \set {1, 2, 3, 4, 5, 6}$
If $D$ is fair, then for all $i$, the number of times we expect to observe each face of $D$ is:
:$E_i = 96 \times \dfrac 1 6 = 16$
Suppose in our trial, the number of times each face comes up is shown in the table below:
Then:
The expectation of $16$ is computed from the data, so there are $6 - 1 = 5$ degrees of freedom.
The $\chi^2$ value is not significant at the $5 \%$ level (i.e. is $< 11.07$), so the hypothesis that $D$ is fair is not rejected.
:
== Sources ==
* 
* 
Category:Examples of Chi-Squared Test for Goodness of Fit
Chinese Remainder Theorem

== Theorem ==
Let $b_1, b_2, \ldots, b_r \in \Z$.
Let $n_1, n_2, \ldots, n_r$ be pairwise coprime positive integers.
Let $\ds N = \prod_{i \mathop = 1}^r n_i$.
Then the system of linear congruences:
has a solution which is unique modulo $N$:
:$\exists ! a \in \Z_{>0}: x \equiv a \pmod N$
=== Corollary ===
=== General Result ===
== Proof ==
=== Existence ===
Let $N_k = \dfrac N {n_k}$ for $k = 1, 2, \ldots, r$.
From Integer Coprime to all Factors is Coprime to Whole:
:$\forall k \in \set {1, 2, \ldots, r}: \gcd \set {N_k, n_k} = \gcd \set {n_1 n_2 \cdots n_{k - 1} n_{k + 1} \cdots n_r, n_k} = 1$
From Solution of Linear Congruence, the linear congruence:
:$N_k x \equiv b_k \pmod {n_k}$
has a unique solution modulo $n_k$.
Let this solution be $x_k$.
That is:
:$(1): \quad N_k x_k \equiv b_k \pmod {n_k}$
for $k = 1, 2, \ldots, r$.
Let $\ds x_0 = \sum_{i \mathop = 1}^r N_i x_i$.
For each $k, i \in \set {1, 2, 3, \ldots, r}$ such that $i \ne k$:
Then for each $k = 1, 2, 3, \ldots, r$:
Thus $x_0$ is a simultaneous solution.
=== Uniqueness ===
Suppose $x'$ is a second solution of the system.
That is:
:$\forall k \in \set {1, 2, \ldots, r}: x_0 \equiv x' \equiv b_k \pmod {n_k}$
Then:
Thus the simultaneous solution is unique modulo $N$.
== Construction of Solution ==
== Examples ==
== Also see ==
* Chinese Remainder Theorem (Commutative Algebra)
== Historical Note ==
== Sources ==
* : $\S 2.3$: Congruences: Theorem $5$
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $12$
* 
* : Sun Tsu Suan Ching: $69$
* 
* 
Category:Chinese Remainder Theorem
Category:Modulo Arithmetic
Category:Number Theory
Category:Named Theorems
Chinese Remainder Theorem/Construction of Solution

== Theorem ==
Recall the Chinese Remainder Theorem:
== Solution ==
The following is a systematic technique for finding $a$:
For each $i \in \set {1, 2, \ldots, r}$, calculate:
:$y_i = \dfrac N {n_i}$
Using Euclid's Algorithm, calculate $z_i$ such that:
:$z_i y_i = 1 \pmod {n_i}$
Then:
:$x \equiv \ds \sum_{i \mathop = 1}^r b_i y_i z_i$
is a unique solution to the given system of linear congruences.
== Proof ==
First we demonstrate that $x$ is a solution.
By construction:
For each $i \in \set {1, 2, \ldots, r}$, we have:
Hence:
:$\forall i \in \set {1, 2, \ldots, r}: x \equiv b_i \pmod {n_i}$
Thus $x$ is a solution as required.
Now we demonstrate uniqueness up to congruence modulo $N$:
Now suppose there exist $u, v \in \Z$ which are both solutions.
Then:
Category:Chinese Remainder Theorem
Chinese Remainder Theorem/Corollary

== Theorem ==
Let $n_1, n_2, \ldots, n_r$ be pairwise coprime positive integers.
Let $\ds N = \prod_{i \mathop = 1}^r n_i$.
For an integer $k$, let $\Z / k \Z$ denote the ring of integers modulo $k$.
Then we have a ring isomorphism:
:$\Z / N \Z \simeq \Z / n_1 \Z \times \cdots \times \Z / n_r \Z$
== Proof ==
Define a mapping:
:$\phi: \Z / N \Z \to \Z / n_1 \Z \times \cdots \times \Z / n_r \Z$
by:
:$\map \phi {d \pmod N} = \paren {d \pmod {n_1}, \ldots, d \pmod {n_r} }$
Then, by Mappings Between Residue Classes, $\phi$ is well-defined.
By the definition of multiplication and addition in $\Z / k \Z$, $k \in \Z$ we have:
:$\paren {a \pmod k} + \paren {b \pmod k} = \paren {a + b} \pmod k$
and
:$\paren {a \pmod k} \cdot \paren {b \pmod k} = \paren {a \cdot b} \pmod k$
Thus taking $k = n_1, \ldots, n_r$ separately we see that $\phi$ is a ring homomorphism.
Let:
:$\paren {a_1 \pmod {n_1}, \ldots, a_r \pmod {n_r} } \in \Z / n_1 \Z \times \cdots \times \Z / n_r \Z$
By the Chinese Remainder Theorem there exists a unique $x \in \Z / N \Z$ such that:
:$\map \phi x = \paren {a_1 \pmod {n_1}, \ldots, a_r \pmod {n_r} }$
Since such an $x$ exists, $\phi$ is surjective.
Since this $x$ is unique modulo $N$, it follows that $\phi$ is injective.
== Sources ==
* : $\S 2.3$: Congruences
Category:Commutative Algebra
Category:Chinese Remainder Theorem
Chinese Remainder Theorem/Examples/x = 2 mod 3, 3 mod 5, 2 mod 7

== Example of use of Chinese Remainder Theorem ==
Consider the system of simultaneous linear congruences:
Then $x \equiv 23 \pmod {105}$
== Proof ==
Using Solution to Chinese Remainder Theorem, we define:
We require to find $z_1$, $z_2$ and $z_3$ such that:
Thus:
Then:
== Also see ==
* Sun Tzu Suan Ching/Examples/Example 2, which is exactly this result
== Sources ==
* 
* 
Category:Examples of Chinese Remainder Theorem
Chinese Remainder Theorem/General Result

== Theorem ==
Let $n_1, n_2, \ldots, n_k$ be positive integers.
Let $b_1, b_2, \ldots, b_k$ be integers such that:
:$\forall i \ne j: \gcd \set {n_i, n_j} \divides b_i - b_j$
Then the system of linear congruences:
has a simultaneous solution which is unique modulo $\lcm \set {n_1, \ldots, n_k}$.
== Proof ==
=== Existence ===
We prove this by induction on $k$.
==== Basis for the induction ====
Let $k = 2$.
Let $d = \gcd \set {n_1, n_2}$.
From Bézout's Identity:
:$d = s n_1 + t n_2$
for some $s, t \in \Z$.
Let $\tuple {q_1, r}$ and $\tuple {q_2, r}$ be the quotient and remainder of $b_1$ and $b_2$ upon division by $d$.
Then $x = q_1 s n_2 + q_2 t n_2 + r$ is a solution.
==== Induction step ====
Let $n = \lcm \set {n_2, \ldots, n_k}$.
By the induction hypothesis, the last $k - 1$ congruences are equivalent to a single congruence:
:$x \equiv b \pmod n$
for a certain $b \in \Z$ which satisfies $b \equiv b_i \pmod {n_i}$ for all $i \in \set {2, \ldots, k}$.
It remains to be shown that
:$\lcm \set {n, n_1} = \lcm \set {n_1, \ldots, n_k}$
:$b \equiv b_1 \pmod {\gcd \set {n, n_1} }$
to apply the case $k = 2$ and conclude.
The first statement follows from Lowest Common Multiple is Associative.
From GCD and LCM Distribute Over Each Other:
:$\gcd \set {n, n_1} = \lcm \set {\gcd \set {n_1, n_2}, \ldots, \gcd \set {n_1, n_k} }$
For all $i \in \set {2, \ldots, k}$:
:$b \equiv b_i \pmod {n_i}$
and:
:$b_i \equiv b_1 \pmod {\gcd \set {n_1, n_i} }$
Thus:
:$b \equiv b_1 \pmod {\gcd \set {n_1, n_i} }$
Therefore:
:$b \equiv b_1 \pmod {\lcm \set {\gcd \set {n_1, n_2}, \ldots, \gcd \set {n_1, n_k} } }$
=== Uniqueness ===
== Sources ==
* 
* 
Category:Chinese Remainder Theorem
Chinese Remainder Theorem/Historical Note

== Historical Note on Chinese Remainder Theorem ==
The Chinese Remainder Theorem was found in the of , who was active in China sometime between $200$ and $500$ C.E (nobody knows exactly when).
The principle is believed to have been used by Chinese calendar makers as far back as $100$ C.E.
It was first proved properly by in $1247$.
== Sources ==
* : $\S 2.3$: Congruences
* 
* 
Category:Historical Notes
Chinese Remainder Theorem (Commutative Algebra)

== Theorem ==
Let $A$ be a commutative and unitary ring.
Let $I_1, \ldots, I_n$ for some $n \ge 1$ be ideals of $A$.
Then the ring homomorphism $\phi: A \to A / I_1 \times \cdots \times A / I_n$ defined as:
:$\map \phi x = \tuple {x + I_1, \ldots, x + I_n}$
has the kernel $\ds I := \bigcap_{i \mathop = 1}^n I_i$, and is surjective the ideals are pairwise coprime, that is:
:$\forall i \ne j: I_i + I_j = A$
Hence in that case, it induces an ring isomorphism:
:$A / I \to A / I_1 \times \cdots \times A / I_n$
through the First Isomorphism Theorem.
== Proof 1 ==
== Proof 2 ==
== Also see ==
* Chinese Remainder Theorem (Groups), of which this is a special case
* Product of Coprime Ideals equals Intersection, which is sometimes cited as part of the Chinese Remainder Theorem
== Sources ==
* : Chapter $12$ Algebraic Number Theory: $\S 3$ Ramification and Degree: Proposition $12.3.1$
* : Chapter $\text {III}$, $\S 3$ Exercises: Problem $7$
* : Proposition $12.4.1$
Category:Chinese Remainder Theorem (Commutative Algebra)
Category:Chinese Remainder Theorem
Category:Commutative Algebra
Chinese Remainder Theorem (Commutative Algebra)/Proof 1

== Theorem ==
== Proof ==
The mapping $\phi$ is indeed a ring homomorphism, because each canonical projection $\phi_i: A \to A / I_i$ is a ring homomorphism.
The kernel of $\phi$ is given by:
:$\ds \ker \phi = \set {x \in A: \forall i, 1 \le i \le n : x \in I_i} = \bigcap_{1 \mathop \le i \mathop \le n} I_i =: I$
It remains then to be proved that $\phi$ is surjective the ideals are pairwise coprime.
Stated explicitly, we will show that the statement:
:$\forall x_i \in A, 1 \le i \le n: \exists x \in A: x - x_i \in I_i, 1 \le i \le n$
holds : 
:$\forall i \ne j: I_i + I_j = A$
To reach this goal, we now define $e_i \in A / I_1 \times \cdots \times A / I_n$ so that a unity lies at the $i$th coordinate:
:$e_i := \tuple {0, \ldots, 0, 1_{A / I_i}, 0, \ldots, 0}$
=== Necessary Condition ===
We will start by showing the condition is necessary for surjectivity.
So suppose $\phi$ is surjective.
Then in particular, for each $i$, there is $a_i \in A$ such that $\map \phi {a_i} = e_i$.
Clearly, $\map {\phi_j} {a_i} = 0$ for $j \ne i$ while $\map {\phi_i} {1 - a_i} = \map {\phi_i} 1 - \map {\phi_i} {a_i} = 1 - 1 = 0$.
Hence for all $i \ne j$, we find:
:$1 = a_i + \paren {1 - a_i} \in I_j + I_i$
Since Sum of Ideals is Ideal, we can conclude $r \cdot 1 \in I_j + I_i$ for all $r \in R$.
This completes the proof that $I_i + I_j = R$.
=== Sufficient Condition ===
We will now show the converse that the ideals being coprime is sufficient. 
Note that each $x \in A / I_1 \times \cdots \times A / I_n$ may then be written as:
:$x = \tuple {x_1 + I_1, \ldots, x_n + I_n} = \paren {x_1 + I_1} e_1 + \cdots + \paren {x_n + I_n} e_n$
for some choice of $x_i \in A$.
This implies that it is enough to find $a_i \in A, 1 \le i \le n$, such that:
:$\map \phi {a_i} = e_i$
because then:
To construct the $a_i \in A$, we need that $a_i - 1 \in I_i$, but $a_i \in I_j$ for all $j \ne i$.
Since $I_i$ is coprime with the other ideals, we have that:
:$I_i + I_j = A, i \ne j$
In particular there exist $u_{i j} \in I_i$, $v_{i j} \in I_j$ for each pair $\tuple {i, j}$ with $i \ne j$ such that $u_{i j} + v_{i j} = 1$.
Define now $\ds a_i = \prod_{k \mathop \ne i} v_{i k}$. 
Then for $k \ne i$:
:$a_i = v_{i k} \tuple {v_{i 1} \cdots v_{i \paren {k - 1} } v_{i \paren {k + 1} } \cdots v_{i n} } \in I_k$
and:
Hence:
:$a_i - 1 \in I_i$
which verifies that $\map \phi {a_i} = e_i$.
This concludes the proof of the sufficiency.
Now to conclude, let $\phi$ be surjective again.
Let $\tilde \phi$ be the injective homomorphism obtained by the First Isomorphism Theorem:
:$\map {\tilde \phi} {x + I} = \tuple {x_1 + I_1, \ldots, x_n + I_n}$
for all $x \in A$.
It immediately follows that $\tilde \phi$ is also surjective, and hence constitutes an isomorphism.
== Sources ==
* : Chapter $12$ Algebraic Number Theory: $\S 3$ Ramification and Degree: Proposition $12.3.1$
* : Chapter $\text {III}$, $\S 3$ Exercises: Problem $7$
* : Proposition $12.4.1$
Category:Chinese Remainder Theorem (Commutative Algebra)
Chinese Remainder Theorem (Commutative Algebra)/Proof 2

== Theorem ==
== Proof ==
Consider $\pi$ only as a homomorphism of groups.
Then Chinese Remainder Theorem (Groups) is applicable as Subgroup of Abelian Group is Normal. 
It remains to demonstrate that the condition $I_i + I_j = R$ for all $i \ne j$ assumed here is equivalent to:
:$\ds \forall k \le n - 1: I_{k + 1} + \bigcap_{i \mathop = 1}^k I_i = R$
The implication from the latter condition is immediate.
For the converse, let $i$ be arbitrary.
The result follows from:
== Sources ==
* : Chapter $12$ Algebraic Number Theory: $\S 3$ Ramification and Degree: Proposition $12.3.1$
* : Chapter $\text {III}$, $\S 3$ Exercises: Problem $7$
* : Proposition $12.4.1$
Category:Chinese Remainder Theorem (Commutative Algebra)
Chinese Remainder Theorem (Groups)

== Theorem ==
Let $G$ be a group.
Let $N_1, \ldots, N_n$ for some $n \ge 1$ be normal subgroups of $G$.
Let $\pi_i: G \rightarrow G / N_i$ be the canonical projections.
Then the homomorphism $\pi: G \to G / N_1 \times \cdots \times G / N_n$ defined as:
:$\map \pi x = \tuple {\map {\pi_1} x, \ldots, \map {\pi_n} x}$
has the kernel $\ds N := \bigcap_{i \mathop = 1}^n N_i$.
Further, $\pi$ is surjective the normal subgroups have the following property:
:$\ds \forall k \le n - 1: N_{k + 1} \bigcap_{i \mathop = 1}^k N_i = G$
== Proof ==
By Quotient Group Epimorphism is Epimorphism, each canonical projection $\pi_i: G \to G / N_i$ is a group homomorphism.
Hence the mapping $\pi$ is indeed a group homomorphism.
The kernel of $\pi$ is given by:
:$\ds \ker \pi = \set {x \in G: \forall i, 1 \le i \le n: \map {\pi_i} x = \map {\pi_i} e} = \set {x \in G: \forall i, 1 \le i \le n: x \in N_i} = \bigcap_{1 \mathop \le i \mathop \le n} N_i =: N$
We will now establish the necessity and sufficiency of the condition for surjectivity of $\pi$.
Indeed, we will demonstrate that if $\pi$ is surjective, then:
:$\ds \forall k: N_k \bigcap_{j \mathop \ne k} N_j = G$
which will complete the proof together with a deduction of surjectivity from the condition that:
:$\ds \forall k \le n - 1: N_{k + 1} \bigcap_{i \mathop = 1}^k N_i = G$
=== Necessary Condition ===
We will start by showing the condition is necessary for surjectivity.
So suppose $\pi$ is surjective.
Let $x \in G$ be arbitrary.
Then for each $i$, there is $u_i \in G$ such that $\map {\pi_i} {u_i} = \map {\pi_i} x$ and $\map {\pi_j} {u_i} = \map {\pi_j} e$ for $j \ne i$.
Note that $\map {\pi_i} {u_i^{-1} x} = \map {\pi_i} {u_i}^{-1} \map {\pi_i} x = \map {\pi_i} e$.
Therefore, $u_i \in N_j$ for $j \neq i$ and $u_i^{-1} x \in N_i$.
Hence for all $i \ne j$, we find:
:$\ds x = u_i \paren {u_i^{-1} x} \in N_j \bigcap_{m \mathop \ne i} N_m$
As $x$ was arbitrary, this completes the proof that $\ds N_j \bigcap_{m \mathop \ne i} N_m = G$.
=== Sufficient Condition ===
We will use induction on $n$, where the base case $n = 1$ is trivial.
By induction, assume the result for the case $n$.
Now take any $x_1, \ldots, x_n, y \in G$.
We will produce an element $g$ with $\map \pi g = \tuple {\map {\pi_1} {x_1}, \ldots, \map {\pi_n} {x_n}, \map {\pi_{n + 1} } y}$.
First, by the induction hypothesis, we can find an $x \in G$ such that we have $\map {\pi_i} x = \map {\pi_i} {x_i}$ for all $i \le n$.
Recall our assumption that $\ds N_{n + 1} \bigcap_{i \mathop = 1}^n N_i = G$.
In particular, we can choose $a \in N_{n + 1}$ and $\ds b \in \bigcap_{i \mathop = 1}^n N_i$ such that $y^{-1} x = a b$.
Equivalently, we have $y a = x b^{-1}$.
Thus for $i \le n$, we have $\map {\pi_i} {y a} = \map {\pi_i} {x b^{-1} } = \map {\pi_i} x = \map {\pi_i} {x_i}$.
Further, we have $\map {\pi_{n + 1} } {y a} = \map {\pi_{n + 1} }y$.
This means that $g = y a$ is the desired element.
This concludes the proof of the sufficiency.
== Also see ==
* Chinese Remainder Theorem (Commutative Algebra)
* Chinese Remainder Theorem
Category:Chinese Remainder Theorem
Category:Normal Subgroups
Chiu Chang Suann Jing/Examples

== Examples of Problems from ==
=== Example $1$ ===
=== Example $2$ ===
=== Example $3$ ===
=== Example $4$ ===
=== Example $5$ ===
=== Example $6$ ===
=== Example $7$ ===
=== Example $8$ ===
=== Example $9$ ===
=== Example $10$ ===
Category:Chiu Chang Suann Jing
Chiu Chang Suann Jing/Examples/Example 1

== Example of Problem from ==
:Two and a half piculs of rice are bought for $\frac 3 7$ of a tael of silver.
:How many piculs of rice can be bought for $9$ taels?
== Answer ==
Let $x$ be the required quantity.
:$\dfrac x 9$ piculs can be bought with $1$ tael.
Hence $\dfrac x 9 \times \dfrac 3 7$ can be bought for $\dfrac 3 7$ of a tael.
That is:
:$\dfrac x 9 \times \dfrac 3 7 = \dfrac 5 2$
and so:
:$x = 9 \times \dfrac 5 2 / \dfrac 3 7 = 52 \frac 1 2$
One picul, apparently, is equal to about $65$ kilograms.
== Sources ==
* 
* : Chapter $3$: Notations and Numbers: Brahmagupta, Mahavira and Bhaskara
Category:Chiu Chang Suann Jing
Chiu Chang Suann Jing/Examples/Example 10

== Example of Problem from ==
:Of $2$ water weeds, one grows $3$ feet and one grows $1$ foot on the first day.
:The growth of the first becomes every day half of that of the preceding day
:while the other grows twice as much as the previous day.
:In how many days will the two grow to equal heights?
== Solution ==
:$2 \frac 6 {13}$ days, at which time they will grow to $4 \frac {11} {13}$ feet.
== Proof ==
The growth of the $2$ plants is governed by a geometric sequence.
Let the height of the two plants after the first day be $a_1$ and $a_2$ respectively.
Let the common ratio of the growth rates of the two plants be $r_1$ and $r_2$ respectively.
Let $d$ be the number of days after which they reach the same height.
We have:
Thus we have that $2^d = 1$ or $2^d = 6$.
Hence either $d = 0$, which does not work, or $d = \log_2 6$.
This gives $d \approx 2.585$, and a common height of $5$ feet.
== Sources ==
* 
* 
* : The Nine Chapters: $68$
Category:Chiu Chang Suann Jing