avewright/proofwiki-math huggingface dataset:
Theorem: Transitivity of Big-O Estimates/Sequences

Let $\sequence {a_n}$, $\sequence {b_n}$ and $\sequence {c_n}$ be sequences of real or complex numbers.
Let $a_n = \map \OO {\sequence {b_n} }$ and $b_n = \map \OO {\sequence {c_n} }$, where $\OO$ denotes big-$\OO$ notation.
Then $a_n = \map \OO {\sequence {c_n} }$.

Proof:
Because $a_n = \map \OO {\sequence {b_n} }$, there exists $K \ge 0$ and $n_0 \in \N$ such that $\size {a_n} \le K \cdot \size {b_n}$ for $n \ge n_0$.
Because $b_n = \map \OO {\sequence {c_n} }$, there exists $L \ge 0$ and $n_1 \in \N$ such that $\size {b_n} \le L \cdot \size {c_n}$ for $n \ge n_1$.
Then $\size {a_n} \le K L \cdot \size {c_n}$ for $n \ge \max \set {n_0, n_1}$.
Thus $a_n = \map \OO {\sequence {c_n} }$.
{{qed}}
Category:Big-O Notation
j1albq05hyknu9hcy8li8tmdmaxfm4g
Theorem: Conjugate of Cycle

Let $n \ge 1$ be a natural number.
Let $S_n$ be the symmetric group on $n$ letters.
Let $\pi, \sigma \in S_n$.
Let $\sigma$ be a cycle of length $k$.
Then the conjugate $\pi \sigma \pi^{-1}$ is a cycle of length $k$.

Proof:
Follows directly from Conjugate Permutations have Same Cycle Type.
{{qed}}
Category:Cyclic Permutations
Category:Conjugacy
32y4tmmpdspvu6gfxihl1bscksbwenj
Theorem: Center of Group is Kernel of Conjugacy Action

Let $G$ be a group.
Let $Z$ be the kernel of the conjugacy action.
Then $Z$ is the center of $G$.

Proof:
{{begin-eqn}}
{{eqn | o =
      | r = x \text { is in the kernel of the conjugacy action}
}}
{{eqn | ll= \leadstoandfrom
      | q = \forall y \in G
      | o =
      | r = x y x^{-1} = y
}}
{{eqn | ll= \leadstoandfrom
      | q = \forall y \in G
      | o =
      | r = x y = y x
      | c = Division Laws for Groups
}}
{{eqn | ll= \leadstoandfrom
      | o =
      | r = x \text { is in the center of } G
}}
{{end-eqn}}
{{qed}}
Category:Conjugacy Action
Category:Centers of Groups
d8xzbd3y4078monl0k5s6x9npt0fybn
Theorem: Little-O Implies Big-O/General Result

Let $X$ be a topological space.
Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\,\cdot\,}$
Let $f, g: X \to V$ be mappings.
Let $x_0 \in X$.
Let $f = \map \oo g$ as $x \to x_0$, where $\oo$ denotes little-$\oo$ notation.
Then $f = \map \OO g$ as $x \to x_0$, where $\OO$ denotes big-$\OO$ notation.

Proof:
From the definition of little-$\oo$ notation:
:there exists a neighborhood $U$ of $x_0$ such that $\norm {\map f x} \le \norm {\map g x}$ for all $x \in U$.
By definition of big-$\OO$ notation, $f = \map \OO g$ as $x \to x_0$.
{{qed}}
Category:Big-O Notation
Category:Little-O Notation
krsegn7o79z9ixc9c2z4qg0elkoriej
Theorem: Little-O Implies Big-O/Sequences

Let $\sequence {a_n}$ and $\sequence {b_n}$ be sequences of real or complex numbers.
Let $a_n = \map \oo {b_n}$ where $\oo$ denotes little-$\oo$ notation.
Then $a_n = \map \OO {b_n}$ where $\OO$ denotes big-$\OO$ notation.

