nyuuzyou/wikis huggingface dataset:
Cycle Matroid is Matroid

== Theorem ==
Let $G = \struct {V, E}$ be a graph.
Let $\struct {E, \mathscr I}$ be the cycle matroid of $G$.
Then $\struct {E, \mathscr I}$ is a matroid. 
== Proof ==
It needs to be shown that $\mathscr I$ satisfies the matroid axioms $(\text I 1)$, $(\text I 2)$ and $(\text I 3)$.
=== Matroid Axiom $(\text I 1)$ ===
$\ds \O \subset E$ is the empty subgraph, which does not contain any cycles.
Hence, by definition of the cycle matroid, $\ds \O \in \mathscr I$.
=== Matroid Axiom $(\text I 2)$ ===
=== Matroid Axiom $(\text I 3)$ ===
== Sources ==
* Chapter $1.$ $\S 3.$ Examples of Matroids
Category:Matroid Theory
Cycle Notation/Examples/Permutations in S8

== Examples of Cycle Notation ==
Consider the permutations in $S_8$, presented in two-row notation as:
These can be expressed in cycle notation as:
We have that:
$\pi$ is of order $\lcm {4, 3} = 12$, and is of odd parity
$\rho$ is of order $2$, and is of even parity
$\pi \rho$ and $\rho \pi$ are both of order $\lcm {4, 2} = 4$, and are of odd parity
$\pi^2 \rho$ is of order $\lcm {6, 2} = 6$, and is of even parity.
== Sources ==
* : Chapter $9$: Permutations: Exercise $1$
Category:Examples of Cycle Notation
Cycle does not Contain Subcycles

== Theorem ==
Let $G$ be a cycle graph.
Then the only cycle graph that is a subgraph of $G$ is $G$ itself.
== Proof ==
 $G$ contains a subgraph $C$ such that:
:$C$ is a cycle graph
:$C \ne G$ is non-empty.
Then there exists some vertex $v$ that is not in $C$.
Let $u$ be any vertex of $C$.
Since $G$ is a cycle graph, it is connected.
Therefore there is a walk from $u$ to $v$ in $G$.
There must be some vertex $x$ that is the last vertex in $C$ along that walk.
Therefore, $x$ is adjacent to a vertex not in $C$.
Thus it has a degree of at least $3$.
But $G$ is a cycle graph and every vertex in a cycle graph has degree $2$.
The result follows by Proof by Contradiction.
Category:Cycles (Graph Theory)
Cycle in Balanced Signed Graph

== Theorem ==
Let $G$ be a balanced signed graph.
Let $C$ be a cycle in $G$.
Then $C$ has an even number of negative edges.
== Proof ==
Let $G$ be a balanced signed graph.
Since $G$ is balanced, we can colour the vertices black and white, say, so that every edge has a black and a white end.
Consider any cycle $C$ in $G$.
As we proceed around $C$, there is a change of colour when we traverse a negative edge.
Since this is a cycle, the last colour is the same as the first one.
So there must be an even number of colour changes.
So there must be an even number of negative edges in $C$.
Category:Cycles (Graph Theory)
Category:Balanced Signed Graphs
Cycle of Subsets implies Set Equality

== Theorem ==
Let $A_1, A_2, \dotsc, A_n$ be sets.
Let:
:$\forall k \in \set {2, 3, \dotsc, n}: A_{k - 1} \subseteq A_k$
and:
:$A_n \subseteq A_1$
Then:
:$\forall j, k \in \set {1, 2, \dotsc, n}: A_j = A_k$
== Proof ==
Consider the set of sets $\mathbb A = \set {A_1, A_2, \dotsc, A_n}$
Consider the relational structure $S = \struct {\mathbb A, \subseteq}$.
We have from Subset Relation is Ordering that $S$ is an ordered structure.
The result follows from Ordering Cycle implies Equality.
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 2$: Sets and Subsets: Exercise $3$
Category:Subsets
Cyclic Group/Examples/Subgroup of Multiplicative Group of Complex Numbers Generated by i

