nyuuzyou/wikis huggingface dataset:
Faà di Bruno's Formula/Historical Note

== Historical Note on Faà di Bruno's Formula ==
While Faà di Bruno's Formula was named after , he was not the first to state it.
That honour belongs to who published it in his textbook of $1800$ .
 himself published this result in 's magazine in $1855$, and again in in $1857$.
== Sources ==
* 
* : $\S 1.2.5$: Permutations and Factorials: Exercise $21$
Category:Historical Notes
Faà di Bruno's Formula/Lemma 1

== Theorem ==
Let $m \in \Z_{\ge 1}$ be a (strictly) positive integer.
Let $k_m \in \Z_{\ge 1}$ also be a (strictly) positive integer.
Let $u: \R \to \R$ be a function of $x$ which is appropriately differentiable.
Then:
:$\map {D_x} {\paren {D_x^m u}^{k_m} } = k_m \paren {D_x^m u}^{k_m - 1} D_x^{m + 1} u$
== Proof ==
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Lemma 2

== Theorem ==
Let $m \in \Z_{\ge 1}$ be a (strictly) positive integer.
Let $k_m \in \Z_{\ge 1}$ also be a (strictly) positive integer.
Let $u: \R \to \R$ be a function of $x$ which is appropriately differentiable.
Then:
:$\ds \map {D_x} {\prod_{m \mathop = 1}^r \paren {\dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} } } } = \prod_{m \mathop = 1}^r \paren {\dfrac {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} } } \sum_{m \mathop = 1}^r k_m \dfrac {D_x^{m + 1} u} {D_x^m u}$
== Proof ==
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Proof 2

== Theorem ==
== Proof ==
For convenience, let:
:$w_j := D_u^j w$
:$u_k := D_x^k u$
Then:
Thus:
Analogously, let a corresponding tableau be set up of set partitions as follows:
Thus inspired, let $a_1 a_2 \cdots a_j$ denote a partition of the set $\set {1, 2, \ldots, n-1}$.
Let:
This rule is isomorphic to:
where the term $w_j u_{r_1} u_{r_2} \ldots u_{r_j}$ corresponds to a partition $a_1 a_2 \cdots a_j$.
Thus there exists a bijection from $\DD^n$ to $D_x^n w$.
Thus, collecting like terms in $D_x^n w$, we obtain a sum of terms:
:$\map c {k_1, k_2, \ldots} w_j u_i^{k_1} u_2^{k_2} \ldots$
where:
:$j = k_1 + k_2 + \cdots$
and:
:$n = k_1 + 2 k_2 + \cdots$
and where:
:$\map c {k_1, k_2, \ldots}$ is the number of partitions of $\set {1, 2, \ldots, n}$ into $j$ subsets where there are $k_t$ subsets with $t$ elements.
Consider an array of $k_t$ boxes of capacity $t$.
The number of ways to put $n$ different elements into these boxes is the multinomial coefficient:
:$\dbinom n {1, 1, \ldots, 1, 2, 2, \ldots, 2, 3, 3, \ldots, 3, 4, \ldots} = \dfrac {n!} {\paren {1!}^{k_1} \paren {2!}^{k_2} \paren {3!}^{k_3} \cdots}$
It remains to divide by $k_1! \, k_2! \, k_3! \ldots$ corresponding to the number of ways each group of $k_t$ can be permuted
Hence:
:$\map c {k_1, k_2, \ldots} = \dfrac {n!} {k_1! \paren {1!}^{k_1} \, k_2! \paren {2!}^{k_2} k_3! \paren {3!}^{k_3} \cdots}$
and the result follows.
== Sources ==
* 
* : $\S 1.2.5$: Permutations and Factorials: Exercise $21$
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Proof 3