Proof:
Because $a_n = \map \oo {b_n}$, there exists $n_0 \in \N$ such that $\size {a_n} \le 1 \cdot \size {b_n}$ for $n \ge n_0$.
Thus $a_n = \map \OO {b_n}$.
{{qed}}
Category:Big-O Notation
Category:Little-O Notation
m5v6mqpzbxxgth2n45of1yj7l1r0ani
Theorem: Equivalence of Definitions of Change of Basis Matrix

Let $R$ be a ring with unity.
Let $G$ be a finite-dimensional unitary $R$-module.
Let $A = \sequence {a_n}$ and $B = \sequence {b_n}$ be ordered bases of $G$.
{{TFAE|def = Change of Basis Matrix}}

Proof:
It will be shown that the two matrices defined are equal column-wise.
Let $\ds b_i = \sum_{j \mathop = 1}^n c_{i j} a_j$ for $i$ ranging from $1$ to $n$, where $c_{i j}$'s are scalars.
The uniqueness of the above expression is justified by Expression of Vector as Linear Combination from Basis is Unique.
Then by definition of coordinate vector, the $i$th column of the matrix defined in definition 1 is:
:$\begin {bmatrix} c_{i 1} & c_{i 2} & \ldots & c_{in} \end {bmatrix}^\intercal$
We also have:
:$\ds \map {I_G} {b_i} = b_i = \sum_{j \mathop = 1}^n c_{i j} a_j$
{{handwaving|The above needs to be clarified}}
So by definition of relative matrix, the $i$th column of the matrix defined in definition 2 is:
:$\begin {bmatrix} c_{i 1} & c_{i 2} & \ldots & c_{i n} \end {bmatrix}^\intercal$
The two matrices are equal, so the two definitions are equivalent.
{{qed}}
Category:Linear Algebra
Category:Matrix Theory
rhgslaw7qknsmr1e7ayjwmaua3bl9dw
Theorem: Substitution in Big-O Estimate/General Result

Let $X$ and $Y$ be topological spaces.
Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\,\cdot\,}$.
Let $x_0 \in X$ and $y_0 \in Y$.
Let $f: X \to Y$ be a function with $\map f {x_0} = y_0$ that is continuous at $x_0$.
Let $g, h: Y \to V$ be functions.
Suppose $\map g y = \map O {\map h y}$ as $y \to y_0$, where $O$ denotes big-O notation.
Then $\map {\paren {g \circ f} } x = \map O {\map {\paren {h \circ f} } x}$ as $x \to x_0$.

Proof:
Because $g = \map O h$, there exists a neighborhood $V$ of $y_0$ and a real number $c$ such that:
:$\norm {\map g x} \le c \cdot \norm {\map h x}$ for all $y \in V$.
By definition of continuity, there exists a neighborhood $U$ of $x_0$ with $\map f U \subset V$.
For $x \in U$, we have:
:$\norm {\map g {\map f x} } \le c \cdot \norm {\map h {\map f x} }$
Thus $g \circ f = \map O {h \circ f}$ as $x \to x_0$.
{{qed}}
Category:Big-O Notation
kmdwwuvozop5tkb8cj6s2eojqijepgv
Theorem: Substitution in Big-O Estimate/Sequences

Let $\sequence {a_n}$ and $\sequence {b_n}$ be sequences of real or complex numbers.
Let $a_n = \map \OO {b_n}$ where $\OO$ denotes big-O notation.
Let $\sequence {n_k}$ be a diverging sequence of natural numbers.
Then $a_{n_k} = \map \OO {b_{n_k} }$.

Proof:
Because $a_n = \map \OO {b_n}$, there exists $M \ge 0$ and $n_0 \in \N$ such that $\size {a_n} \le M \cdot \size {b_n}$ for $n \ge n_0$.
Because $n_k$ diverges, there exists $k_0 \in \N$ such that $n_k \ge n_0$ for $k \ge k_0$.
Then $\size {a_{n_k} } \le M \cdot \size {b_{n_k} }$ for $k \ge k_0$.
Thus:
:$a_{n_k} = \map \OO {b_{n_k} }$
{{qed}}
Category:Big-O Notation
l5hrptktbarpd9p4cm3mi821nkvyay6
Theorem: First Sequence of Three Consecutive Strictly Decreasing Euler Phi Values

