avewright/proofwiki-math huggingface dataset:
Theorem: Euler's Formula

Let $z \in \C$ be a complex number.
Then:
:$e^{i z} = \cos z + i \sin z$

Proof:
As Complex Sine Function is Absolutely Convergent and Complex Cosine Function is Absolutely Convergent, we have:
{{begin-eqn}}
{{eqn | l = \cos z + i \sin z
      | r = \sum_{n \mathop = 0}^\infty \paren {-1}^n \dfrac {z^{2 n} } {\paren {2 n}!} + i \sum_{n \mathop = 0}^\infty \paren {-1}^n \dfrac {z^{2 n + 1} } {\paren {2 n + 1}!}
      | c = {{Defof|Complex Cosine Function}} and {{Defof|Complex Sine Function}}
}}
{{eqn | r = \sum_{n \mathop = 0}^\infty \paren {\paren {-1}^n \dfrac {z^{2 n} } {\paren {2 n}!} + i \paren {-1}^n \dfrac {z^{2 n + 1} } {\paren {2 n + 1}!} }
      | c = Sum of Absolutely Convergent Series
}}
{{eqn | r = \sum_{n \mathop = 0}^\infty \paren {\dfrac {\paren {i z}^{2 n} } {\paren {2 n}!} + \dfrac {\paren {i z}^{2 n + 1} } {\paren {2 n + 1}!} }
      | c = {{Defof|Imaginary Unit}}
}}
{{eqn | r = \sum_{n \mathop = 0}^\infty \dfrac {\paren {i z}^n} {n!}
}}
{{eqn | r = e^{i z}
      | c = {{Defof|Complex Exponential Function}}
}}
{{end-eqn}}
{{qed}}
Theorem: Euler's Formula

Let $z \in \C$ be a complex number.
Then:
:$e^{i z} = \cos z + i \sin z$

Proof:
Consider the differential equation:
:$D_z \map f z = i \cdot \map f z$
=== Step 1 ===
We will prove that $z = \cos \theta + i \sin \theta$ is a solution.
{{begin-eqn}}
{{eqn | l = z
      | r = \cos \theta + i \sin \theta
      | c = 
}}
{{eqn | l = \frac {\d z} {\d \theta}
      | r = -\sin \theta + i \cos \theta
      | c = Derivative of Sine Function, Derivative of Cosine Function, Linear Combination of Derivatives
}}
{{eqn | r = i^2 \sin \theta + i\cos \theta
      | c = $i^2 = -1$
}}
{{eqn | r = i \paren {i \sin \theta + \cos \theta}
}}
{{eqn | r = i z
}}
{{end-eqn}}
{{qed|lemma}}
=== Step 2 ===
We will prove that $y = e^{i\theta}$ is a solution.
{{begin-eqn}}
{{eqn | l = y
      | r = e^{i\theta}
      | c = 
}}
{{eqn | l = \frac {\d y} {\d \theta}
      | r = i e^{i \theta}
      | c = Derivative of Exponential Function, Chain Rule for Derivatives, Linear Combination of Derivatives
}}
{{eqn | r = i y
}}
{{end-eqn}}
{{qed|lemma}}
=== Step 3 ===
Consider the initial condition $\map f 0 = 1$.
{{begin-eqn}}
{{eqn | l = \bigvalueat y {\theta \mathop = 0}
      | r = e^{0 i}
}}
{{eqn | r = 1
}}
{{eqn | l = \bigvalueat z {\theta \mathop = 0}
      | r = \cos 0 + i \sin 0
}}
{{eqn | r = 1
}}
{{end-eqn}}
So $y$ and $z$ are both particular solutions.
But a particular solution to a differential equation is unique.
{{MissingLinks|"Specific solution" and the proof that such a specific solution is unique.}}
Therefore $y = z$, that is, $e^{i \theta} = \cos \theta + i \sin \theta$.
{{qed}}
Theorem: Euler's Formula