== Example of Cyclic Group ==
Consider the multiplicative group of complex numbers $\struct {\C_{\ne 0}, \times}$.
Consider the subgroup $\gen i$ of $\struct {\C_{\ne 0}, \times}$ generated by $i$.
Then $\gen i$ is an (finite) cyclic group of order $4$.
== Proof ==
We have that $\gen i$ is subgroup generated by a single element of $\struct {\C_{\ne 0}, \times}$
By definition, $\gen i$ is a cyclic group.
By Example: Order of Imaginary Unit in Multiplicative Group of Complex Numbers, $i$ is of finite order $4$.
The result follows by definition of finite cyclic group.
== Sources ==
* : $\S 39$. Cyclic groups: $(2)$
Category:Examples of Cyclic Groups
Cyclic Group/Examples/Subgroup of Multiplicative Group of Real Numbers Generated by 2

== Example of Cyclic Group ==
Consider the multiplicative group of real numbers $\struct {\R_{\ne 0}, \times}$.
Consider the subgroup $\gen 2$ of $\struct {\R_{\ne 0}, \times}$ generated by $2$.
Then $\gen 2$ is an infinite cyclic group.
== Proof ==
We have that $\gen 2$ is subgroup generated by a single element of $\struct {\R_{\ne 0}, \times}$
By definition, $\gen 2$ is a cyclic group.
By Example: Order of Element of Multiplicative Group of Real Numbers, $2$ is of infinite order.
The result follows by definition of infinite cyclic group.
== Sources ==
* : $\S 39$. Cyclic groups: $(1)$
Category:Examples of Cyclic Groups
Cyclic Group/Group Presentation

== Generator of the Cyclic Group of Order $n$ ==
The presentation of a finite cyclic group of order $n$ is:
:$C_n = \gen {a: a^n = e}$
== Proof ==
The elements of $\gen {a: a^n = e}$ are:
:$a, a^2, a^3, \ldots, a^{n - 1}, a^n, a^{n + 1}, a^{n + 2}, \ldots$
However, we have that:
:$a^n = e$
and so the elements of $\gen {a: a^n = e}$ are:
:$a, a^2, a^3, \ldots, a^{n - 1}, e, e a, e a^2, \ldots$
That is:
:$C_n = \set {a, a^2, \ldots, a^{n - 1}, e}$
and the result follows by definition of cyclic group.
== Sources ==
* : Chapter $4$: Subgroups: Example $4.10$
Category:Cyclic Groups
Category:Examples of Group Presentations
Cyclic Group Elements whose Powers equal Identity

== Theorem ==
Let $G$ be a cyclic group whose identity is $e$ and whose order is $n$.
Let $d \divides n$.
Then there exist exactly $d$ elements $x \in G$ satisfying the equation $x^d = e$.
These are the elements of the group $G_d$ generated by $g^{n / d}$: 
:$G_d = \gen {g^{n / d} }$
== Proof ==
From the argument in Subgroup of Finite Cyclic Group is Determined by Order, it follows that $x$ satisfies the equation $x^d = e$ $x$ is a power of $g^{n/d}$.
Thus there are $d$ solutions to this equation.
== Sources ==
* : Chapter $2$: Subgroups and Cosets: $\S 43 \alpha$
Category:Cyclic Groups
Cyclic Group is Abelian

== Theorem ==
Let $G$ be a cyclic group.
Then $G$ is abelian.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 9$: Cyclic Groups
* : Chapter $2$: Subgroups and Cosets: $\S 43$
* : $0$: Some Conventions and some Basic Facts
* 
Category:Cyclic Groups
Category:Abelian Groups
Category:Cyclic Group is Abelian
Cyclic Group is Abelian/Proof 1

== Theorem ==
== Proof ==
Let $G$ be a cyclic group.
All elements of $G$ are of the form $a^n$, where $n \in \Z$.
Let $x, y \in G: x = a^p, y = a^q$.
From Powers of Group Elements: Sum of Indices:
: $x y = a^p a^q = a^{p + q} = a^{q + p} = a^q a^p = y x$
Thus:
: $\forall x, y \in G: x y = y x$
and $G$ is by definition abelian.
== Sources ==
* : $\S 5.4$. Cyclic groups
* : $\S 39.3$ Cyclic Groups
* : Chapter $4$: Subgroups: Proposition $4.12$
Category:Cyclic Group is Abelian
Cyclic Group is Abelian/Proof 2