== Proof ==
We have that:
:$\dfrac {D_x^k u} {k!}$ is the coefficient of $z^k$ in $\map u {x + z}$
:$\dfrac {D_u^j w} {j!}$ is the coefficient of $y^j$ in $\map w {u + y}$.
Hence the coefficient of $z^n$ in $\map w {\map u {x + z} }$ is:
:$\dfrac {D_x^n w} {n!} = \ds \sum_{\substack {\sum_{p \mathop \ge 1} k_p \mathop = j \\ \sum_{p \mathop \ge 1} p k_p \mathop = n \\ \forall p \mathop \ge 1: k_p \mathop \ge 0} } \dfrac {j!} {k_1! \, k_2! \cdots k_n!} \paren {\dfrac {D_x^1 u} {1!} }^{k_1} \paren {\dfrac {D_x^2 u} {2!} }^{k_2} \cdots \paren {\dfrac {D_x^n u} {n!} }^{k_n}$
== Sources ==
* 
* : $\S 1.2.5$: Permutations and Factorials: Exercise $21$
Category:Faà di Bruno's Formula
Faà di Bruno's Formula/Proof 4

== Theorem ==
== Proof ==
$D_x^n$ can be expressed as a determinant:
:$D_x^n = \begin{vmatrix}
\dbinom {n - 1} 0 u_1 & \dbinom {n - 1} 1 u_2 & \dbinom {n - 1} 2 u_3 & \cdots & \dbinom {n - 1} {n - 2} u_{n - 1} & \dbinom {n - 1} {n - 1} u_n \\
 -1 & \dbinom {n - 2} 0 u_1 & \dbinom {n - 2} 1 u_2 & \cdots & \dbinom {n - 2} {n - 3} u_{n - 2} & \dbinom {n - 2} {n - 2} u_{n - 1} \\
 0 & -1 & \dbinom {n - 3} 0 u_1 & \cdots & \dbinom {n - 3} {n - 4} u_{n - 3} & \dbinom {n - 3} {n - 3} u_{n - 2} \\
 \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
 0 & 0 & 0 & \cdots & -1 & \dbinom 0 0 u_1
\end{vmatrix}$
where $u_j := \paren {D_x^j u} D_u$.
Both sides of this equation are differential operators which are to be applied to $w$.
== Sources ==
* 
* 
* : $\S 1.2.5$: Permutations and Factorials: Exercise $21$
Category:Faà di Bruno's Formula
Feit-Thompson Conjecture

== Conjecture ==
There exist no distinct prime numbers $p$ and $q$ such that:
:$\dfrac {p^q - 1} {p - 1}$ divides $\dfrac {q^p - 1} {q - 1}$
=== Stronger Feit-Thompson Conjecture ===
Category:Prime Numbers
Category:Divisors
Category:Unproven Hypotheses
Category:Feit-Thompson Conjecture
Feit-Thompson Conjecture/Stronger

== Conjecture ==
There exist no distinct prime numbers $p$ and $q$ such that:
:$\dfrac {p^q - 1} {p - 1}$ and $\dfrac {q^p - 1} {q - 1}$ are not coprime.
== Refutation ==
Let:
:$A = \dfrac {p^q - 1} {p - 1}$
:$B = \dfrac {q^p - 1} {q - 1}$
Suppose there exists a prime number $r$ such that:
:$r \divides A$ and $r \divides B$
where $\divides$ denotes divisibility.
 $p = 2$.
Then:
:$r \divides 2^q - 1$
and:
:$r \divides q + 1$
From Factor of Mersenne Number $M_p$ is of form $2 k p + 1$:
:$2 q \divides r - 1$
From Absolute Value of Integer is not less than Divisors:
which is impossible.
Hence both $p$ and $q$ are odd primes.
:
:$r \divides \paren {p - 1}$
By Sum of Geometric Sequence:
:$A = 1 + p + p^2 + \cdots + p^{q - 1} \equiv q \pmod r$
and so $r = q$.
But $q \nmid B$.
Hence:
:$r \nmid \paren {p - 1}$
Similarly:
:$r \nmid \paren {q - 1}$
It follows that:
:$p^q \equiv 1 \pmod r$
from which:
:$q \divides \paren {r - 1}$
It follows then that:
:$(1): \quad r = 2 \lambda p q + 1$
for some $\lambda \in \Z_{>0}$.
It then remains to test the residues of $p^q$ and $q^p$ modulo $r$ for all odd primes $p$ and $q$ for all $r$ of the form given in $1$ in a suitable range.
The counterexample $p = 17$, $q = 3313$ was discovered using the above technique in $1971$, using the ranges $p < 443$, $pq < 200 \, 000$ and $r < 400 \, 000$.
The common divisor was found to be $2 p q + 1 = 112 \, 643$.
It is believed that the exercise has not been reported on since, and that no other counterexamples to the conjecture are known.
== Historical Note ==
== Sources ==
* 
Category:Famous False Conjectures
Category:Feit-Thompson Conjecture
Feit-Thompson Conjecture/Stronger/Historical Note