The first sequence of $3$ consecutive positive integers whose Euler $\phi$ values are strictly decreasing is:
:$\map \phi {523} > \map \phi {524} > \map \phi {525}$

Proof:
{{begin-eqn}}
{{eqn | l = \map \phi {523}
      | r = 522
      | c = Euler Phi Function of Prime
}}
{{eqn | l = \map \phi {524}
      | r = 260
      | c = {{EulerPhiLink|524}}
}}
{{eqn | l = \map \phi {525}
      | r = 240
      | c = {{EulerPhiLink|525}}
}}
{{end-eqn}}
{{ProofWanted|It remains to be shown that this is the first such.}}
Theorem: Bases of Free Module have Equal Cardinality

Let $R$ be a commutative ring with unity.
Let $M$ be a free $R$-module.
Let $B$ and $C$ be bases of $M$.
Then $B$ and $C$ are equivalent.
That is, they have the same cardinality.

Proof:
By definition, a basis is a generator.
By Basis of Free Module is No Greater than Generator, there exist:
:an injection $f : B \to C$
:an injection $g : C \to B$
By the Cantor-Bernstein-Schröder Theorem, $B$ and $C$ are equivalent.
{{qed}}
Theorem: Sequences of Three Consecutive Strictly Increasing Euler Phi Values

The following sequences of $3$ consecutive positive integers have the property that their Euler $\phi$ values are strictly increasing:
:$\tuple {105, 106, 107}, \tuple {165, 166, 167}, \tuple {315, 316, 317}, \tuple {525, 526, 527}, \dots$
{{expand|Related sequences: A161962 (superset), A161963}}

Proof:
{{begin-eqn}}
{{eqn | l = \map \phi {525}
      | r = 240
      | c = {{EulerPhiLink|525}}
}}
{{eqn | l = \map \phi {526}
      | r = 262
      | c = {{EulerPhiLink|526}}
}}
{{eqn | l = \map \phi {527}
      | r = 480
      | c = {{EulerPhiLink|527}}
}}
{{end-eqn}}
{{finish}}
Theorem: Basis of Vector Space Injects into Generator

Let $K$ be a division ring.
Let $V$ be a vector space over $K$.
Let $B$ be a basis of $V$.
Let $G$ be a generator of $V$.
Then there exists an injection from $B$ to $G$.

Proof:
By Vector Space has Basis between Linearly Independent Set and Spanning Set, there exists a basis $C \subset G$.
By Bases of Vector Space have Equal Cardinality, there exists a bijection between $B$ and $C$.
By Composite of Injections is Injection, composing this bijection with the inclusion of $C$ in $G$, we obtain an injection from $B$ to $G$.
{{qed}}
Category:Vector Spaces
o50qamytl06tbrbu0zgnt3j68uncmuj
Theorem: Increasing Union of Ideals is Ideal/Sequence

Let $R$ be a ring.
Let $S_0 \subseteq S_1 \subseteq S_2 \subseteq \dotsb \subseteq S_i \subseteq \dotsb$ be ideals of $R$.
Then the increasing union $S$:
:$\ds S = \bigcup_{i \mathop \in \N} S_i$
is an ideal of $R$.

Proof:
Let $\ds S = \bigcup_{i \mathop \in \N} S_i$.
From Increasing Union of Subrings is Subring, we have that $S$ is a subring of $R$.
Now we need to show that it is an ideal of $R$.
Let $a \in S$.
Then $\exists i \in \N: a \in S_i$.
Let $b \in R$.
Then $a b \in S_i$ and $b a \in S_i$, as $S_i$ is an ideal of $R$.
Thus $a b \in S$ and $b a \in S$.
So $S$ is an ideal of $R$.
{{qed}}
Theorem: Increasing Union of Ideals is Ideal/Chain

