nyuuzyou/wikis huggingface dataset:
Lexicographic Order of Family of Totally Ordered Sets is Totally Ordered Set

== Theorem ==
Let $\struct {I, \preceq}$ be a well-ordered set.
For each $i \in I$, let $\struct {S_i, \preccurlyeq_i}$ be a totally ordered set.
Let $\ds D = \prod_{i \mathop \in I} S_i$ be the Cartesian product of the family $\family {\struct {S_i, \preccurlyeq_i} }_{i \mathop \in I}$ indexed by $I$.
Let $\preccurlyeq_D$ be the lexicographic order on $D$, defined as:
:$\forall u, v \in D: u \preccurlyeq_D v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in I$ such that $\map u i \ne \map v i$} \end {cases}$
Then $\struct {D, \preccurlyeq_D}$ is a totally ordered set.
== Proof ==
From Lexicographic Product of Family of Ordered Sets is Ordered Set, $\struct {D, \preccurlyeq_D}$ is an ordered set.
It remains to be shown that $\struct {D, \preccurlyeq_D}$ is totally ordered.
Let $p, q \in D$.
If $p = q$, then $p \preccurlyeq_D q$ by the definition of ordering.
If $p \ne q$, then the set $M = \set {i \in I: p_i \ne q_i}$ is non-empty.
Because $\struct {I, \preceq}$ is a well-ordered set and $M \subseteq I$, $M$ has a $\preceq$-least element $k$.
Because $\preccurlyeq_k$ is a total ordering, it must hold that $p_k \preccurlyeq_k q_k$ or $q_k \preccurlyeq_k p_k$.
But:
:$p_k \preccurlyeq_k q_k \implies p \preccurlyeq_D q$
and:
:$q_k \preccurlyeq_k p_k \implies q \preccurlyeq_D p$
so $\preccurlyeq_D$ is a total ordering.
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $35 \ \text {(b)}$
Category:Lexicographic Order
Category:Total Orderings
Lexicographic Order of Family of Well-Ordered Sets is not necessarily Well-Ordered

== Theorem ==
Let $\struct {I, \preceq}$ be a well-ordered set.
For each $i \in I$, let $\struct {S_i, \preccurlyeq_i}$ be a well-ordered set.
Let $\ds D = \prod_{i \mathop \in I} S_i$ be the Cartesian product of the family $\family {\struct {S_i, \preccurlyeq_i} }_{i \mathop \in I}$ indexed by $I$.
Let $\preccurlyeq_D$ be the lexicographic order on $D$, defined as:
:$\forall u, v \in D: u \preccurlyeq_D v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in I$ such that $\map u i \ne \map v i$} \end {cases}$
Then it is not necessarily the case that $\struct {D, \preccurlyeq_D}$ is also a well-ordered set.
== Proof ==
Proof by Counterexample:
Let $\struct {I, \preceq} = \struct {\N, \le}$.
Let $\struct {S_i, \preccurlyeq_i} = \struct {\N, \le}$ for all $i \in \N$.
Let $n \in \N$.
Let $\ds u_n \in \prod_{i \mathop \in \N} \N$ be the mapping defined as:
:$\map {u_n} i = \begin {cases} 0 & : i \le n \\ 1 & : i > n \end {cases}$
It is to be shown that the instances of $u_n$ form an infinite decreasing sequence in $\ds {\bigotimes_{i \mathop \in \N} }^l \N$.
Let $\sequence S$ be the sequence of elements of $\prod_{i \mathop \in \N} \N$ defined as:
:$s_i = \sequence {\map {u_n} i}$
We have that:
:$s_i$ starts with $i - 1$ instances of $0$
:$s_{i + 1}$ starts with $i$ instances of $0$.
Hence $s_i$ and $s_{i + 1}$ are first different at that $i$th element.
Further:
:the $i$th element of $s_i$ is $1$
:the $i$th element of $s_{i + 1}$ is $0$
and so by definition of the lexicographic order:
:$s_{i + 1} \preccurlyeq_l s_i$
We have that the terms of $\sequence S$ form a non-empty subset of $\ds \prod_{i \mathop \in \N} \N$ which has no minimal element by $\preccurlyeq_l$.
Hence by Infinite Sequence Property of Well-Founded Relation, $\preccurlyeq_l$ is not well-founded and so is not a well-ordering.
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $36$
Category:Lexicographic Order
Category:Well-Orderings
Lexicographic Order on Products of Well-Ordered Sets