== Theorem ==
== Proof ==
We have that Integers under Addition form Abelian Group.
The result then follows from combining:
:Epimorphism from Integers to Cyclic Group
:Epimorphism Preserves Commutativity.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $25$. Cyclic Groups and Lagrange's Theorem: Theorem $25.3$
Category:Cyclic Group is Abelian
Cyclic Group is Simple iff Prime

== Theorem ==
Let $G$ be a cyclic group.
Then $G$ is simple $G$ is a prime group.
== Proof ==
Let $G$ be a cyclic group.
From Cyclic Group is Abelian it follows that $G$ is an abelian group.
The result follows from Abelian Group is Simple iff Prime.
Category:Simple Groups
Category:Cyclic Groups
Cyclic Group of Order 6

== Theorem ==
Let $C_n$ be the cyclic group of order $n$.
Then:
: $C_2 \times C_3 \cong C_6$
: $C_6$ is the internal group direct product of $C_2$ and $C_3$.
== Proof ==
From Group Direct Product of Cyclic Groups noting that $2 \perp 3$:
:$C_2 \times C_3 \cong C_6$
* $C_6$ is the internal group direct product of $C_2$ and $C_3$:
Let $\left({C_6, \circ}\right) = \left \langle {x} \right \rangle$, let $\left({C_2, \circ}\right) = \left \langle {x^3} \right \rangle$, and let $\left({C_3, \circ}\right) = \left \langle {x^2} \right \rangle$.
From Subgroup of Abelian Group is Normal, $C_2 \lhd C_6$ and $C_3 \lhd C_6$.
We can factorise the elements of $C_6$ thus:
:$e = e \circ e, x = x^3 \circ \left({x^2}\right)^2, x^2 = e \circ x^2, x^3 = x^3 \circ e, x^4 = e \circ \left({x^2}\right)^2, x^5 = x^2 \circ x^3$ 
Hence the result.
Category:Examples of Cyclic Groups
Category:Groups of Order 6
Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n

== Theorem ==
Let $n \in \Z_{\ge 0}$ be an integer.
Let $\struct {\Z / n \Z, +, \cdot}$ be the ring of integers modulo $n$.
Let $U = \struct {\paren {\Z / n \Z}^\times, \cdot}$ denote the group of units of $\struct {\Z / n \Z, +, \cdot}$.
Let $C_8$ denote the cyclic group of order $8$
Then:
:$U$ and $C_8$ are not isomorphic.
== Proof 1 ==
== Proof 2 ==
Category:Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n
Category:Ring of Integers Modulo m
Category:Cyclic Group of Order 8
Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n/Lemma

== Lemma for Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo $n$ ==
There are only $5$ numbers $n$ with the property that $\map \phi n = 8$, and they are $15$, $16$, $20$, $24$ and $30$.
== Proof ==
Let $p$ be a prime factor of $n$.
By Euler Phi Function is Multiplicative:
:$p - 1 = \map \phi p \divides \map \phi n = 8$
so:
:$p \in \set {2, 3, 5}$
Let $i, j, k \in \Z^{\ge 0}$ such that $n = 2^i 3^j 5^k$.
By Euler Phi Function is Multiplicative:
:$8 = \map \phi n = \map \phi {2^i} \map \phi {3^j} \map \phi {5^k}$
has only $5$ solutions:
:$\tuple {i, j, k} = \tuple {0, 1, 1}, \tuple {4, 0, 0}, \tuple {2, 0, 1}, \tuple {3, 1, 0}$ and $\tuple {1, 1, 1}$.
Category:Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n
Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n/Proof 1

== Theorem ==
== Proof ==
=== Lemma ===
 $U$ and $C_8$ are isomorphic.
:$\order U = \order {C_8} = 8$
From Order of Group of Units of Integers Modulo n we have that
:$8 = \order U = \map \phi n$
where $\phi$ denotes the Euler $\phi$-function.
From the :
:there are $5$ numbers $n$ with the property that $\map \phi n = 8$, and they are $15$, $16$, $20$, $24$ and $30$.
Hence:
Therefore, no multiplicative group of integers mod $n$ is isomorphic to $C_8$.
Category:Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n
Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n/Proof 2

== Theorem ==
== Proof ==
 $U$ and $C_8$ are isomorphic.