Let $R$ be a ring.
Let $\struct {P, \subseteq}$ be the ordered set consisting of all ideals of $R$, ordered by inclusion.
Let $\set {I_\alpha}_{\alpha \mathop \in A}$ be a non-empty chain of ideals in $P$.
Let $\ds I = \bigcup_{\alpha \mathop \in A} I_\alpha$ be their union.
Then $I$ is an ideal of $R$.

Proof:
=== Property 1: $0 \in I$ ===
Since $\set {I_\alpha}_{\alpha \mathop \in A}$ is non-empty chain, it must contain some ideal $I_\beta$
Since $I_\beta$ is an ideal, $0 \in I_\beta$. 
Thus $0 \in I$.
Theorem: Union of Chain of Proper Ideals is Proper Ideal

Let $R$ be a ring with unity.
Let $\struct {P, \subseteq}$ be the ordered set consisting of all ideals of $R$, ordered by inclusion.
Let $\sequence {I_\alpha}_{\alpha \mathop \in A}$ be a non-empty chain of proper ideals in $P$.
Let $\ds I = \bigcup_{\alpha \mathop \in A} I_\alpha$ be their union.
Then $I$ is a proper ideal of $R$.

Proof:
By Union of Chain of Ideals is Ideal, $I$ is an ideal.
It remains to show that $I \subsetneq R$.
The ideals $I_\alpha$ are all proper, so none of them contain the unity.
Thus $I$ does not contain $1$, which means $I \subsetneq R$.
{{qed}}
Theorem: Dimension of Free Vector Space on Set

Let $k$ be a division ring.
Let $X$ be a set.
Let $k^{\paren X}$ be the free vector space on $X$.
The vector space $k^{\paren X}$ has dimension the cardinality of $X$.

Proof:
Follows from:
:Canonical Basis of Free Module on Set is Basis
:Cardinality of Canonical Basis of Free Module on Set
{{qed}}
Category:Vector Spaces
tfppnzuta22hqh19b9ep3xu1k0mgyru
Theorem: Numbers not Expressible as Sum of Fewer than 19 Fourth Powers

The following positive integer are the only ones which cannot be expressed as the sum of fewer than $19$ fourth powers:
:$79, 159, 239, 319, 399, 479, 559$
{{OEIS|A046050}}

Proof:
On a case-by-case basis:
From Smallest Number not Expressible as Sum of Fewer than 19 Fourth Powers:
{{:Smallest Number not Expressible as Sum of Fewer than 19 Fourth Powers}}
From 159 is not Expressible as Sum of Fewer than 19 Fourth Powers:
{{:159 is not Expressible as Sum of Fewer than 19 Fourth Powers}}
From 239 is not Expressible as Sum of Fewer than 19 Fourth Powers:
{{:239 is not Expressible as Sum of Fewer than 19 Fourth Powers}}
From 319 is not Expressible as Sum of Fewer than 19 Fourth Powers
{{:319 is not Expressible as Sum of Fewer than 19 Fourth Powers}}
From 399 is not Expressible as Sum of Fewer than 19 Fourth Powers
{{:399 is not Expressible as Sum of Fewer than 19 Fourth Powers}}
From 479 is not Expressible as Sum of Fewer than 19 Fourth Powers
{{:479 is not Expressible as Sum of Fewer than 19 Fourth Powers}}
From 559 is not Expressible as Sum of Fewer than 19 Fourth Powers
{{:559 is not Expressible as Sum of Fewer than 19 Fourth Powers}}
{{ProofWanted|It needs to be shown that there are no other numbers known with this property.}}
Theorem: 239 is not Expressible as Sum of Fewer than 19 Fourth Powers

:$239 = 13 \times 1^4 + 4 \times 2^4 + 2 \times 3^4$