== Theorem ==
Let $S$ be a set which is well-ordered by $\preccurlyeq$.
Let $\preccurlyeq_l$ be the lexicographic order on the set $T$ of all ordered tuples of $S$.
Then:
:$(1): \quad$ For a given $n \in \N: n > 0$, $\preccurlyeq_l$ is a well-ordering on the set $T_n$ of all ordered $n$-tuples of $S$;
:$(2): \quad \preccurlyeq_l$ is not a well-ordering on the set $T$ of all ordered tuples of $S$.
== Proof ==
It is straightforward to show that $\preccurlyeq_l$ is a total ordering on both $T_n$ and $T$.
It remains to investigate the nature of $\preccurlyeq_l$ as to whether or not it is a well-ordering.
=== Proof for Finite Product ===
=== Proof for Infinite Product ===
Category:Lexicographic Order
Category:Well-Orderings
Lexicographic Product of Family of Ordered Sets is Ordered Set

== Theorem ==
Let $\struct {I, \preceq}$ be a well-ordered set.
For each $i \in I$, let $\struct {S_i, \preccurlyeq_i}$ be an ordered set.
Let $\ds D = \prod_{i \mathop \in I} S_i$ be the Cartesian product of the family $\family {\struct {S_i, \preccurlyeq_i} }_{i \mathop \in I}$ indexed by $I$.
Let $\preccurlyeq_D$ be the lexicographic order on $D$, defined as:
:$\forall u, v \in D: u \preccurlyeq_D v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in I$ such that $\map u i \ne \map v i$} \end {cases}$
Then $\struct {D, \preccurlyeq_D}$ is an ordered set.
== Proof ==
For a subset $J$ of $I$, let $D_J$ be defined as:
:$\ds D_J = \prod_{i \mathop \in J} S_i$
Similarly, let $\preccurlyeq_J$ be the lexicographic order on $D_J$:
:$\forall u, v \in D_J: u \preccurlyeq_J v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in J$ such that $\map u i \ne \map v i$} \end {cases}$
Let $Y$ be the subset of $I$ defined as:
:$\ds Y = \leftset {y \in I: \struct {D_Y, \preccurlyeq_Y} }$ is an ordered set $\rightset{}$
We require to show that $Y = I$.
Let $b \in I$ be the smallest element of $I$.
Let $J = \set b$.
We have that:
We have that $\struct {S_b, \preccurlyeq b}$ is an ordered set.
Thus $b \in Y$ by definition of $Y$.
Let $s \in I$ such that:
:$\forall t \in I: t \prec s \implies t \in Y$
Let $T = \set {t \in I: t \prec s}$.
We have that $T \subseteq I$ such that:
:$\struct {D_T, \preccurlyeq_T}$ is an ordered set.
Now we consider the lexicographic product $D_T \otimes^l S_s$.
By Lexicographic Order is Ordering:
:$\struct {D_T \times S_s, \preccurlyeq l}$ is an ordered set.
We have that $\preccurlyeq l$ is defined as:
:$\tuple {u, s_1} \preccurlyeq_l \tuple {v, s_2} \iff \tuple {u \prec_T v} \lor \paren {u = v \land s_1 \preccurlyeq_s s_2}$
But $\preccurlyeq_T$ is defined as:
:$\forall u, v \in D_T: u \preccurlyeq_T v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in T$ such that $\map u i \ne \map v i$} \end {cases}$
Let $T' = T \cup \set s$.
We see that $\preccurlyeq l$ is the same as:
:$\forall u, v \in D_{T'}: u \preccurlyeq_{T'} v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in T'$ such that $\map u i \ne \map v i$} \end {cases}$
That is:
:$s \in Y$
Thus we have shown that:
:$\paren {\forall t \in I: t \prec s \implies t \in Y} \implies s \in Y$
By Induction on Well-Ordered Set it follows that $Y = I$.
The result follows.
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $35 \ \text {(a)}$
Category:Lexicographic Order
Lexicographically Ordered Pair of Ordered Semigroups with Cancellable Elements