== Historical Note on Stronger Feit-Thompson Conjecture ==
The stronger form of the Feit-Thompson Conjecture was refuted by in $1971$, by means of a computer search.
Note that , in his of $1986$, misreports this result, stating it about the common divisor of $p^q - 1$ and $q^p - 1$.
 
Then in his of $1997$, he misreports this result again, in a different way, stating it about the common divisor of $p^p - 1$ and $q^q - 1$.
The latter is obviously spurious, as, given odd primes $p$ and $q$, $p^p - 1$ and $q^q - 1$ are both even, and hence have a common divisor of $2$.
Category:Historical Notes
Feit-Thompson Conjecture/Stronger/Mistake/First Edition

== Source Work ==
:
:The Dictionary
::$17$
== Mistake ==
:The only known prime values for which $p^q - 1$ and $q^p - 1$ have a common factor less than $400,000$ are $17$ and $3313$. The common factor is $112,643$.
== Correction ==
The correct expressions are $\dfrac {p^q - 1} {p - 1}$ and $\dfrac {q^p - 1} {q - 1}$.
It appears that the author misrepresented the refutation of the Stronger Feit-Thompson Conjecture:
== Sources ==
* : $17$
Category:Mistakes/Curious and Interesting Numbers
Feit-Thompson Conjecture/Stronger/Mistake/Second Edition

== Source Work ==
:
:The Dictionary
::$17$
== Mistake ==
:The only known prime values for which $p^p - 1$ and $q^q - 1$ have a common factor less than $400,000$ are $17$ and $3313$. The common factor is $112,643$.
== Correction ==
This is of course false, because $p^p - 1$ and $q^q - 1$ have the obvious common factor $2$.
It appears that the second edition compounded the mistake reported in the first edition
by confusing the $p$s and $q$s.
The Stronger Feit-Thompson Conjecture actually states:
== Sources ==
* : $17$
Category:Mistakes/Curious and Interesting Numbers
Feit-Thompson Theorem/Historical Note

== Historical Note on Feit-Thompson Theorem ==
The Feit-Thompson Theorem originated as a conjecture of in the $1911$ edition of his .
He had previously raised the question in the first ($1897$) edition of that work about the existence or not of a non-abelian simple group of odd order without actually predicting the outcome.
The question was settled by and in their $1963$ paper in .
== Sources ==
* 
* : $1$: Introduction to Finite Group Theory: $1.12$
* 
Category:Historical Notes
Fekete's Subadditive Lemma

== Theorem == 
Let $\sequence {a_n}_{n \mathop \ge 1}$ be a subadditive sequence.
Then:
:$\ds \lim_{n \mathop \to \infty} \frac {a_n} n = \inf_{n \mathop \ge 1} \frac {a_n} n$
== Proof ==
Let $k \ge 1$.
Let $n \ge 1$.
By Division Theorem, there exist $q \in \N$ and $r \in \set {0, 1, \ldots , k - 1}$ such that:
:$n = k q + r$
Thus:
By $n \to \infty$, we obtain:
:$\ds \forall k \ge 1 : \limsup_{n \mathop \to \infty} \frac {a_n} n \le \frac {a_k} k$
In particular:
:$\ds (1): \quad \limsup_{n \mathop \to \infty} \frac {a_n} n \le \inf_{k \mathop \ge 1} \frac {a_k} k$
On the other hand, by definition of infimum:
:$\ds \forall n \ge 1 : \inf_{k \mathop \ge 1} \frac {a_k} k \le \frac{a_n} n$
In particular:
:$\ds (2): \quad \inf_{k \mathop \ge 1} \frac {a_k} k \le \liminf_{n \mathop \to \infty} \frac {a_n} n$
By Convergence of Limsup and Liminf, $(1)$ and $(2)$ together mean:
:$\ds \lim_{n \mathop \to \infty} \frac {a_n} n = \inf_{k \mathop \ge 1} \frac {a_k} k$
== Also known as ==
== Sources ==
* : $6.2.$ Subadditive Sequences
Category:Fekete's Subadditive Lemma
Category:Real Sequences
Fencepost Mistake