Proof:
First note that $4^4 = 256 > 239$.
Then note that $3 \times 3^4 = 243 > 239$.
Hence any expression of $239$ as fourth powers uses no $n^4$ for $n \ge 4$, and uses not more than $2$ instances $3^4$.
For the remainder, using $2^4$ uses fewer fourth powers than $16$ instances $1^4$ does.
Now we have:
{{begin-eqn}}
{{eqn | l = 239
      | r = 2 \times 3^4 + 4 \times 2^4 + 13 \times 1^4
}}
{{eqn | r = 1 \times 3^4 + 9 \times 2^4 + 14 \times 1^4
}}
{{eqn | r = 0 \times 3^4 + 13 \times 2^4 + 15 \times 1^4
}}
{{end-eqn}}
and it is apparent the first one uses the least number of fourth powers, at $19$.
{{qed}}
Theorem: 479 is not Expressible as Sum of Fewer than 19 Fourth Powers

:$479 = 13 \times 1^4 + 3 \times 2^4 + 2 \times 3^4 + 4^4$
or:
:$479 = 10 \times 1^4 + 4 \times 2^4 + 5 \times 3^4$

Proof:
First note that $5^4 = 625 > 479$.
Then note that $2 \times 4^4 = 512 > 479$.
Hence any expression of $479$ as fourth powers uses no $n^4$ for $n \ge 5$, and uses not more than $1$ instance of $4^4$.
For the remainder, using $2^4$ uses fewer fourth powers than $16$ instances of $1^4$ does.
Now we have:
{{begin-eqn}}
{{eqn | l = 479
      | r = 4^4 + 2 \times 3^4 + 3 \times 2^4 + 13 \times 1^4
}}
{{eqn | r = 4^4 + 1 \times 3^4 + 8 \times 2^4 + 14 \times 1^4
}}
{{eqn | r = 4^4 + 0 \times 3^4 + 13 \times 2^4 + 15 \times 1^4
}}
{{eqn | r = 5 \times 3^4 + 4 \times 2^4 + 10 \times 1^4
}}
{{eqn | r = 4 \times 3^4 + 9 \times 2^4 + 11 \times 1^4
}}
{{eqn | r = 3 \times 3^4 + 14 \times 2^4 + 12 \times 1^4
}}
{{eqn | r = 2 \times 3^4 + 19 \times 2^4 + 13 \times 1^4
}}
{{eqn | r = 1 \times 3^4 + 24 \times 2^4 + 14 \times 1^4
}}
{{eqn | r = 0 \times 3^4 + 29 \times 2^4 + 15 \times 1^4
}}
{{end-eqn}}
and it can be seen that the first and the fourth uses the least number of fourth powers, at $19$.
{{qed}}
Theorem: 559 is not Expressible as Sum of Fewer than 19 Fourth Powers

:$559 = 15 \times 1^4 + 2 \times 2^4 + 2 \times 4^4$
or:
:$559 = 9 \times 1^4 + 4 \times 2^4 + 6 \times 3^4$

Proof:
First note that $5^4 = 625 > 559$.
Then note that $3 \times 4^4 = 768 > 559$.
Hence any expression of $559$ as fourth powers uses no $n^4$ for $n \ge 5$, and uses not more than $2$ instances of $4^4$.
For the remainder, using $2^4$ uses fewer fourth powers than $16$ instances of $1^4$ does.
Now we have:
{{begin-eqn}}
{{eqn | l = 559
      | r = 2 \times 4^4 + 0 \times 3^4 + 2 \times 2^4 + 15 \times 1^4
}}
{{eqn | r = 1 \times 4^4 + 3 \times 3^4 + 3 \times 2^4 + 12 \times 1^4
}}
{{eqn | r = 1 \times 4^4 + 2 \times 3^4 + 8 \times 2^4 + 13 \times 1^4
}}
{{eqn | r = 1 \times 4^4 + 1 \times 3^4 + 13 \times 2^4 + 14 \times 1^4
}}
{{eqn | r = 1 \times 4^4 + 0 \times 3^4 + 18 \times 2^4 + 15 \times 1^4
}}
{{eqn | r = 6 \times 3^4 + 4 \times 2^4 + 9 \times 1^4
}}
{{eqn | r = 5 \times 3^4 + 9 \times 2^4 + 10 \times 1^4
}}
{{eqn | r = 4 \times 3^4 + 14 \times 2^4 + 11 \times 1^4
}}
{{eqn | r = 3 \times 3^4 + 19 \times 2^4 + 12 \times 1^4
}}
{{eqn | r = 2 \times 3^4 + 24 \times 2^4 + 13 \times 1^4
}}
{{eqn | r = 1 \times 3^4 + 29 \times 2^4 + 14 \times 1^4
}}
{{eqn | r = 0 \times 3^4 + 34 \times 2^4 + 15 \times 1^4
}}
{{end-eqn}}
and it can be seen that the first and the sixth use the least number of fourth powers, at $19$.
{{qed}}
Theorem: Free Module on Set is Free