== Theorem ==
Let $\struct {S_1, \circ_1, \preccurlyeq_1}$ and $\struct {S_2, \circ_2, \preccurlyeq_2}$ be ordered semigroups.
Let $\struct {S_1 \times S_2, \odot} := \struct {S_1, \circ_1} \times \struct {S_2, \circ_2}$ denote the external direct product of $\struct {S_1, \circ_1}$ and $\struct {S_2, \circ_2}$.
Let $\struct {S_1 \times S_2, \preccurlyeq_l} := \struct {S_1, \preccurlyeq_1} \otimes^l \struct {S_2, \preccurlyeq_2}$ denote the lexicographic order of $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$:
:$\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2} \iff \paren {x_1 \prec_1 y_1} \lor \paren {x_1 = y_1 \land x_2 \preccurlyeq_2 y_2}$
Let every element of $\struct {S_1, \circ_1}$ be cancellable.
Then $\struct {S_1 \times S_2, \odot, \preccurlyeq_l}$ is also an ordered semigroup.
=== Converse ===
== Proof ==
From Lexicographic Order is Ordering we have that $\struct {S_1 \times S_2, \preccurlyeq_l}$ is an ordered set.
From External Direct Product of Semigroups, $\struct {S_1 \times S_2, \odot}$ is a semigroup.
It remains to be shown that $\preccurlyeq_l$ is compatible with $\odot$.
Let $\tuple {x_1, x_2}, \tuple {y_1, y_2} \in S_1 \times S_2$ be arbitrary such that $\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2}$.
;Case $1$: First suppose $x_1 = y_1$.
;Case $2$: Now suppose $x_1 \prec_1 y_1$.
and the proof is complete.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 15$: Ordered Semigroups: Exercise $15.6$
Category:Lexicographic Order
Category:Ordered Semigroups
Category:Cancellability
Category:Lexicographically Ordered Pair of Ordered Semigroups with Cancellable Elements
Lexicographically Ordered Pair of Ordered Semigroups with Cancellable Elements/Converse

== Theorem ==
Let $\struct {S_1, \circ_1, \preccurlyeq_1}$ and $\struct {S_2, \circ_2, \preccurlyeq_2}$ be ordered semigroups.
Let $\struct {S_1 \times S_2, \odot} := \struct {S_1, \circ_1} \times \struct {S_2, \circ_2}$ denote the external direct product of $\struct {S_1, \circ_1}$ and $\struct {S_2, \circ_2}$.
Let $\struct {S_1 \times S_2, \preccurlyeq_l} := \struct {S_1, \preccurlyeq_1} \otimes^l \struct {S_2, \preccurlyeq_2}$ denote the lexicographic order of $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$:
:$\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2} \iff \paren {x_1 \prec_1 y_1} \lor \paren {x_1 = y_1 \land x_2 \preccurlyeq_2 y_2}$
If $\circ_1$ is not a cancellable operation, then it may not necessarily be the case that $\preccurlyeq_l$ is compatible with $\odot$.
== Proof ==
Recall from Lexicographically Ordered Pair of Ordered Semigroups with Cancellable Elements that if $\circ_1$ is cancellable, then $\preccurlyeq_l$ is compatible with $\odot$.
Let $\Z_2$ denote the set of integers modulo $2$:
:$\Z_2 = \set {0, 1}$
Let $\vee_2$ be the operation on $\Z_2$ defined as:
:$\forall a, b \in \Z_2: a \vee_2 b = \max \set {a, b}$
From Integers Modulo m under Max Operation form Ordered Semigroup, the ordered algebraic structure $\struct {\Z_2, \vee_2, \le}$ is an ordered semigroup.
Let $\struct {\Z_2 \times \Z_2, \odot, \le_l}$ be the external direct product of $\struct {\Z_2, \vee_2, \le}$ with itself, such that:
:$\odot$ is the operation defined as:
::$\forall \tuple {x_1, y_1}, \tuple {x_2, y_2} \in \Z_2 \times \Z_2: \tuple {x_1, y_1} \odot \tuple {x_2, y_2} := \tuple {x_1 \vee_2 x_2, y_1 \vee_2, y_2}$
:$\le_l$ is the lexicographic ordering defined as:
::$\tuple {x_1, x_2} \le_l \tuple {y_1, y_2} \iff \paren {x_1 < y_1} \lor \paren {x_1 = y_1 \land x_2 \le y_2}$
From Lexicographic Order is Ordering we have that $\struct {S_1 \times S_2, \preccurlyeq_l}$ is an ordered set.
From External Direct Product of Semigroups, $\struct {S_1 \times S_2, \odot}$ is a semigroup.
However, we note that $\vee_2$ is not cancellable:
:$0 \vee_2 1 = 1 \vee_2 1$
but:
:$0 \ne 1$
We are now to demonstrate that $\le_l$ is not compatible with $\odot$.
Indeed:
Thus we have that:
Hence and so.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 15$: Ordered Semigroups: Exercise $15.6$
Category:Lexicographically Ordered Pair of Ordered Semigroups with Cancellable Elements
Liber Abaci/Problems/Bezants and a Seventh