:$\order U = \order {C_8} = 8$
From Order of Group of Units of Integers Modulo n we have that
:$8 = \order U = \map \phi n$
where $\phi$ denotes the Euler $\phi$-function.
$\map \phi 1 = \map \phi 2 = 1$, so $n > 2$.
By Cyclicity Condition for Units of Ring of Integers Modulo n, either:
:$n = p^\alpha$
or:
:$n = 2 p^\alpha$
where $p \ge 3$ is prime and $\alpha \ge 1$.
In either case, we get:
:$8 = \map \phi n = p^{\alpha - 1} \paren{p - 1}$
so $p - 1 \divides 8$, but $p \ge 3$, so $p \in \set {3,5}$.
If $p = 3$, we get:
:$8 = 3^{\alpha - 1}\times 2$
contradiction.
If $p = 5$, we get:
:$8 = 5^{\alpha - 1}\times 4$
contradiction.
Category:Cyclic Group of Order 8 is not isomorphic to Group of Units of Integers Modulo n
Cyclic Groups of Same Order are Isomorphic

== Theorem ==
Two cyclic groups of the same order are isomorphic to each other.
== Proof ==
Let $G_1$ and $G_2$ be cyclic groups, both of finite order $k$.
Let $G_1 = \gen a, G_2 = \gen b$.
Then, by the definition of a cyclic group:
:$\order a = \order b = k$
Also, by definition:
:$G_1 = \set {a^0, a^1, \ldots, a^{k - 1} }$
and:
:$G_2 = \set {b^0, b^1, \ldots, b^{k - 1} }$
Let us set up the obvious bijection:
:$\phi: G_1 \to G_2: \map \phi {a^n} = b^n$
The next task is to show that $\phi$ is an isomorphism.
Note that $\map \phi {a^n} = b^n$ holds for all $n \in \Z$, not just where $0 \le n < k$, as follows:
Let $n \in \Z: n = q k + r, 0 \le r < k$, by the Division Theorem.
Then, by Element to Power of Remainder:
:$a^n = a^r, b^n = b^r$
Thus:
:$\map \phi {a^n} = \map \phi {a^r} = b^r = b^n$
Now let $x, y \in G_1$.
Since $G_1 = \gen a$, it follows that:
:$\exists s, t \in \Z: x = a^s, y = a^t$
Thus:
So $\phi$ is a homomorphism.
As $\phi$ is bijective, $\phi$ is an isomorphism from $G_1$ to $G_2$.
Thus $G_1 \cong G_2$ and the result is proved.
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 9$: Cyclic Groups
* : $\S 1.7$: Theorem $9$
* : $0$: Some Conventions and some Basic Facts: Exercise $2$
* : $\S 46$. Isomorphic groups: Worked Example
* : Chapter $4$: Subgroups: Example $4.8$
Category:Cyclic Groups
Category:Group Isomorphisms
Cyclic Permutation/Examples/Non-Cyclic Element of S4

== Example of Non-Cyclic Permutation ==
Not all permutations are cycles.
Here is an example (written in two-row notation) of a permutation of the Symmetric Group on 4 Letters which is not a cycle:
:$\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 1 & 4 & 3 
\end{pmatrix}$
== Sources ==
* : Chapter $9$: Permutations: Example $9.3$
Category:Examples of Cyclic Permutations
Cyclic Permutation/Examples/Symmetric Group on 3 Letters

== Examples of Cyclic Permutations ==
Each of the non-identity elements of the Symmetric Group on 3 Letters is a cyclic permutation.
Expressed in cycle notation, they are as follows:
== Sources ==
* : Chapter $9$: Permutations: Example $9.3$
Category:Examples of Cyclic Permutations
Cyclic Permutation of 3-Digit Multiple of 37

== Theorem ==
Let $n$ be a $3$-digit multiple of $37$.
Let $m$ be an integer formed by cyclically permuting the digits of $n$.
Then $m$ is also a multiple of $37$.
== Proof ==
== Sources ==
* : $37$
* : $37$
Category:Recreational Mathematics
Category:37
Cyclic Permutation of Kaprekar Number