Let $z \in \C$ be a complex number.
Then:
:$e^{i z} = \cos z + i \sin z$

Proof:
This:
:$e^{i \theta} = \cos \theta + i \sin \theta$
is logically equivalent to this:
:$\dfrac {\cos \theta + i \sin \theta} {e^{i \theta} } = 1$
for every $\theta$.
Note that the left expression is nowhere undefined.
Taking the derivative of this:
{{begin-eqn}}
{{eqn | l = \dfrac \d {\d \theta} e^{-i \theta} \paren {\cos \theta + i \sin \theta}
      | r = e^{-i \theta} \paren {-\sin \theta + i \cos \theta} + \paren {-i e^{-i \theta} } \paren {\cos \theta + i \sin \theta}
      | c = Product Rule for Derivatives and Derivative of Exponential Function
}}
{{eqn | r = e^{-i \theta} \paren {-\sin \theta + i \cos \theta - i \cos \theta - i^2 \sin \theta}
      | c =
}}
{{eqn | r = e^{-i \theta} \paren {-\sin \theta + i \cos \theta - i \cos \theta + \sin \theta}
      | c =
}}
{{eqn | r = e^{-i \theta} \paren 0
      | c =
}}
{{eqn | r = 0
      | c =
}}
{{end-eqn}}
Thus the expression, as a function of $\theta$, is constant and so yields the same value for every $\theta$.
We know the value at at least one point, that is, when $\theta = 0$:
:$\dfrac {\cos 0 + i \sin 0} {e^{0 i}} = \dfrac {1 + 0} 1 = 1$
Thus it is $1$ for ''every'' $\theta$, which verifies the above.
Hence the result.
{{qed}}
Theorem: Euler's Formula

Let $z \in \C$ be a complex number.
Then:
:$e^{i z} = \cos z + i \sin z$

Proof:
Note that the following proof, as written, only holds for real $\theta$.
Define:
:$\map x \theta = e^{i \theta}$
:$\map y \theta = \cos \theta + i \sin \theta$
Consider first $\theta \ge 0$.
Taking Laplace transforms:
{{begin-eqn}}
{{eqn | l = \map {\laptrans {\map x \theta} } s
      | r = \map {\laptrans {e^{i \theta} } } s
}}
{{eqn| r = \frac 1 {s - i}
     | c = Laplace Transform of Exponential
}}
{{eqn | l = \map {\laptrans {\map y \theta} } s
      | r = \map {\laptrans {\cos \theta + i \sin \theta} } s
}}
{{eqn | r = \map {\laptrans {\cos \theta} } s + i \, \map {\laptrans {\sin \theta} } s
      | c = Linear Combination of Laplace Transforms
}}
{{eqn | r = \frac s {s^2 + 1} + \frac i {s^2 + 1}
      | c = Laplace Transform of Cosine, Laplace Transform of Sine
}}
{{eqn | r = \frac {s + i} {\paren {s + i} \paren {s - i} }
}}
{{eqn | r = \frac 1 {s - i}
}}
{{end-eqn}}
So $x$ and $y$ have the same Laplace transform for $\theta \ge 0$.
Now define $\tau = -\theta, \sigma = -s$, and consider $\theta < 0$ so that $\tau > 0$.
Taking Laplace transforms of $\map x \tau$ and $\map y \tau$: 
{{begin-eqn}}
{{eqn | l = \map {\laptrans {\map x \tau} } \sigma
      | r = \frac 1 {\sigma - i}
      | c = from above
}}
{{eqn | l = \map {\laptrans {\map y \tau} } \sigma
      | r = \frac 1 {\sigma - i}
      | c = from above
}}
{{end-eqn}}
So $\map x \theta$ and $\map y \theta$ have the same Laplace transforms for $\theta < 0$.
The result follows from Injectivity of Laplace Transform.
{{qed}}
Theorem: Euler's Formula