== Classic Problem ==
:A man left to his oldest son $1$ bezant and a seventh of what was left;
:then, from the remainder, to his next son he left $2$ bezants and a seventh of what was left;
:then, from the new remainder, to his third son he left $3$ bezants and a seventh of what was left.
:He continued in this way, giving each son $1$ bezant more than the previous son and a seventh of what remained.
:By this division it developed that the last son received all that was left, and all the sons shared equally.
:How many sons were there and how large was the man's estate?
== Solution ==
There were $6$ sons and $36$ bezants.
== Proof ==
Let the last son receive $n$ bezants.
Then the last son but one received $n - 1$ bezants plus $\dfrac 1 7$ of what remained.
But that also equals $n$ bezants.
So the last son received $\paren {n - 1} + 1$ bezant.
Therefore what remained after his having taken $n - 1$ bezants must have been $7 \times 1 = 7$ bezants.
He took $1$ more bezant, leaving $6$.
Because the $n$th son took $n$ bezants, it must be the case that there were $6$ sons, all of whom took $6$ bezants.
To check this, we confirm what each son receives:
:Son $1$ took $1$ bezant and $\frac 1 7 \times 35 = 5$ bezants, leaving $30$ bezants.
:Son $2$ took $2$ bezants and $\frac 1 7 \times 28 = 4$ bezants, leaving $24$ bezants.
:Son $3$ took $3$ bezants and $\frac 1 7 \times 21 = 3$ bezants, leaving $18$ bezants.
:Son $4$ took $4$ bezants and $\frac 1 7 \times 14 = 2$ bezants, leaving $12$ bezants.
:Son $5$ took $5$ bezants and $\frac 1 7 \times 7 = 1$ bezants, leaving $6$ bezants.
:Son $6$ took $6$ bezants, and there was nothing left over.
== Sources ==
* 
* : p. $230$
* : Liber Abaci: $90$
Category:Classic Problems
Category:Liber Abaci
Liber Abaci/Problems/Lion, Leopard and Bear