== Common Mistake ==
Let $F$ be a fence of length $n$ units, with fenceposts at either end and spaced $1$ unit apart.
How many fenceposts are there?
To answer $n$ is to make the fencepost mistake.
There are $n + 1$ fenceposts.
== Also known as ==
This is usually seen as fencepost error, but prefers to reserve the word error for its context in unavoidable inaccuracies in measurement.
== Also see ==
Category:Mistakes
Category:Fencepost Mistakes
Fermat's Last Theorem

== Theorem ==
:$\forall a, b, c, n \in \Z_{>0}: n > 2$, the equation $a^n + b^n = c^n$ has no solutions.
== Proof ==
The proof of this theorem is beyond the current scope of , and indeed, is beyond the understanding of many high level mathematicians.
For the curious reader, the proof can be found here, in a paper published by , entitled Modular elliptic curves and Fermat's Last Theorem, in volume 141, issue 3, pages 443 through 551 of the Annals of Mathematics.
It is worth noting that Wiles' proof was indirect in that he proved a special case of the Taniyama-Shimura Conjecture, which then along with the already proved Epsilon Conjecture implied that integral solutions of the theorem were impossible.
=== Cubic ===
=== Fourth Powers ===
== Historical Note ==
== Sources ==
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* : $2$
* 
* : Chapter $\text {A}.13$: Fermat ()
* : Bachet
* 
* 
* : Notes on the Exercises: Exercise $4$
* : $2$
* : Notes on the Exercises: Exercise $3$
* 
* 
* : Chapter $7$: Patterns in Numbers: Fermat
* 
Category:Number Theory
Category:Classic Problems
Category:Fermat's Last Theorem
Fermat's Last Theorem/Cubic/Historical Note

== Historical Note on Fermat's Last Theorem: Cubic Case ==
The special case of Fermat's Last Theorem:
:$\forall a, b, c \in \Z_{>0}$, the equation $a^3 + b^3 = c^3$ has no solutions
was proven by .
== Sources ==
* : $3$
* : $3$
Category:Historical Notes
Fermat's Last Theorem/Historical Note

== Historical Note on Fermat's Last Theorem ==
=== Fermat's Note ===
As himself put it, sometime around $1637$:
Nobody managed to find such a proof, until it was finally proved by in $1994$.
It is seriously doubted that actually had found a general proof of it.
It is almost impossible that he found ' proof, since it uses areas of mathematics that were not yet invented in 's time.
 himself left an outline of the proof for $n = 4$.
 provided the full proof for $n = 4$ and also a proof for the more difficult case $n = 3$.
The cases for $n = 5$ and $n = 7$ were proved by , and and others.
The case for $n = 7$ was proved by in $1840$.
At the time ' proof was published, the theorem had been established as true for all numbers up to $125 \, 000$.
Furthermore, where $n$ does not divide any of $x$, $y$ or $z$, it had been proved for all $n$ up to $253 \, 747 \, 889$.
In the words of :
:Before beginning I would have to put in three years of intensive study, and I haven't that much time to waste on a probable failure.
, in the introductions to early editions of his , introduced Fermat's Last Theorem as an example of a $50$ point exercise, that is, a research problem.
In later editions, that is, those published after $1994$, it was downgraded to a $45$ point question.
== Sources ==
* : Chapter $\text{IV}$: The Prince of Amateurs
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* : $7$
* : $125,000$
* : $253,747,889$
* 
* : Chapter $\text {A}.13$: Fermat ()
* : Bachet
* : Chapter $\text{I}$: An Overview of the Proof of Fermat's Last Theorem
* : $7$
* 
* 
* 
Category:Historical Notes
Fermat's Last Theorem/Historical Note/Fermat's Note