Let $z \in \C$ be a complex number.
Then:
:$e^{i z} = \cos z + i \sin z$

Proof:
As Sine Function is Absolutely Convergent and Cosine Function is Absolutely Convergent, we have:
{{begin-eqn}}
{{eqn | l = \cos \theta + i \sin \theta
      | r = \sum_{n \mathop = 0}^\infty \paren {-1}^n \dfrac {\theta^{2 n} } {\paren {2 n}!} + i \sum_{n \mathop = 0}^\infty \paren {-1}^n \dfrac {\theta^{2 n + 1} } {\paren {2 n + 1}!}
      | c = {{Defof|Complex Cosine Function}} and {{Defof|Complex Sine Function}}
}}
{{eqn | r = \sum_{n \mathop = 0}^\infty \paren {\paren {-1}^n \dfrac {\theta^{2 n} } {\paren {2 n}!} + i \paren {-1}^n \dfrac {\theta^{2 n + 1} } {\paren {2 n + 1}!} }
      | c = Sum of Absolutely Convergent Series
}}
{{eqn | r = \sum_{n \mathop = 0}^\infty \paren {\dfrac {\paren {i \theta}^{2 n} } {\paren {2 n}!} + \dfrac {\paren {i \theta}^{2 n + 1} } {\paren {2 n + 1}!} }
      | c = {{Defof|Imaginary Unit}}
}}
{{eqn | r = \sum_{n \mathop = 0}^\infty \dfrac {\paren {i \theta}^n} {n!}
}}
{{eqn | r = e^{i \theta}
      | c = {{Defof|Exponential Function/Complex|subdef = Power Series Expansion|Complex Exponential Function}}
}}
{{end-eqn}}
{{qed}}
Theorem: Lagrange's Theorem (Group Theory)

Let $G$ be a finite group.
Let $H$ be a subgroup of $G$.
Then:
:$\order H$ divides $\order G$
where $\order G$ and $\order H$ are the order of $G$ and $H$ respectively.
In fact:
:$\index G H = \dfrac {\order G} {\order H}$
where $\index G H$ is the index of $H$ in $G$.
When $G$ is an infinite group, we can still interpret this theorem sensibly:
:A subgroup of finite index in an infinite group is itself an infinite group.
:A finite subgroup of an infinite group has infinite index.

Proof:
Let $G$ be finite.
Consider the mapping $\phi: G \to G / H^l$, defined as:
:$\phi: G \to G / H^l: \map \phi x = x H$
where $G / H^l$ is the left coset space of $G$ modulo $H$.
For every $x H \in G / H^l$, there exists a corresponding $x \in G$, so $\phi$ is a surjection.
From Cardinality of Codomain of Surjection it follows that $G / H^l$ is finite.
From Cosets are Equivalent, for every $x \in G$, $xH$ has the same number of elements as $H$.
We have that the $G / H^l$ is a partition of $G$.
It follows from Number of Elements in Partition that $\index G H = \dfrac {\order G} {\order H}$
{{Qed}}
Theorem: Lagrange's Theorem (Group Theory)

Let $G$ be a finite group.
Let $H$ be a subgroup of $G$.
Then:
:$\order H$ divides $\order G$
where $\order G$ and $\order H$ are the order of $G$ and $H$ respectively.
In fact:
:$\index G H = \dfrac {\order G} {\order H}$
where $\index G H$ is the index of $H$ in $G$.
When $G$ is an infinite group, we can still interpret this theorem sensibly:
:A subgroup of finite index in an infinite group is itself an infinite group.
:A finite subgroup of an infinite group has infinite index.