== Classic Problem ==
:A lion would take $4$ hours to eat $1$ sheep.
:A leopard would take $5$ hours.
:A bear would take $6$.
:If a single sheep were to be thrown to them, how many hours would it take to devour it?
== Solution ==
The three together would consume the sheep in $1 \frac {23} {37}$ hours.
== Proof ==
Using the Method of False Position:
For $4$ hours, in which the lion eats a sheep, put $\dfrac 1 4$.
For the $5$ hours the leopard takes, put $\dfrac 1 5$.
For the $6$ hours the bear takes, put $\dfrac 1 6$.
Because $\dfrac 1 6$, $\dfrac 1 5$ and $\dfrac 1 4$ are found exactly in $60$, suppose that in $60$ hours they devour the sheep.
Then consider how many sheep a lion can eat in $60$ hours;
:since in four hours it can devour one sheep, it can consume $15$ sheep in $60$ hours
and the leopard would eat $12$ as a fifth of $60$ is $12$.
Similarly the bear would eat $10$, as $\dfrac 1 6$ of $60$ is $10$.
Therefore in $60$ hours, all $3$ together would eat $15 + 12 + 10 = 37$ sheep.
So if takes them $60$ hours to eat $37$ sheep, it takes then $\dfrac {37} {60}$ hours to consume $1$ sheep.
Hence the result.
== Historical Note ==
== Sources ==
* 
* : $\text {7.A}$: The Thirteenth and Fourteenth Centuries: $\text {7.A1}$: Leonardo Fibonacci: $\text {(d)}$: The Lion, the leopard and the bear
* : Liber Abaci: $89$
Category:Classic Problems
Category:Cistern Problems
Category:Liber Abaci
Liber Abaci/Problems/Lion, Leopard and Bear/Historical Note

== Historical Note on The Lion, the Leopard and the Bear ==
As pointed out by and in their of $1987$, this is a "more gory version" of the cistern problem, as seen for example in the Greek Anthology Book $\text {XIV}$, no. $132$.
Instead of $3$ pipes pouring water into a pool at given rates, $3$ animals remove flesh from a sheep at different rates.
== Sources ==
* : $\text {7.A}$: The Thirteenth and Fourteenth Centuries
* : Liber Abaci: $89$
Category:Historical Notes
Liber Abaci/Problems/Orchard with Seven Gates

== Classic Problem ==
:A man entered an orchard with $7$ gates, and there took a certain number of apples.
:When he left the orchard he gave the first guard $\dfrac 1 2$ the apples and $1$ apple more.
:To the second guard he gave $\dfrac 1 2$ of his remaining apples and $1$ apple more.
:He did the same for all the remaining $5$ guards, and left the orchard with $1$ apple.
:How many apples did he gather in the orchard?
== Solution ==
$382$ apples.
== Proof ==
After his encounter with the $7$th guard he had one apple left.
After giving the guard $\dfrac 1 2$ his apples, and before giving him $1$ more, he would have had $2$ apples.
Hence after leaving the $6$th guard, he had $4$ apples.
Similarly:
:after leaving the $5$th guard he had $2 \paren {4 + 1} = 10$ apples
:after leaving the $4$th guard he had $2 \paren {10 + 1} = 22$ apples
:after leaving the $3$rd guard he had $2 \paren {22 + 1} = 46$ apples
:after leaving the $2$nd guard he had $2 \paren {46 + 1} = 94$ apples
:after leaving the $1$st guard he had $2 \paren {94 + 1} = 190$ apples
:before meeting the $1$st guard he had $2 \paren {190 + 1} = 382$ apples.
== Sources ==
* 
* : p. $231$
* : Liber Abaci: $91$
Category:Liber Abaci
Lie Algebra is Anticommutative

== Theorem ==
Let $L$ be a Lie algebra.
Then $L$ is anticommutative:
:$\forall a, b \in L: \sqbrk {a, b} = -\sqbrk {b, a}$
where $\sqbrk {\, \cdot, \cdot \,}$ denotes the bilinear mapping over $L$.
== Proof ==
== Notes ==
The converse, that in a bilinear context anticommutativity implies $[x,x]=0$, is not quite true; however, the only exceptions occur when the vector space underlying the Lie algebra are over a field of characteristic 2.
Category:Lie Theory
Category:Anticommutativity
Lift a Bottle using Single Straw

== Problem ==
How can a bottle be lifted using a single straw?
== Solution ==
Bend the straw, so that the length after the bend is a little wider than the width of the bottle.
Push the bent corner into the bottle, so that when it opens out, the bent bit will open out with one end against the side of the bottle, inside the neck.
Then lift the other end of the straw, and the straw will act like a barb, and the bent bit will prevent the straw from coming out of the bottle.
It will exert enough force on the bottle so as to allow the latter to be lifted into the air.
== Historical Note ==
== Sources ==
* 
* : Henry van Etten: $115$
Category:Physics
Category:Classic Problems
Lifting The Exponent Lemma