== Historical Note on Fermat's Last Theorem: 's Note in 's ==
:Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos et generaliter nullam in infinitum ultra quadratum potestatem in duos ejusdem nominis fas est dividere: cujus rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.
Loosely translated from the Latin, that means:
:The equation $x^n + y^n = z^n$ has no integral solutions when $n > 2$. I have discovered a perfectly marvellous proof, but this margin is not big enough to hold it.
This was written against problem $8$ of Book $\text {II}$ of 's .
== Sources ==
* : Chapter $\text{IV}$: The Prince of Amateurs
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* 
* : Chapter $\text {A}.13$: Fermat ()
* : Bachet
* : Chapter $7$: Patterns in Numbers: Fermat
Category:Historical Notes
Fermat's Little Theorem

== 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$
=== Corollary 1 ===
=== Corollary 2 ===
=== Corollary 3 ===
=== Corollary 4 ===
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Proof 4 ==
== Proof 5 ==
== Examples ==
== Also known as ==
== Also defined as ==
== Also presented as ==
== Also see ==
* Euler's Theorem (Number Theory)
== Historical Note ==
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $25$. Cyclic Groups and Lagrange's Theorem: Exercise $25.6$
* : $\text {3-2}$ Fermat's Little Theorem: Exercise $1$
* : $0$: Some Conventions and some Basic Facts: Exercise $8$
* : $\S 19$: Properties of $\Z_m$ as an algebraic system (mention)
* : $\S 2.3$: Congruences: Theorem $3$
* : $64$
* 
* : Chapter $\text {A}.13$: Fermat ()
* : $64$
* 
* 
* 
* 
* 
* 
* 
* 
Category:Fermat's Little Theorem
Category:Number Theory
Fermat's Little Theorem/Also defined as

== Fermat's Little Theorem: Also defined as == 
Some sources refer to the :
:$n^p \equiv n \pmod p$
or:
:$p \divides n^p - n$ 
as Fermat's Little Theorem and from it derive this result.
== Sources ==
* : Chapter $\text{IV}$: The Prince of Amateurs
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-2}$
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Theorem $\text{F}$
* 
Category:Fermat's Little Theorem
Fermat's Little Theorem/Also known as

== Fermat's Little Theorem: Also known as == 
Some sources refer to Fermat's Little Theorem as Fermat's Theorem, but it needs to be appreciated that this may cause confusion with Fermat's Last Theorem.
== Sources ==
* : Chapter $\text{IV}$: The Prince of Amateurs
* : Chapter $\text {IV}$: Rings and Fields: $25$. Cyclic Groups and Lagrange's Theorem: Exercise $25.6$
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* : $0$: Some Conventions and some Basic Facts: Exercise $8$
* : $\S 19$: Properties of $\Z_m$ as an algebraic system (mention)
* : $\S 2.3$: Congruences: Theorem $3$
* : Chapter $\text {A}.13$: Fermat ()
* 
* 
* 
* 
Category:Fermat's Little Theorem
Fermat's Little Theorem/Also presented as

== Fermat's Little Theorem: Also presented as == 
Some sources present Fermat's Little Theorem in the form:
:$p \divides n^{p - 1} - 1$
where $\divides$ denotes divisibility.
== Sources ==
* : $\text {3-2}$ Fermat's Little Theorem: Exercise $1$
* : $64$
* : Chapter $\text {A}.13$: Fermat ()
* : $64$
* 
* 
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 1

== Corollary to Fermat's Little Theorem ==
If $p$ is a prime number, then $n^p \equiv n \pmod p$.
== Proof 1 ==
== Proof 2 ==
== Also reported as ==
== Also known as ==
== Historical Note ==
== Sources ==
* : Chapter $\text{IV}$: The Prince of Amateurs
* : Chapter $\text {IV}$: Rings and Fields: $25$. Cyclic Groups and Lagrange's Theorem: Exercise $25.6$
* : $\text {3-1}$ Permutations and Combinations: Exercise $11$
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-2}$
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Theorem $\text{F}$
* 
* 
* : Chapter $7$: Patterns in Numbers: Fermat
* 
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 1/Also known as