== Theorem ==
Let $n$ be a Kaprekar number of $k$ digits.
Let $m$ be an integer formed from a cyclic permutation of the digits of $n$.
Let $m$ be squared and the result split into $2$ parts, where the $2$nd part is of $k$ digits.
Let these two parts be added, in the way of operating on a Kaprekar number.
If the result is more than $k$ digits long, split that into $2$ parts, where the $2$nd part is of $k$ digits, and add the parts.
The result will be another cyclic permutation of the digits of $n$.
== Proof ==
== Examples ==
== Sources ==
* : $297$
* : $297$
Category:Kaprekar Numbers
Category:Cyclic Permutation of Kaprekar Number
Cyclic Permutation of Kaprekar Number/Examples/2727

== Example of Cyclic Permutation of Kaprekar Number ==
$2727$ is a cyclic permutation of the $4$-digit Kaprekar number $7272$.
Thus we have:
and it is seen that $7272$ is a (trivial) cyclic permutation of $7272$.
== Sources ==
* : $297$
* : $297$
Category:Cyclic Permutation of Kaprekar Number
Cyclic Permutation of Kaprekar Number/Examples/972

== Example of Cyclic Permutation of Kaprekar Number ==
$972$ is a cyclic permutation of the $3$-digit Kaprekar number $297$.
Thus we have:
and it is seen that $729$ is another cyclic permutation of $297$.
== Sources ==
* : $297$
* : $297$
Category:Cyclic Permutation of Kaprekar Number
Cyclic Permutations of 5-Digit Multiples of 41

== Theorem ==
Let $n$ be a multiple of $41$ with $5$ digits.
Let $m$ be an integer formed by cyclically permuting the digits of $n$.
Then $m$ is a multiple of $41$.
== Proof ==
First we note that $10^5 - 1 = 41 \times 271 \times 9$
$10$ generates exactly $5$ elements in $\Z_{41}$ Subgroup Generated by One Element is Cyclic
In $\Z_{41}$: $ \set {10^1, 10^2, 10^3, 10^4, 10^5} \leadsto \set {10, 18, 16, 37, 1}$
Let $n$ be a multiple of $41$ with $5$ digits.
Then we have:
Let $m$ be an integer formed by cyclically permuting the digits of $n$.
Then we have:
Therefore $m$ is a multiple of $41$.
== Also see ==
* Numbers whose Cyclic Permutations of 3-Digit Multiples are Multiples
== Sources ==
* : $41$
* : $41$
Category:Number Theory
Category:41
Cycloid has Tautochrone Property

== Theorem ==
Let a wire $AB$ be curved into the shape of an arc of a cycloid such that:
:$A$ is at the cusp
:$B$ is the highest point of the arc
and inverted so that its cusps are uppermost and on the same horizontal line.
Thus $B$ is the lowest point of the arc.
Let $AB$ be embedded in a constant and uniform gravitational field where Acceleration Due to Gravity is $g$.
Let a bead $P$ be released from anywhere on the wire between $A$ and $B$ to slide down without friction to $B$.
Then the time taken for $P$ to slide to $B$ is:
:$T = \pi \sqrt {\dfrac a g}$
independently of the point from which $P$ is released.
That is, a cycloid is a tautochrone.
== Proof ==
:
By the Principle of Conservation of Energy, the speed of the bead at a particular height is determined by its loss in potential energy in getting there.
Thus, at the point $\tuple {x, y}$, we have:
:$(1): \quad v = \dfrac {\d s} {\d t} = \sqrt {2 g y}$
This can be written:
Thus the time taken for the bead to slide down the wire is given by:
:$\ds T_1 = \int \sqrt {\dfrac {\d x^2 + \d y^2} {2 g y} }$
From Equation of Cycloid, we have:
:$x = a \paren {\theta - \sin \theta}$
:$y = a \paren {1 - \cos \theta}$
Substituting these in the above integral:
:$\ds T_1 = \int_0^{\theta_1} \sqrt {\dfrac {2 a^2 \paren {1 - \cos \theta} } {2 a g \paren {1 - \cos \theta} } } \rd \theta = \theta_1 \sqrt {\dfrac a g}$
This is the time needed for the bead to reach the bottom when released when $\theta_1 = \pi$, and so:
:$T_1 = \pi \sqrt {\dfrac a g}$
Now suppose the bead is released at any intermediate point $\tuple {x_0, y_0}$.
Take equation $(1)$ and replace it with:
:$v = \dfrac {\d s} {\d t} = \sqrt {2 g \paren {y - y_0} }$
Thus the total time to reach the bottom is:
Setting:
:$u = \dfrac {\cos \frac 1 2 \theta} {\cos \frac 1 2 \theta_0}$
and so:
:$\d u = -\dfrac 1 2 \dfrac {\sin \frac 1 2 \theta \rd \theta} {\cos \frac 1 2 \theta_0}$
Then $(2)$ becomes:
That is, wherever the bead is released from, it takes that same time to reach the bottom.
Hence the result.
== Also known as ==
== Also see ==
* Tautochrone Problem
* Brachistochrone is Cycloid, in which it is shown that a cycloid is also the shape for which the time is shortest.
== Historical Note ==
== Sources ==
* : Chapter $\text{V}$: "Greatness and Misery of Man"
* : Chapter $\text{VIII}$: Nature or Nurture?
* : $\S 2.11$: Problem $4$
* : Chapter $\text {A}.17$: Huygens ()
* : Chapter $\text {B}.21$: The Cycloid
* 
* 
Category:Cycloid has Tautochrone Property
Category:Tautochrone Problem
Category:Cycloids
Cyclotomic Polynomial has Integer Coefficients