Let $R$ be a ring with unity.
Let $I$ be a set.
Let $R^{\paren I}$ be the free $R$-module on $I$.
Then $R^{\paren I}$ is a free $R$-module.

Proof:
From Canonical Basis of Free Module on Set is Basis, $R^{\paren I}$ has a basis.
{{qed}}
Category:Free Modules
jpeodkx099o9yv0mnusg2golguk0j9d
Theorem: Canonical Basis of Free Module on Set is Basis

Let $R$ be a ring with unity.
Let $I$ be a set.
Let $R^{\paren I}$ be the free $R$-module on $I$.
Let $B$ be its canonical basis.
Then $B$ is a basis of $R^{\paren I}$.

Proof:
{{refactor|I'm not sure it's completely necessary just to repeat everything in the exposition}}
Let $R$ be a ring with unity.
Let $I$ be a set.
Let $R^{\paren I}$ be the free $R$-module on $I$.
Let $B$ be its canonical basis.
Recall the definition of canonical basis:
{{:Definition:Canonical Basis of Free Module on Set}}
It is to be shown that $B$ is a basis.
{{ProofWanted}}
Hence the result.
Category:Free Modules
818t7v80lurzpmg4p9gkzfdp1k0awaz
Theorem: Korselt's Theorem

Let $n \ge 2$ be an integer.
Then $n$ is a '''Carmichael number''' {{iff}}:
: $(1): \quad n$ is odd
and the following conditions hold for every prime factor $p$ of $n$:
: $(2): \quad p^2 \nmid n$
: $(3): \quad \paren {p - 1} \divides \paren {n - 1}$
where:
:$\divides$ denotes divisibility
:$\nmid$ denotes non-divisibility.

Proof:
=== Sufficient Condition ===
Let $n$ be a Carmichael number:
:$(4): \quad \forall a \in \Z: a \perp n: a^n \equiv a \pmod n$
where $\perp$ denotes coprimality.
Suppose $n$ is even.
Set $a = -1$ in $(4)$.
Then $\paren {-1}^n = 1$ and so:
:$1 \equiv -1 \pmod n$
resulting in $n = 2$.
But as $2$ is not a Carmichael number, it follows that for $n$ to be Carmichael it must be odd.
Thus:
:$(1): \quad n$ is odd
holds.
From the Fundamental Theorem of Arithmetic, let $n$ be expressed as:
:$n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$
where:
:the $p_i$'s are distinct odd primes
:for all $i$, $k_i \ge 1$.
By Conditions for Integer to have Primitive Root there exists a primitive root $a_i$ modulo $p_i^{k_i}$ for each $i$.
In particular:
:$a_i \perp p_i$
By the Chinese Remainder Theorem:
:$\exists a: \forall i: a \equiv a_i \pmod {p_i^{k_i} }, a \perp n$
Consider a particular $i$.
We have:
{{begin-eqn}}
{{eqn | l = a^n
      | o = \equiv
      | r = a
      | rr= \pmod n
      | c = from $(4)$
}}
{{eqn | ll= \leadsto
      | l = a^{n - 1}
      | o = \equiv
      | r = 1
      | rr= \pmod n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a^{n - 1}
      | o = \equiv
      | r = 1
      | rr= \pmod {p_i^{k_i} }
      | c = 
}}
{{eqn | ll= \leadsto
      | l = {a_i}^{n - 1}
      | o = \equiv
      | r = 1
      | rr= \pmod {p_i^{k_i} }
      | c = 
}}
{{end-eqn}}
We have that $a_i$ is a primitive root modulo $p_i^{k_i}$.
Thus:
{{begin-eqn}}
{{eqn | l = \map {\operatorname {ord}_{p_i^{k_i} } } {a_i}
      | r = \map \phi {p_i^{k_i} }
      | c = where $\phi$ is the Euler $\phi$ function
}}
{{eqn | r = p_i^{k_i - 1} \paren {p_i - 1}
      | c = 
}}
{{eqn | o = \divides
      | r = n - 1
      | c = 
}}
{{end-eqn}}
But because $p_i \divides n$:
:$p_i \perp n - 1$
Thus:
:$k_i = 1$
giving that $n$ is square-free, and:
:$p_i - 1 \divides n - 1$
As $i$ is arbitrary, both conditions $(1)$ and $(2)$ of the statement of the theorem are thus fulfilled:
That is:
: $(1): \quad n$ is odd
and for all primes $p$ such that $p \divides n$:
: $(2): \quad p^2 \nmid n$
: $(3): \quad \paren {p - 1} \divides \paren {n - 1}$
{{qed|lemma}}
Theorem: Carmichael Number has 3 Odd Prime Factors