== Theorem ==
Let $x, y \in \Z$ be distinct integers.
Let $n \ge 1$ be a natural number.
Let $p$ be an odd prime.
Let:
:$p \divides x - y$
and:
:$p \nmid x y$
where $\divides$ and $\nmid$ denote divisibility and non-divisibility respectively.
Then
:$\map {\nu_p} {x^n - y^n} = \map {\nu_p} {x - y} + \map {\nu_p} n$
where $\nu_p$ denotes $p$-adic valuation.
== Proof ==
=== Lemma ===
Let $k = \map {\nu_p} n$.
Then $n = p^k m$ such that $p \nmid m$.
By P-adic Valuation of Difference of Powers with Coprime Exponent:
:$\map {\nu_p} {x^n - y^n} = \map {\nu_p} {x^{p^k} - y^{p^k} }$
By repeatedly applying the lemma:
:$\map {\nu_p} {x^{p^k} - y^{p^k} } = \map {\nu_p} {x - y} + k$
== Also see ==
* Lifting The Exponent Lemma for Sums
* Lifting The Exponent Lemma for p=2
== Sources ==
* 
Category:P-adic Valuations
Category:Number Theory
Category:Lifting The Exponent Lemma
Lifting The Exponent Lemma/Lemma

== Lemma ==
Let $x, y \in \Z$ be distinct integers.
Let $p$ be an odd prime.
Let:
:$p \divides x - y$
and:
:$p \nmid x y$.
Then 
:$\map {\nu_p} {x^p - y^p} = \map {\nu_p} {x - y} + 1$
where $\nu_p$ denotes $p$-adic valuation.
== Proof ==
Let $\map {\nu_p} {x - y} = k$.
Then $x=p^k m + y$ where $p \nmid m$.
We have:
Note that all terms in the above expression have a factor of $p$ to the order at least $k+1$.
So, $p^{k + 1} \mid x^p - y^p$.
Also note that all terms in the summation have a factor of $p$ to the order at least $k + 2$.
But in the term $p^{k + 1} m y^{p - 1}$, since $p \nmid m$ and $p \nmid y$, we have:
:$p^{k + 2} \nmid p^{k + 1} m y^{p - 1}$
So:
:$p^{k + 2} \nmid x^p - y^p$
So by definition of $p$-adic valuation:
:$\map {\nu_p} {x^p - y^p} = k + 1$
== Sources ==
* : Theorem $\text{III}$.
Category:P-adic Valuations
Lifting The Exponent Lemma for Sums

== Theorem ==
Let $x, y \in \Z$ be integers with $x + y \ne 0$.
Let $n \ge 1$ be an odd natural number.
Let $p$ be an odd prime.
Let:
:$p \divides x + y$
and:
:$p \nmid x y$
where $\divides$ and $\nmid$ denote divisibility and non-divisibility respectively.
Then:
:$\map {\nu_p} {x^n + y^n} = \map {\nu_p} {x + y} + \map {\nu_p} n$
where $\nu_p$ denotes $p$-adic valuation.
</onlyinclude>
== Proof ==
This follows from the Lifting The Exponent Lemma with $y$ replaced by $-y$.
== Also see ==
* Lifting The Exponent Lemma for Sums for p=2
Category:Lifting The Exponent Lemma
Lifting The Exponent Lemma for Sums for p=2

== Theorem ==
Let $x, y \in \Z$ be integers with $x + y \ne 0$.
Let $n \ge 1$ be an odd natural number.
Let:
:$2 \divides x + y$
where $\divides$ denotes divisibility.
Then:
:$\map {\nu_2} {x^n + y^n} = \map {\nu_2} {x + y}$
where $\nu_2$ denotes $2$-adic valuation.
</onlyinclude>
== Proof ==
This follows from the Lifting The Exponent Lemma for p=2 with $y$ replaced by $-y$.
== Also see ==
* Lifting The Exponent Lemma for Sums
Category:Lifting The Exponent Lemma
Lifting The Exponent Lemma for p=2