Proof:
Let $G$ be a group.
Let $H$ be a subgroup of $G$.
From Cosets are Equivalent, a left coset $y H$ has the same number of elements as $H$, namely $\order H$.
Since left cosets are identical or disjoint, each element of $G$ belongs to exactly one left coset.
From the definition of index of subgroup, there are $\index G H$ left cosets, and therefore:
:$\order G = \index G H \order H$
Let $G$ be of finite order.
All three numbers are finite, and the result follows.
Now let $G$ be of infinite order.
If $\index G H = n$ is finite, then $\order G = n \order H$ and so $H$ is of infinite order.
If $H$ is of finite order such that $\order H = n$, then $\order G = \index G H \times n$ and so $\index G H$ is infinite.
{{qed}}
Theorem: Lagrange's Theorem (Group Theory)

Let $G$ be a finite group.
Let $H$ be a subgroup of $G$.
Then:
:$\order H$ divides $\order G$
where $\order G$ and $\order H$ are the order of $G$ and $H$ respectively.
In fact:
:$\index G H = \dfrac {\order G} {\order H}$
where $\index G H$ is the index of $H$ in $G$.
When $G$ is an infinite group, we can still interpret this theorem sensibly:
:A subgroup of finite index in an infinite group is itself an infinite group.
:A finite subgroup of an infinite group has infinite index.

Proof:
Follows directly from the Orbit-Stabilizer Theorem applied to Group Action on Coset Space.
{{Qed}}
Theorem: Carathéodory's Theorem (Analysis)