== Theorem ==
Let $n \in \Z_{>0}$ be a positive integer.
Then the $n$th cyclotomic polynomial $\map {\Phi_n} x$ has integer coefficients.
== Proof ==
The proof proceeds by strong induction on $n$.
For all $n \in \Z_{>0}$, let $\map P n$ be the proposition:
:$\map {\Phi_n} x$ has integer coefficients
=== Basis for the Induction ===
By First Cyclotomic Polynomial:
:$\map {\Phi_1} x = x - 1$
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that if $\map P j$ is true, for all $j$ such that $0 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.
This is the induction hypothesis:
:For all $j$ such that $0 \le j \le k$, $\map {\Phi_j} x$ has integer coefficients
from which it is to be shown that:
:$\map {\Phi_{k + 1} } x$ has integer coefficients
=== Induction Step ===
This is the induction step:
Suppose $\map P j$ holds for all $j \le k$.
From Product of Cyclotomic Polynomials:
:$\ds \prod_{d \mathop \divides {k + 1} } \map {\Phi_d} x = x^{k + 1} - 1$
That is:
:$\ds \map {\Phi_{k + 1} } x \times \prod_{\substack {d \mathop \divides {k + 1} \\ d \mathop \ne {k + 1} } } \map {\Phi_d} x = x^{k + 1} - 1$
By the induction hypothesis:
:$\ds \prod_{\substack {d \mathop \divides {k + 1} \\ d \mathop \ne {k + 1} } } \map {\Phi_d} x$
is a monic polynomial with integer coefficients, and thus primitive.
From Content of Polynomial is Multiplicative it follows that $\map {\Phi_{k + 1} } x$ has integer coefficients.
Category:Cyclotomic Polynomials
Cyclotomic Polynomial of Index times Prime Power