== Theorem ==
Let $x, y \in \Z$ be distinct odd integers.
Let $n \ge 1$ be a natural number.
Let:
:$4 \divides x - y$
where $\divides$ denotes divisibility.
Then
:$\map {\nu_2} {x^n - y^n} = \map {\nu_2} {x - y} + \map {\nu_2} n$
where $\nu_2$ denotes $2$-adic valuation.
=== Corollary ===
== Proof ==
Let $k = \map {\nu_2} n$.
Then $n = 2^k m$ with $2 \nmid m$.
By P-adic Valuation of Difference of Powers with Coprime Exponent:
:$\map {\nu_2} {x^n - y^n} = \map {\nu_2} {x^{2^k} - y^{2^k} }$
Note that:
:$x^{2^k} - y^{2^k} = \paren {x - y} \cdot \ds \prod_{i \mathop = 0}^{k - 1} \paren {x^{2^i} + y^{2^i} }$
By Square Modulo 4:
:$\map {\nu_2} {x^{2^i} + y^{2^i} } = 1$
for $i > 0$.
Because $4 \divides \paren {x - y}$, $4 \nmid \paren {x + y}$.
Thus:
:$\map {\nu_2} {x + y} = 1$
Thus:
== Also see ==
* Lifting The Exponent Lemma
* Lifting The Exponent Lemma for Sums for p=2
Category:Lifting The Exponent Lemma
Lifting The Exponent Lemma for p=2/Corollary

== Corollary to Lifting The Exponent Lemma for p=2 ==
Let $x, y \in \Z$ be distinct odd integers.
Let $n \geq1$ be an even natural number.
Then
:$\nu_2 \left({x^n - y^n}\right) = \nu_2 \left({x + y}\right) + \nu_2 \left({x - y}\right) + \nu_2 \left({n}\right) - 1$
where $\nu_2$ denotes $2$-adic valuation.
== Proof ==
By Square Modulo 4, $4\mid x^2-y^2$.
By Lifting The Exponent Lemma for p=2:
Category:Lifting The Exponent Lemma
Lightning Calculation by 9-Digit Number

== Party Trick ==
Ask someone in the audience for some $9$-digit number.
You will then announce that you are going to multiply it by $142 \, 857 \, 143$ in your head.
You start writing down that product from the moment the first few digits are being given to you.
== The Secret ==
You mentally write down that big number twice, concatenating the two parts to obtain a big number of twice the length.
Then you divide this number by $7$, which, using the standard algorithm for division, you do from the .
== Examples ==
== Proof ==
We have that:
:$142 \, 857 \, 143 \times 7 = 1 \, 000 \, 000 \, 001$
By writing down the given $9$-digit number twice, you are multiplying it by $1 \, 000 \, 000 \, 001$.
So dividing that number by $7$ you are multiplying the original $9$-digit number by $142 \, 857 \, 143$.
== Sources ==
* : $142,857$
* : $142,857$
Category:Recreational Mathematics
Category:Lightning Calculation by 9-Digit Number
Lightning Calculation by 9-Digit Number/Examples/577,831,345

== Example of Lightning Calculation by 9-Digit Number ==
The showman announces he will instantly multiply any given $9$-digit number by $142 \, 857 \, 143$.
The given $9$-digit number is $577 \, 831 \, 345$.
Thus by division by $7$:
 82,547,335,082,547,335
 ------------------------
7)577,831,345,577,831,345
== Sources ==
* : $142,857$
* : $142,857$
Category:Lightning Calculation by 9-Digit Number
Lightning Never Strikes Twice

== Fallacy ==
Lightning never strikes twice in the same place.
== Refutation ==
The mathematical idea behind this fallacy is that if a supposedly-improbable event has happened once, then it is less likely for it to happen again.
This is similar to the fallacy that if a fair coin has come up heads a lot when tossed, then the chance of it coming up tails next time must be increased.
Category:Fallacies and Mistakes