Let $I \subseteq \R$.
Let $c \in I$ be an interior point of $I$.
{{Disambiguate|Definition:Interior Point}}
{{explain|In this case, there appears not to be a definition for "interior point" which appropriately captures the gist of this. It is clearly a point inside a real interval, but the concept has not yet been defined.}}
Let $f : I \to \R$ be a real function.
Then $f$ is differentiable at $c$ {{iff}}:
:There exists a real function $\varphi : I \to \R$ that is continuous at $c$ and satisfies:
:$(1): \quad \forall x \in I: \map f x - \map f c = \map \varphi x \paren {x - c}$
:$(2): \quad \map \varphi c = \map {f'} c$

Proof:
=== Necessary Condition ===
Suppose $f$ is differentiable at $c$.
Then by definition $\map {f'} c$ exists.
So we can define $\varphi$ by:
:$\map \varphi x = \begin{cases}
\dfrac {\map f x - \map f c} {x - c} & : x \ne c, x \in I \\
\map {f'} c & : x = c
\end{cases}$
Condition $(2)$, that $\varphi$ is continuous at $c$, is satisfied, since:
{{begin-eqn}}
{{eqn | l = \map \varphi c
      | r = \map {f'} c
      | c = Definition of $\varphi$
}}
{{eqn | r = \lim_{x \mathop \to c} \frac {\map f x - \map f c} {x - c}
      | c = {{Defof|Derivative}}
}}
{{eqn | r = \lim_{x \mathop \to c} \map \varphi x
      | c = Definition of $\varphi$
}}
{{end-eqn}}
Finally, condition $(1)$ is vacuous for $x = c$.
For $x \ne c$, it follows from the definition of $\varphi$ by dividing both sides of $(1)$ by $x - c$.
{{qed|lemma}}
Theorem: One-Step Subgroup Test

Let $\struct {G, \circ}$ be a group.
Let $H$ be a subset of $G$.
Then $\struct {H, \circ}$ is a subgroup of $\struct {G, \circ}$ {{iff}}:
:$(1): \quad H \ne \O$, that is, $H$ is non-empty
:$(2): \quad \forall a, b \in H: a \circ b^{-1} \in H$.

Proof:
=== Sufficient Condition ===
Let $H$ be a subset of $G$ that fulfils the conditions given.
It is noted that the fact that $H$ is non-empty is one of the conditions.
It is also noted that the group operation of $\struct {H, \circ}$ is the same as that for $\struct {G, \circ}$, that is, $\circ$.
So it remains to show that $\struct {H, \circ}$ is a group.
We check the four group axioms:
Theorem: Two-Step Subgroup Test

Let $\struct {G, \circ}$ be a group.
Let $H$ be a subset of $G$.
Then $\struct {H, \circ}$ is a subgroup of $\struct {G, \circ}$ {{iff}}:
:$(1): \quad H \ne \O$, that is, $H$ is non-empty
:$(2): \quad a, b \in H \implies a \circ b \in H$
:$(3): \quad a \in H \implies a^{-1} \in H$.
That is, $\struct {H, \circ}$ is a subgroup of $\struct {G, \circ}$ {{iff}} $\struct {H, \circ}$ is a $H$ be a nonempty subset of $G$ which is:
:closed under its operation
and:
:closed under inversion.

Proof:
=== Necessary Condition ===
Let $H$ be a subset of $G$ that fulfils the conditions given.
It is noted that the fact that $H$ is nonempty is one of the conditions.
It is also noted that the group operation of $\struct {H, \circ}$ is the same as that for $\struct {G, \circ}$, that is, $\circ$.
So it remains to show that $\struct {H, \circ}$ is a group.
We check the four group axioms:
Theorem: Fundamental Theorem of Arithmetic

For every integer $n$ such that $n > 1$, $n$ can be expressed as the product of one or more primes, uniquely up to the order in which they appear.

Proof:
In Integer is Expressible as Product of Primes it is proved that every integer $n$ such that $n > 1$, $n$ can be expressed as the product of one or more primes.
In Prime Decomposition of Integer is Unique, it is proved that this prime decomposition is unique up to the order of the factors.
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
As for Euclid's Lemma for Prime Divisors, this can be verified by direct application of general version of Euclid's Lemma for irreducible elements.
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
Proof by induction:
For all $r \in \N_{>0}$, let $\map P r$ be the proposition:
:$\ds p \divides \prod_{i \mathop = 1}^r a_i \implies \exists i \in \closedint 1 r: p \divides a_i$
$\map P 1$ is true, as this just says $p \divides a_1 \implies p \divides a_1$.
=== Basis for the Induction ===
$\map P 2$ is the case:
:$p \divides a_1 a_2 \implies p \divides a_2$ or $p \divides a_2$
which is proved in Euclid's Lemma for Prime Divisors.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds p \divides \prod_{i \mathop = 1}^k a_i \implies \exists i \in \closedint 1 k: p \divides a_i$
Then we need to show:
:$\ds p \divides \prod_{i \mathop = 1}^{k + 1} a_i \implies \exists i \in \closedint 1 {k + 1}: p \divides a_i$
=== Induction Step ===
This is our induction step:
{{begin-eqn}}
{{eqn | l = p
      | o = \divides
      | r = a_1 a_2 \ldots a_{k + 1}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = p
      | o = \divides
      | r = \paren {a_1 a_2 \ldots a_k} \paren {a_{k + 1} }
      | c =
}}
{{eqn | ll= \leadsto
      | l = p
      | o = \divides
      | r = a_1 a_2 \ldots a_k \lor p \divides a_{k + 1}
      | c = Basis for the Induction
}}
{{eqn | ll= \leadsto
      | l = p
      | o = \divides
      | r = a_1 \lor p \divides a_2 \lor \ldots \lor p \divides a_k \lor p \divides a_{k + 1}
      | c = Induction Hypothesis
}}
{{end-eqn}}
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall r \in \N: p \divides \prod_{i \mathop = 1}^r a_i \implies \exists i \in \closedint 1 r: p \divides a_i$
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
Let $p \divides n$.
{{AimForCont}}:
:$\forall i \in \set {1, 2, \ldots, r}: p \nmid a_i$
By Prime not Divisor implies Coprime:
:$\forall i \in \set {1, 2, \ldots, r}: p \perp a_i$
By Integer Coprime to all Factors is Coprime to Whole:
:$p \perp n$
By definition of coprime:
:$p \nmid n$
The result follows by Proof by Contradiction.
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
We have that the integers form a Euclidean domain.
Then from Irreducible Elements of Ring of Integers we have that the irreducible elements of $\Z$ are the primes and their negatives.
The result then follows directly from Euclid's Lemma for Irreducible Elements.
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
Let $p \divides a b$.
Suppose $p \nmid a$.
Then from the definition of prime:
:$p \perp a$
where $\perp$ indicates that $p$ and $a$ are coprime.
Thus from Euclid's Lemma it follows that:
:$p \divides b$
Similarly, if $p \nmid b$ it follows that $p \divides a$.
So:
:$p \divides a b \implies p \divides a$ or $p \divides b$
as we needed to show.
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
Let $p \divides a b$.
Suppose $p \nmid a$.
Then by {{EuclidPropLink|book = VII|prop = 29|title = Prime not Divisor implies Coprime}}:
:$p \perp a$
As $p \divides a b$, it follows by definition of divisor:
:$\exists e \in \Z: e p = a b$
So by {{EuclidPropLink|book = VII|prop = 19|title = Relation of Ratios to Products}}:
:$p : a = b : e$
But as $p \perp a$, by:
:{{EuclidPropLink|book = VII|prop = 21|title = Coprime Numbers form Fraction in Lowest Terms}}
and: 
:{{EuclidPropLink|book = VII|prop = 20|title = Ratios of Fractions in Lowest Terms}}
it follows that:
:$p \divides b$
Similarly, if $p \perp b$ then $p \divides a$.
Hence the result.
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
Follows directly from Integers are Euclidean Domain.
{{qed}}
Theorem: Euclid's Lemma

Let $a, b, c \in \Z$.
Let $a \divides b c$, where $\divides$ denotes divisibility.
Let $a \perp b$, where $\perp$ denotes relative primeness.
Then $a \divides c$.

Proof:
Let $a, b, c \in \Z$.
We have that $a \perp b$.
That is:
:$\gcd \set {a, b} = 1$
where $\gcd$ denotes greatest common divisor.
From Bézout's Identity, we may write:
:$a x + b y = 1$
for some $x, y \in \Z$.
Upon multiplication by $c$, we see that:
:$c = c \paren {a x + b y} = c a x + c b y$
Now note that $c a x + c b y$ is an integer combination of $a c$ and $b c$.
So, since:
:$a \divides a c$
and:
:$a \divides b c$
it follows from Common Divisor Divides Integer Combination that:
:$a \divides \paren {c a x + c b y}$
However:
: $c a x + c b y = c \paren {a x + b y} = c \cdot 1 = c$
Therefore:
: $a \divides c$
{{qed}}
Theorem: Fermat's Little Theorem

Let $p$ be a prime number.
Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.
Then:
:$n^{p - 1} \equiv 1 \pmod p$

Proof:
There are two cases:
:$(1): \quad$ If $p \divides n$, then $n^p \equiv 0 \equiv n \pmod p$.
:$(2): \quad$ Otherwise, $p \nmid n$.
Then, by Fermat's Little Theorem, $n^{p-1} \equiv 1 \pmod p$.
Multiplying both sides by $n$, then by Congruence of Product we have:
: $n^p \equiv n \pmod p$
{{qed}}
Theorem: Fermat's Little Theorem

Let $p$ be a prime number.
Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.
Then:
:$n^{p - 1} \equiv 1 \pmod p$

Proof:
Suppose we want to form strings of colored beads, each with exactly $p$ beads in.
Suppose we have an unlimited number of beads to allow unlimited use of each of $n$ colors.
How many different strings can we form?
The answer is $n^p$ as each bead can be chosen in $n$ ways and there are $p$ choices for each string.
Out of these $n^p$ possibilities, exactly $n$ strings have beads of only one color.
Put these aside, and thus there are $n^p - n$ beads remaining.
Suppose we then form bracelets from these strings by joining one end to the other and making them closed loops.
Now we can change any string of beads by removing one bead from one end and putting it on the other.
This produces a different string of beads without changing the resulting bracelet.
Let $k$ be the least number of times this operation can be done before the original color scheme is reproduced.
Clearly $k > 1$ as the monocolor strings have all been eliminated.
After $2 k$ steps the bracelet will once again be reproduced, and again at $3 k$ and so on.
By the Division Theorem there exists $h$ and $r$ such that $p = h k + r$ where $0 \le r < k$.
Since the color scheme is reproduced after $h k$ steps and also after $p$ steps, it takes exactly $r$ steps after the $h k$th step to get back to the original color scheme.
Since $r < k$ and $k$ is the least positive number of such steps, $r = 0$.
So $p = h k$ and so $k = p$ as $p$ is prime.
So the $n^p - n$ strings fall into groups of $p$ strings each, and each one forms a separate bracelet.
So the number of bracelets $N$ multiplied by $p$ gives the number of strings which are not monocolor, that is, $n^p - n$.
So $p N = n^p - n$, that is, $p \divides n^p - n$, and the result follows.
{{qed}}
Theorem: Fermat's Little Theorem

Let $p$ be a prime number.
Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.
Then:
:$n^{p - 1} \equiv 1 \pmod p$

Proof:
Consider the integer sequence $n, 2 n, 3 n, \dotsc, \paren {p - 1} n$.
Note that none of these integers is congruent modulo $p$ to any of the others.
If this were the case, we would have $a n \equiv b n \pmod p$ for some $1 \le a < b \le p - 1$.
Then as $\map \gcd {n, p} = 1$, and we can cancel the $n$, we get $a \equiv b \pmod p$ and so $a = b$.
We have that:
:$\forall c \in \set {1, 2, \dotsc, p - 1}: p \nmid n \land p \nmid c$
So by Euclid's Lemma:
:$p \nmid c n$
for any such $c n$, which means:
:$c n \not \equiv 0 \pmod p$
Thus, each integer in the sequence can be reduced modulo $p$ to exactly one of $1, 2, 3, \ldots, p - 1$.
So $\set {1, 2, 3, \ldots, p - 1}$ is the set of Reduced Residue System modulo $p$.
So, upon taking the product of these congruences, we see that:
:$n \times 2 n \times 3 n \times \dots \times \paren {p - 1} n \equiv 1 \times 2 \times 3 \times \cdots \times \paren {p - 1} \pmod p$
This simplifies to:
:$n^{p - 1} \times \paren {p - 1}! \equiv \paren {p - 1}! \pmod p$
Since $p \nmid \paren {p - 1}!$, we can cancel $\paren {p - 1}!$ from both sides, leaving us with:
:$n^{p - 1} \equiv 1 \pmod p$
{{qed}}
Theorem: Fermat's Little Theorem

Let $p$ be a prime number.
Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.
Then:
:$n^{p - 1} \equiv 1 \pmod p$

Proof:
By Prime not Divisor implies Coprime:
:$p \nmid n \implies p \perp n$
and Euler's Theorem (Number Theory) can be applied.
Thus:
:$n^{\map \phi p} \equiv 1 \pmod p$
But from Euler Phi Function of Prime Power:
:$\map \phi p = p \paren {1 - \dfrac 1 p} = p - 1$
and the result follows.
{{qed}}
Theorem: Fermat's Little Theorem

Let $p$ be a prime number.
Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.
Then:
:$n^{p - 1} \equiv 1 \pmod p$

Proof:
Let $\struct {\Z'_p, \times}$ denote the multiplicative group of reduced residues modulo $p$.
From {{Corollary|Reduced Residue System under Multiplication forms Abelian Group}}, $\struct {\Z'_p, \times}$ forms a group of order $p - 1$ under modulo multiplication.
By Element to Power of Group Order is Identity, we have:
:$n^{p - 1} \equiv 1 \pmod p$
{{qed}}