Let $n$ be a Carmichael number.
Then $n$ has at least $3$ distinct odd prime factors.

Proof:
By Korselt's Theorem, $n$ is odd.
Therefore $n$ has at least $1$ odd prime factor.
By Korselt's Theorem, for each prime factor of $n$:
:$p^2 \nmid n$
:$\paren {p - 1} \divides \paren {n - 1}$
Suppose $n = p^k$ for some odd prime $p$.
By Korselt's Theorem, $k = 1$.
However by definition of a Carmichael Number, $n$ cannot be prime.
Therefore $n$ has at least $2$ distinct odd prime factors.
Suppose $n = p^a q^b$ for distinct odd primes $p$ and $q$.
By Korselt's Theorem, the following holds:
:$a = b = 1$
:$n = p q$
:$\paren {p - 1} \divides \paren {n - 1}$
:$\paren {q - 1} \divides \paren {n - 1}$
Hence:
{{begin-eqn}}
{{eqn | l = \paren {p - 1}
      | o = \divides
      | r = \paren {n - 1 - q \paren {p - 1} }
}}
{{eqn | r = p q - 1 - p q + q
}}
{{eqn | r = q - 1
}}
{{end-eqn}}
Swapping $p$ and $q$ yields $\paren {q - 1} \divides \paren {p - 1}$.
Hence $p - 1 = q - 1$ and $p = q$, which is a contradiction.
Therefore $n$ has at least $3$ distinct odd prime factors.
{{qed}}
Theorem: Intersection of Submodules is Submodule/General Result

Let $S$ be a set of submodules of $M$.
Then the intersection $\bigcap S$ is a submodule of $M$.