== Theorem ==
Let $n, k \ge 1$ be natural numbers.
Let $p$ be a prime number.
Let $\Phi_n$ denote the $n$th cyclotomic polynomial.
Then $\map {\Phi_{p^k n}} x = \begin{cases}
\map {\Phi_n} {x^{p^k}} & \text{if } p \divides n\\
\dfrac {\map {\Phi_n} {x^{p^k}}} {\map {\Phi_n} {x^{p^{k - 1}}}} & \text{if } p \nmid n \end{cases}$
== Proof ==
Suppose $p \divides n$.
Then for all $m \in \Z$:
Hence:
Now suppose $p \nmid n$.
We still have $p \divides p n$.
Write $p^k = p^{k - 1} p n$.
Notice that the result we proved above holds trivially for $k = 0$:
:$\map {\Phi_{p^0 n} } x = \map {\Phi_n } x = \map {\Phi_n } {x^1} = \map {\Phi_n } {x^{p^0}}$
Hence from the above:
:$\map {\Phi_{p^k n} } x = \map {\Phi_{p n}} {x^{p^{k - 1}}}$
We need the following result:
:the sets $\set {m \in \Z: m \perp p n}$ and $\set {p r: r \perp n}$ are disjoint and has union $\set {m \in \Z: m \perp n}$
First to show that they are indeed disjoint:
Suppose $x \in \set {p r: r \perp n}$.
Then $p \divides x$.
Since $p \divides p n$:
:$x \not \perp p n$
and thus:
:$x \notin \set {m \in \Z: m \perp p n}$
Hence the sets are disjoint.
Now we show that their union is indeed $\set {m \in \Z: m \perp n}$.
By Divisor of One of Coprime Numbers is Coprime to Other:
:$\forall m \in \Z: m \perp p n \implies \paren {m \perp p \land m \perp n}$
This gives:
:$\set {m \in \Z: m \perp p n} \subseteq \set {m \in \Z: m \perp n}$
Let $x \in \set {p r: r \perp n}$.
We are given that $p \perp n$.
By Integer Coprime to all Factors is Coprime to Whole:
:$x \perp n$
Hence $x \in \set {m \in \Z: m \perp n}$.
This gives:
:$\set {p r: r \perp n} \subseteq \set {m \in \Z: m \perp n}$
By Union of Subsets is Subset:
:$\set {m \in \Z: m \perp p n} \cup \set {p r: r \perp n} \subseteq \set {m \in \Z: m \perp n}$
For the other direction, we let $x \notin \set {m \in \Z: m \perp p n} \cup \set {p r: r \perp n}$.
Then by De Morgan's Laws (Set Theory)/Set Complement:
:$x \in \set {m \in \Z: m \not \perp p n} \cap \set {p r: r \not \perp n}$.
By definition of intersection:
:$x \in \set {p r: r \not \perp n}$
Thus:
:$\exists d \in \Z: d > 1: d \divides r \divides x \land d \divides n$
Therefore $x \not \perp n$.
This gives:
:$x \notin \set {m \in \Z: m \perp n}$
Hence:
:$\set {m \in \Z: m \perp n} \subseteq \set {m \in \Z: m \perp p n} \cup \set {p r: r \perp n}$
and we have our result by definition of set equality.
Therefore:
as required.
Category:Cyclotomic Polynomials
Cyclotomic Polynomial of Prime Index

== Theorem ==
Let $p$ be a prime number.
The $p$th cyclotomic polynomial is:
:$\map {\Phi_p} x = x^{p - 1} + x^{p - 2} + \cdots + x + 1$
== Proof ==
From Product of Cyclotomic Polynomials:
:$\map {\Phi_p} x \map {\Phi_1} x = x^p - 1$
Thus from Sum of Geometric Sequence:
:$\map {\Phi_p} x = \dfrac {x^p - 1} {x - 1} = x^{p - 1} + x^{p - 2} + \cdots + x + 1$
Category:Examples of Cyclotomic Polynomials
Cyclotomic Ring/Examples/5th

== Examples of Cyclotomic Rings ==
The $5$th cyclotomic ring is the algebraic structure:
:$\struct {\Z \sqbrk {i \sqrt 5}, +, \times}$
where $\Z \sqbrk {i \sqrt 5}$ is the set $\set {a + i b \sqrt 5: a, b \in \Z}$.
$\struct {\Z \sqbrk {i \sqrt 5}, +, \times}$ is a ring.
== Proof ==
We have that $\Z \sqbrk {i \sqrt 5}$ is a subset of the Field of Complex Numbers $\struct {\C, +, \times}$.
So to prove that $\struct {\Z \sqbrk {i \sqrt 5}, +, \times}$ is a ring it is sufficient to demonstrate that $\struct {\Z \sqbrk {i \sqrt 5}, +, \times}$ fulfils the conditions of the Subring Test.
First we note that setting $a = 1, b = 0$ we have that $1 + 0 i \in \Z \sqbrk {i \sqrt 5}$ and so $\Z \sqbrk {i \sqrt 5} \ne \O$.
Let $z_1 = a_1 + i b_1 \sqrt 5$ and $z_2 = a_2 + i b_2 \sqrt 5$ be arbitrary elements of $\Z \sqbrk {i \sqrt 5}$
Then:
and:
The Subring Test is satisfied, and so $\struct {\Z \sqbrk {i \sqrt 5}, +, \times}$ is a ring.
== Sources ==
* : Chapter $9$: Rings: Exercise $19$
Category:Cyclotomic Rings