== : Also known as == 
Some sources refer to as Fermat's Little Theorem, and from it derive Fermat's Little Theorem as a corollary.
== Sources ==
* : Chapter $\text{IV}$: The Prince of Amateurs
* : $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-2}$
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Theorem $\text{F}$
* : Chapter $7$: Patterns in Numbers: Fermat
* 
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 1/Also reported as

== : Also reported as == 
 can also be reported as:
:If $p$ is a prime number, then $n^p - n$ is divisible by $p$.
== Sources ==
* : Chapter $\text{IV}$: The Prince of Amateurs
* : $\text {3-1}$ Permutations and Combinations: Exercise $11$
* : $1$: The Nature of Differential Equations: $\S 6$: The Brachistochrone. Fermat and the Bernoullis
* 
* 
* : Chapter $7$: Patterns in Numbers: Fermat
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 1/Proof 1

== Corollary to Fermat's Little Theorem ==
== 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$
== Sources ==
* : $\S 2.3$: Congruences: Theorem $3$: Corollary
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 1/Proof 2

== Corollary to Fermat's Little Theorem ==
== 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.
== Sources ==
* : $\text {3-2}$ Fermat's Little Theorem: Theorem $\text {3-4}$
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 2

== Corollary to Fermat's Little Theorem ==
Let $p$ be a prime number.
Then:
:$n^{p - 1} \equiv \sqbrk {p \nmid n} \pmod p$
where:
:$\nmid$ denotes non-divisibility
:$\sqbrk \cdots$ is Iverson's convention.
== Proof ==
If $p \nmid n$ then from Fermat's Little Theorem:
:$n^{p - 1} \equiv 1 \pmod p$
If $p \divides n$ then:
:$p \divides n^{p - 1}$
and $n^{p - 1} \equiv 0 \pmod p$ by definition.
Hence the result by definition of Iverson's convention.
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $25$
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 3

== Corollary to Fermat's Little Theorem ==
Let $p^k$ be a prime power for some prime number $p$ and $k \in \Z_{>0}$.
Then:
:$\forall n \in \Z_{>0}: n^{p^k} \equiv n \pmod p$
== Proof ==
The proof proceeds by induction.
For all $k \in \Z_{\ge 1}$, let $\map P k$ be the proposition:
:$\forall n \in \Z_{>0}: n^{p^k} \equiv n \pmod p$
=== Basis for the Induction ===
$\map P 1$ is the case:
:$\forall n \in \Z_{>0}: n^p \equiv n \pmod p$
which follows from .
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P {k - 1}$ is true, where $k \ge 2$, then it logically follows that $\map P k$ is true.
So this is the induction hypothesis:
:$\forall n \in \Z_{>0}: n^{p^{k - 1} } \equiv n \pmod p$
from which it is to be shown that:
:$\forall n \in \Z_{>0}: n^{p^k} \equiv n \pmod p$
=== Induction Step ===
This is the induction step:
For any $n \in \Z_{>0}$ then:
Category:Fermat's Little Theorem
Fermat's Little Theorem/Corollary 4

== Corollary to Fermat's Little Theorem ==
Let $p^k$ be a prime power for some prime number $p$ and $k \in \Z_{\gt 0}$.
Let $n \in \Z_{>0}$ with $p \nmid n$.
Then:
:$n^{p^k - 1} \equiv 1 \pmod p$
== Proof ==
From :
:$n^{p^k} \equiv n \pmod p$
That is:
:$p \divides \paren {n^{p^k} - n} = n \paren {n^{p^k - 1} - 1}$
Since $p \nmid n$, from Prime Divisor of Coprime Integers:
:$p \divides \paren {n^{p^k - 1} - 1}$
That is:
:$n^{p^k - 1} \equiv 1 \pmod p$
Category:Fermat's Little Theorem
Fermat's Little Theorem/Examples/12 Divides n^2-1 if gcd(n, 6)=1

== Examples of Use of Fermat's Little Theorem ==
:$12$ divides $n^2 - 1$ if $\gcd \set {n, 6} = 1 \implies 12 \divides n^2 - 1$
== Proof ==
Then:
So we have:
== Sources ==
* : $\text {3-2}$ Fermat's Little Theorem: Exercise $2$
Category:Fermat's Little Theorem