Proof:
From Intersection of Subgroups is Subgroup:General Result, it follows that $\bigcap S$ is a subgroup of $M$.
As a subgroup is closed for its operation, it follows that for all $x, y \in \bigcap S$, we have $x + y, y + x \in \bigcap S$.
As $M$ is an $R$-module, and the addition $+$ on $\bigcap S$ is the restriction of the addition on $M$, it follows that $x + y = y + x$.
Hence, $\bigcap S$ is an abelian group.
Let $\lambda \in R$, and let $x \in \bigcap S$.
Let $H$ be a submodule of $M$ such that $H \in S$.
By definition of intersection, it follows that $x \in H$.
As a submodule is closed for scalar product, it follows that $\lambda \circ x, x \circ \lambda \in H$.
As this is true for all submodules in the set $S$, it follows that $\lambda \circ x, x \circ \lambda \in \bigcap S$.
Hence, $\bigcap S$ is closed for scalar product.
Next, we show that $\struct {\bigcap S, +, \circ}_R$ satisfy the left module axioms, and the right module axioms.
By definition of $R$-module, each of these axioms are satisfied by $\struct {G, +, \circ}_R$.
As the addition $+$ and the scalar multiplication $\circ$ on $\bigcap S$ are the restrictions of the operations $+, \circ$ on $M = \struct {G, +, \circ}_R$, it follows that the axioms also are satisfied by $\struct {\bigcap S, +, \circ}_R$.
For instance, the {{Left-module-axiom|1}} can be shown by:
{{begin-eqn}}
{{eqn | q = \forall x, y \in \bigcap S
      | l = x + y
      | o = \in
      | r = \bigcap S
      | c = as $\bigcap S$ is closed for addition
}}
{{eqn | q = \forall \lambda \in R
      | l = \lambda \circ x
      | o = \in
      | r = \bigcap S
      | c = as $\bigcap S$ is closed for scalar product
}}
{{eqn | l = \lambda \circ y
      | o = \in
      | r = \bigcap S
      | c = as $\bigcap S$ is closed for scalar product
}}
{{eqn | ll= \leadsto
      | l = \paren {\lambda \circ x} + \paren {\lambda \circ y}
      | o = \in
      | r = \bigcap S
      | c = by combining the three statements above
}}
{{eqn | ll= \leadsto
      | l = \paren {\lambda \circ x} + \paren {\lambda \circ y}
      | o = \in
      | r = G
      | c = as $\bigcap S \subseteq G$
}}
{{eqn | ll= \leadsto
      | l = \paren {\lambda \circ x} + \paren {\lambda \circ y}
      | r = \lambda \circ \paren {x + y}
      | c = {{Module-axiom|1}} as applied to $\struct {G, +, \circ}_R$
}}
{{end-eqn}}
Hence, $\struct {\bigcap S, +, \circ}_R$ is a submodule of $M$.
{{qed}}
Theorem: Substitution in Big-O Estimate/Real Analysis

Let $f$ and $g$ be real-valued or complex-valued functions defined on a neighborhood of $+ \infty$ in $\R$.
Let $f = \map \OO g$, where $\OO$ denotes big-O notation.
Let $h$ be a real-valued defined on a neighborhood of $+ \infty$ in $\R$.
Let $\ds \lim_{x \mathop \to +\infty} \map h x = +\infty$.
Then:
:$f \circ h = \map \OO {g \circ h}$ as $x \to +\infty$.

Proof:
{{ProofWanted}}
Category:Big-O Notation
3p4oafq4g08ec0l09shqdiyoizg7y1n
Theorem: Product of Big-O Estimates/Sequences

Let $\sequence {a_n}, \sequence {b_n}, \sequence {c_n}, \sequence {d_n}$ be sequences of real or complex numbers.
Let:
:$a_n = \map \OO {b_n}$
:$c_n = \map \OO {d_n}$
where $\OO$ denotes big-$\OO$ notation.
Then:
:$a_n c_n = \map \OO {b_n d_n}$

Proof:
Since:
:$a_n = \map \OO {b_n}$
there exists a positive real number $C_1$ and natural number $N_1$ such that: 
:$\size {a_n} \le C_1 \size {b_n}$
for all $n \ge N_1$. 
Similarly, since: 
:$c_n = \map \OO {d_n}$
there exists a positive real number $C_2$ and natural number $N_2$ such that: 
:$\size {c_n} \le C_2 \size {d_n}$
for all $n \ge N_2$. 
Let:
:$N = \max \set {N_1, N_2}$
Then, for $n \ge N$, we have: 
{{begin-eqn}}
{{eqn | l = \size {a_n c_n}
      | r = \size {a_n} \size {c_n}
}}
{{eqn | o = \le
      | r = C_1 \size {b_n} \size {c_n}
      | c = since $n \ge N_1$
}}
{{eqn | o = \le
      | r = C_1 C_2 \size {b_n} \size {d_n}
      | c = since $n \ge N_2$
}}
{{eqn | r = C_1 C_2 \size {b_n d_n}
}}
{{end-eqn}}
giving:
:$a_n c_n = \map \OO {b_n d_n}$
{{qed}}
Category:Big-O Notation
ccm3rec739kqlgb7464wkysgpzi5z0l