avewright/proofwiki-math huggingface dataset:
Theorem: Modulo Multiplication is Closed

Multiplication modulo $m$ is closed on the set of integers modulo $m$:
:$\forall \eqclass x m, \eqclass y m \in \Z_m: \eqclass x m \times_m \eqclass y m \in \Z_m$.

Proof:
From the definition of multiplication modulo $m$, we have:
:$\eqclass x m \times_m \eqclass y m = \eqclass {x y} m$
By the Division Theorem:
:$x y = q m + r$ where $0 \le r < m$
Therefore for all $0 \le r < m$:
:$\eqclass {x y} m = \eqclass r m$
Therefore from the definition of integers modulo $m$:
:$\eqclass {x y} m \in \Z_m$
{{qed}}
Theorem: Modulo Multiplication is Associative

Multiplication modulo $m$ is associative:
:$\forall \eqclass x m, \eqclass y m, \eqclass z m \in \Z_m: \paren {\eqclass x m \times_m \eqclass y m} \times_m \eqclass z m = \eqclass x m \times_m \paren {\eqclass y m \times_m \eqclass z m}$
That is:
:$\forall x, y, z \in \Z_m: \paren {x \cdot_m y} \cdot_m z = x \cdot_m \paren {y \cdot_m z}$

Proof:
{{begin-eqn}}
{{eqn | l = \paren {\eqclass x m \times_m \eqclass y m} \times_m \eqclass z m
      | r = \eqclass {x y} m \times_m \eqclass z m
      | c = {{Defof|Modulo Multiplication}}
}}
{{eqn | r = \eqclass {\paren {x y} z} m
      | c = {{Defof|Modulo Multiplication}}
}}
{{eqn | r = \eqclass {x \paren {y z} } m
      | c = Integer Multiplication is Associative
}}
{{eqn | r = \eqclass x m \times_m \eqclass {y z} m
      | c = {{Defof|Modulo Multiplication}}
}}
{{eqn | r = \eqclass x m \times_m \paren {\eqclass y m \times_m \eqclass z m}
      | c = {{Defof|Modulo Multiplication}}
}}
{{end-eqn}}
{{qed}}
Theorem: Modulo Multiplication is Associative

Multiplication modulo $m$ is associative:
:$\forall \eqclass x m, \eqclass y m, \eqclass z m \in \Z_m: \paren {\eqclass x m \times_m \eqclass y m} \times_m \eqclass z m = \eqclass x m \times_m \paren {\eqclass y m \times_m \eqclass z m}$
That is:
:$\forall x, y, z \in \Z_m: \paren {x \cdot_m y} \cdot_m z = x \cdot_m \paren {y \cdot_m z}$

Proof:
Let $j$ be the largest integer such that:
:$j m \le x y$
Let $p$ be the largest integer such that:
:$p m \le y z$
By definition of multiplication modulo $m$:
:$x \cdot_m y = x y - j m$
:$y \cdot_m z = y z - p m$
Let $k$ be the largest integer such that:
:$k m \le \paren {x y - j m} z$
Let $q$ be the largest integer such that:
:$q m \le x \paren {y z - p m}$
Then:
:$\paren {j z + k} m \le \paren {x y} z$
:$\paren {q + x p} m \le x \paren {y z}$
Thus:
{{begin-eqn}}
{{eqn | l = \paren {x \cdot_m y} \cdot_m z
      | r = \paren {x y - j m} z - k m
      | c = {{Defof|Modulo Multiplication}}
}}
{{eqn | l = x \cdot_m \paren {y \cdot_m z}
      | r = x \left({y z - p m}\right) - q m
      | c = {{Defof|Modulo Multiplication}}
}}
{{end-eqn}}
But suppose that there exists an integer $s$ such that:
:$s m \le \paren {x y} z$
and:
:$j z + k < s$
Then:
:$\paren {j z + k + 1} m \le \paren {x y} z$
from which:
:$\paren {k + 1} m \le \paren {x y - j m} z$
But this contradicts the definition of $k$.
Thus $j z + k$ is the largest of those integers $i$ such that $i m \le \paren {x y} z$.
Similarly, $q + x p$ is the largest of those integers $i$ such that $i m \le x \paren {y z}$.
From Integer Multiplication is Associative:
:$\paren {x y} z = x \paren {y z}$
Thus $j z + k = q + x p$ and so:
{{begin-eqn}}
{{eqn | l = \paren {x \cdot_m y} \cdot_m z
      | r = \paren {x y - j m} z - k m
      | c = {{Defof|Modulo Multiplication}}
}}
{{eqn | r = x y z - \paren {j z + k} m
      | c = 
}}
{{eqn | r = x y z - \paren {q + x p} m
      | c = 
}}
{{eqn | r = x \paren {y z - p m} - q m
      | c = 
}}
{{eqn | r = x \cdot_m \paren {y \cdot_m z}
      | c = {{Defof|Modulo Multiplication}}
}}
{{end-eqn}}
{{qed}}
Theorem: Modulo Multiplication is Commutative

Multiplication modulo $m$ is commutative:
:$\forall \eqclass x m, \eqclass y m \in \Z_m: \eqclass x m \times_m \eqclass y m = \eqclass y m \times_m \eqclass x m$

Proof:
{{begin-eqn}}
{{eqn | l = \eqclass x m \times_m \eqclass y m
      | r = \eqclass {x y} m
      | c = {{Defof|Modulo Multiplication}}
}}
{{eqn | r = \eqclass {y x} m
      | c = Integer Multiplication is Commutative
}}
{{eqn | r = \eqclass y m \times_m \eqclass x m
      | c = {{Defof|Modulo Multiplication}}
}}
{{end-eqn}}
{{qed}}
Theorem: Modulo Multiplication has Identity

Multiplication modulo $m$ has an identity:
:$\forall \eqclass x m \in \Z_m: \eqclass x m \times_m \eqclass 1 m = \eqclass x m = \eqclass 1 m \times_m \eqclass x m$

Proof:
Follows directly from the definition of multiplication modulo $m$:
{{begin-eqn}}
{{eqn | l = \eqclass x m \times_m \eqclass 1 m
      | r = \eqclass {x \times 1} m
      | c = 
}}
{{eqn | r = \eqclass x m
      | c = 
}}
{{eqn | r = \eqclass {1 \times x} m
      | c = 
}}
{{eqn | r = \eqclass 1 m \times_m \eqclass x m
      | c = 
}}
{{end-eqn}}
Thus $\eqclass 1 m$ is the identity for multiplication modulo $m$.
{{qed}}
Theorem: Modulo Multiplication Distributes over Modulo Addition

Multiplication modulo $m$ is distributive over addition modulo $m$:
:$\forall \eqclass x m, \eqclass y m, \eqclass z m \in \Z_m$:
:: $\eqclass x m \times_m \paren {\eqclass y m +_m \eqclass z m} = \paren {\eqclass x m \times_m \eqclass y m} +_m \paren {\eqclass x m \times_m \eqclass z m}$
:: $\paren {\eqclass x m +_m \eqclass y m} \times_m \eqclass z m = \paren {\eqclass x m \times_m \eqclass z m} +_m \paren {\eqclass y m \times_m \eqclass z m}$
where $\Z_m$ is the set of integers modulo $m$.
That is, $\forall x, y, z, m \in \Z$:
: $x \paren {y + z} \equiv x y + x z \pmod m$
: $\paren {x + y} z \equiv x z + y z \pmod m$

Proof:
Follows directly from the definition of multiplication modulo $m$ and addition modulo $m$:
{{begin-eqn}}
{{eqn | l = \eqclass x m \times_m \paren {\eqclass y m +_m \eqclass z m}
      | r = \eqclass x m \times_m \eqclass {y + z} m
      | c = 
}}
{{eqn | r = \eqclass {x \paren {y + z} } m
      | c = 
}}
{{eqn | r = \eqclass {\paren {x y} + \paren {x z} } m
      | c = 
}}
{{eqn | r = \eqclass {x y} m +_m \eqclass {x z} m
      | c = 
}}
{{eqn | r = \paren {\eqclass x m \times_m \eqclass y m} +_m \paren {\eqclass x m \times_m \eqclass z m}
      | c = 
}}
{{end-eqn}}
And the second is like it, namely this:
{{begin-eqn}}
{{eqn | l = \paren {\eqclass x m +_m \eqclass y m} \times_m \eqclass z m
      | r = \eqclass {x + y} m \times_m \eqclass z m
      | c = 
}}
{{eqn | r = \eqclass {\paren {x + y} z} m
      | c = 
}}
{{eqn | r = \eqclass {\paren {x z} + \paren {y z} } m
      | c = 
}}
{{eqn | r = \eqclass {x z} m +_m \eqclass {y z} m
      | c = 
}}
{{eqn | r = \paren {\eqclass x m \times_m \eqclass z m} +_m \paren {\eqclass y m \times_m \eqclass z m}
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Intersection of Congruence Classes

Let $\RR_m$ denote congruence modulo $m$ on the set of integers $\Z$.
Then:
:$\RR_m \cap \RR_n = \RR_{\lcm \set {m, n} }$
where $\lcm \set {m, n}$ is the lowest common multiple of $m$ and $n$.
In the language of modulo arithmetic, this is equivalent to:
:$a \equiv b \pmod m, a \equiv b \pmod n \implies a \equiv b \pmod {\lcm \set {m, n} }$

Proof:
Let $\tuple {a, b} \in \RR_m \cap \RR_n$.
That is, let $\tuple {a, b} \in \RR_m$ and $\tuple {a, b} \in \RR_n$.
That means, by definition of congruence:
:$a \equiv b \pmod m$
:$a \equiv b \pmod n$
Thus by definition of congruence:
:$\exists r, s \in \Z: a - b = r m, a - b = s n$
Let $d = \gcd \set {m, n}$ so that $m = d m', n = d n', m' \perp n'$.
Substituting for $m$ and $n$:
:$r d m' = s d n'$ and so $r m' = s n'$.
So $n' \divides r m'$ and $m' \perp n'$ so by Euclid's Lemma $n' \divides r$.
So we can put $r = k n'$ and get:
:$a - b = r m = k m n' = k m \dfrac n d = k \dfrac {m n} d$
But:
:$\dfrac {m n} d = \dfrac {m n} {\gcd \set {m, n} }$
So by Product of GCD and LCM:
:$a - b = k \lcm \set {m, n}$
So:
:$a \equiv b \pmod {\lcm \set {m, n} }$
and hence the result.
{{qed}}
Theorem: Mappings Between Residue Classes

Let $\eqclass a m$ be the residue class of $a$ (modulo $m$).
Let $\phi: \Z_m \to \Z_n$ be a mapping given by:
:$\map \phi {\eqclass x m} = \eqclass x n$
Then $\phi$ is well defined {{iff}} $m$ is a divisor of $n$.

Proof:
For $\phi$ to be well defined, we require that:
:$\forall x, y \in \Z_m: \eqclass x m = \eqclass y m \implies \map \phi {\eqclass x m} = \map \phi {\eqclass y m}$
Now:
:$\eqclass x m = \eqclass y m \implies x - y \divides m$
For $\map \phi {\eqclass x m} = \map \phi {\eqclass y m}$ we require that:
:$\eqclass x n = \eqclass y n \implies x - y \divides n$
Thus $\phi$ is well defined {{iff}}:
:$x - y \divides m \implies x - y \divides n$
That is, {{iff}} $m \divides n$.
{{qed}}
Theorem: GCD from Congruence Modulo m

Let $a, b \in \Z, m \in \N$.
Let $a$ be congruent to $b$ modulo $m$.
Then the GCD of $a$ and $m$ is equal to the GCD of $b$ and $m$.
That is:
:$a \equiv b \pmod m \implies \gcd \set {a, m} = \gcd \set {b, m}$

Proof:
We have:
:$a \equiv b \pmod m \implies \exists k \in \Z: a = b + k m$
Thus:
:$a = b + k m$
and the result follows directly from GCD with Remainder.
{{qed}}
Theorem: Prime Number has 4 Integral Divisors

Let $p$ be an integer.
Then $p$ is a prime number {{iff}} $p$ has exactly four integral divisors: $1, -1, p, -p$.

Proof:
=== Necessary Condition ===
Let $p$ be a prime number from the definition that $p$ has exactly $2$ divisors which are positive integers.
From One Divides all Integers and Integer Divides Itself those positive integers are $1$ and $p$.
Also, we have $-1 \divides p$ and $-p \divides p$ from One Divides all Integers and Integer Divides its Negative.
{{AimForCont}}:
: $\exists x < 0: x \divides p$
where $x \ne -1$ and $x \ne -p$.
Then:
: $\size x \divides x \divides p$
and so $\size x$ is therefore a positive integer other than $1$ and $p$ that divides $p$.
This is a contradiction of the condition for $p$ to be prime.
So $-1$ and $-p$ are the only negative integers that divide $p$.
It follows that $p$ has exactly those four divisors.
{{qed|lemma}}
=== Sufficient Condition ===
Suppose $p$ has the divisors $1, -1, p, -p$.
It follows that $1$ and $p$ are the only positive integers that divide $p$.
Thus $p$ has exactly two divisors which are positive integers.
{{qed}}
Theorem: Prime not Divisor implies Coprime

Let $p, a \in \Z$.
If $p$ is a prime number then:
:$p \nmid a \implies p \perp a$
where:
:$p \nmid a$ denotes that $p$ does not divide $a$
:$p \perp a$ denotes that $p$ and $a$ are coprime.
It follows directly that if $p$ and $q$ are primes, then:
:$p \divides q \implies p = q$
:$p \ne q \implies p \perp q$

Proof:
Let $p \in \Bbb P, p \nmid a$.
We need to show that $\gcd \set {a, p} = 1$.
Let $\gcd \set {a, p} = d$.
As $d \divides p$, we must have $d = 1$ or $d = p$ by GCD with Prime.
But if $d = p$, then $p \divides a$ by definition of greatest common divisor.
So $d \ne p$ and therefore $d = 1$.
{{qed}}
Theorem: Prime not Divisor implies Coprime

Let $p, a \in \Z$.
If $p$ is a prime number then:
:$p \nmid a \implies p \perp a$
where:
:$p \nmid a$ denotes that $p$ does not divide $a$
:$p \perp a$ denotes that $p$ and $a$ are coprime.
It follows directly that if $p$ and $q$ are primes, then:
:$p \divides q \implies p = q$
:$p \ne q \implies p \perp q$

Proof:
Let $p$ be a prime number.
Let $a \in \Z$ be such that $p$ is not a divisor of $a$.
{{AimForCont}} $p$ and $a$ are not coprime.
Then:
:$\exists c \in \Z_{>1}: c \divides p, c \divides a$
where $\divides$ denotes divisibility.
But then by definition of prime:
:$c = p$
Thus:
:$p \divides a$
The result follows by Proof by Contradiction.
{{qed}}
Theorem: Composite Number has Two Divisors Less Than It

Let $n \in \Z_{> 1}$ such that $n \notin \mathbb P$.
Then:
:$\exists a, b \in \Z: 1 < a < n, 1 < b < n: n = a b$
That is, a non-prime number greater than $1$ can be expressed as the product of two positive integers strictly greater than $1$ and less than $n$.
Note that these two numbers are not necessarily distinct.

Proof:
Since $n \notin \mathbb P$, it has a positive factor $a$ such that $a \ne 1$ and $a \ne n$.
Hence $\exists b \in \Z: n = a b$.
Thus by definition of factor:
:$a \divides n$
where $\divides$ denotes divisibility.
From Divisor Relation on Positive Integers is Partial Ordering:
:$a \le n$
As $a \ne n$, it follows that $a < n$.
From One Divides all Integers:
:$1 \divides a$
Thus from Divisor Relation on Positive Integers is Partial Ordering:
:$1 \le a$
Similarly, as $1 \ne a$ it follows that $1 < a$.
Since $a \ne n$, it follows that $b \ne 1$.
Similarly, since $a \ne 1$, it follows that $b \ne n$.
Thus:
:$b \divides n: 1 \ne b \ne n$
Arguing as above, we show that $1 < b < n$ and the result follows.
{{qed}}
Note that we have not shown (and it is not necessarily the case) that $a \ne b$.
Category:Divisors
197jd22ea9wbyx8phcgp1vaw454jncw
Theorem: Condition for Divisibility of Powers of Prime

Let $p$ be a prime.
Let $k, l \in \Z_{>0}$.
Then:
:$p^k \divides p^l \iff k \le l$

Proof:
=== Necessary Condition ===
Let $k \le l$.
Then:
:$l - k \ge 0$
Thus $p^k, p^{l - k} \in \Z$ such that $p^l = p^k p^{l - k}$.
Thus:
:$p^k \divides p^l$
{{qed|lemma}}
Theorem: Exponents of Primes in Prime Decomposition are Less iff Divisor

Let $a, b \in \Z_{>0}$.
Then $a \divides b$ {{iff}}:
:$(1): \quad$ every prime $p_i$ in the prime decomposition of $a$ appears in the prime decomposition of $b$
and:
:$(2): \quad$ the exponent of each $p_i$ in $a$ is less than or equal to its exponent in $b$.

Proof:
Let $a, b \in \Z_{>0}$.
Let their prime decomposition be:
:$a = p_1^{k_1} p_2^{k_2} \dotsm p_n^{k_n}$
:$b = q_1^{l_1} q_2^{l_2} \dotsm q_n^{l_n}$
Theorem: Not Coprime means Common Prime Factor

Let $a, b \in \Z$.
If $d \divides a$ and $d \divides b$ such that $d > 1$, then $a$ and $b$ have a common divisor which is prime.

Proof:
As $d > 1$, it has a prime decomposition.
Thus there exists a prime $p$ such that $p \divides d$.
From Divisor Relation on Positive Integers is Partial Ordering, we have $p \divides d, d \divides a \implies p \divides a$, and similarly for $b$.
The result follows.
{{qed}}
Category:Coprime Integers
Category:Prime Numbers
1dbh22tlukqincvbw8rkczuduc9vuvj
Theorem: Set of Divisors of Integer

Let $n \in \Z_{>1}$.
Let $n$ be expressed in its prime decomposition:
:$n = p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r}$
where $p_1 < p_2 < \dotsb < p_r$ are distinct primes and $k_1, k_2, \ldots, k_r$ are positive integers.
The set of divisors of $n$ is:
:$\set {p_1^{h_1} p_2^{h_2} \dotsm p_r^{h_r}: 0 \le h_i \le k_i, i = 1, 2, \ldots, r}$

Proof:
Each integer in the given set is a divisor of $n$ because:
:$(1): \quad \forall i: k_i - h_i \ge 0$
:$(2): \quad n = \paren {p_1^{h_1} p_2^{h_2} \dotsm p_r^{h_r} } p_1^{k_1 - h_1} p_2^{k_2 - h_2} \ldots p_r^{k_r - h_r}$
from Exponents of Primes in Prime Decomposition are Less iff Divisor.
By the Fundamental Theorem of Arithmetic, these integers are distinct.
It is necessary to show that the integers in this set are the ''only'' divisors of $n$.
Let $d > 1$ and let $p \in \mathbb P: p \divides d$.
{{begin-eqn}}
{{eqn | o = 
      | r = p \divides d \land d \divides n
      | c = 
}}
{{eqn | o = \leadsto
      | r = p \divides n
      | c = Divisor Relation on Positive Integers is Partial Ordering
}}
{{eqn | o = \leadsto
      | r = \exists i: p = p_i, 1 \le i \le r
      | c = 
}}
{{eqn | o = \leadsto
      | r = p \in \set {p_i: 1 \le i \le r}
      | c = 
}}
{{eqn | o = \leadsto
      | r = d = p_1^{h_1} p_2^{h_2} \dotsm p_r^{h_r}: 0 \le h_i
      | c = 
}}
{{end-eqn}}
It remains to be shown that:
:$\forall i: h_1 \le k_i$
First note that:
:$d \divides n \implies \forall i: p_i^{k_i} \divides n$
From above, all the primes $p_i$ are distinct.
Therefore by Prime not Divisor implies Coprime:
:$p_1 \nmid p_2^{k_2} p_3^{k_3} \dotsm p_r^{k_r} \implies \gcd \set {p_1, p_2^{k_2} p_3^{k_3} \ldots p_r^{k_r} } = 1$
So:
:$p_1^{h_1} \divides n \implies n = p_1^{k_1} \paren {p_2^{k_2} p_3^{k_3} \dotsm p_r^{k_r} }$
By Euclid's Lemma:
:$p_1^{h_1} \divides p_1^{k_1} \implies h_1 \le k_1$
and the same argument applies to each of the other prime factors of $n$.
The result follows.
{{qed}}
Category:Number Theory
rzbwqi92fhcc2ar5kuqb694dh6aozep
Theorem: Sum Less Minimum is Maximum

For all numbers $a, b$ where $a, b$ in $\N, \Z, \Q$ or $\R$:
:$a + b - \min \set {a, b} = \max \set {a, b}$

Proof:
From Sum of Maximum and Minimum we have that $a + b = \max \set {a, b} + \min \set {a, b}$.
Thus $a + b - \min \set {a, b} = \max \set {a, b}$ follows by subtracting $\min \set {a, b}$ from both sides.
It is clear that this result applies when $a, b$ in $\Z, \Q$ or $\R$, as subtraction is well-defined throughout those number sets.
However, it can be seen to apply in $\N$ as well, despite the fact that $n - m$ is defined on $\N$ only when $n \ge m$.
This is because the fact that $a + b \ge \min \set {a, b}$ follows immediately again from $a + b = \max \set {a, b} + \min \set {a, b}$.
{{qed}}
Category:Algebra
bvhtrgkqvzrov81mcjvejd4x9y9g0fq
Theorem: Sum Less Maximum is Minimum

For all numbers $a, b$ where $a, b$ in $\N, \Z, \Q$ or $\R$:
:$a + b - \max \set {a, b} = \min \set {a, b}$.

Proof:
From Sum of Maximum and Minimum we have that $a + b = \max \set {a, b} + \min \set {a, b}$.
Thus $a + b - \max \set {a, b} = \min \set {a, b}$ follows by subtracting $\max \set {a, b}$ from both sides.
It is clear that this result applies when $a, b$ in $\Z, \Q$ or $\R$, as subtraction is well-defined throughout those number sets.
However, it can be seen to apply in $\N$ as well, despite the fact that $n - m$ is defined on $\N$ only when $n \ge m$.
This is because the fact that $a + b \ge \max \set {a, b}$ follows immediately again from $a + b = \max \set {a, b} + \min \set {a, b}$.
{{qed}}
Category:Algebra
p7n9y5qiemvv9doosc5na3bko9m1wpn
Theorem: GCD and LCM from Prime Decomposition

Let $m, n \in \Z$.
Let:
:$m = p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r}$
:$n = p_1^{l_1} p_2^{l_2} \dotsm p_r^{l_r}$
:$p_i \divides m \lor p_i \divides n, 1 \le i \le r$.
That is, the primes given in these prime decompositions may be divisors of ''either'' of the numbers $m$ or $n$.
Note that if one of the primes $p_i$ does not appear in the prime decompositions of either one of $m$ or $n$, then its corresponding index $k_i$ or $l_i$ will be zero.
Then the following results apply:
:$\gcd \set {m, n} = p_1^{\min \set {k_1, l_1} } p_2^{\min \set {k_2, l_2} } \ldots p_r^{\min \set {k_r, l_r} }$
:$\lcm \set {m, n} = p_1^{\max \set {k_1, l_1} } p_2^{\max \set {k_2, l_2} } \ldots p_r^{\max \set {k_r, l_r} }$

Proof:
The proof of these results can be found in:
:GCD from Prime Decomposition
:LCM from Prime Decomposition
{{Qed}}
Category:Greatest Common Divisor
Category:Lowest Common Multiple
Category:Prime Numbers
iur6iagonkv1hmri44ycxc6lbtsc4ux
Theorem: GCD and LCM Distribute Over Each Other

Let $a, b, c \in \Z$.
Then:
: $\lcm \set {a, \gcd \set {b, c} } = \gcd \set {\lcm \set {a, b}, \lcm \set {a, c} }$
: $\gcd \set {a, \lcm \set {b, c} } = \lcm \set {\gcd \set {a, b}, \gcd \set {a, c} }$
That is, greatest common divisor and lowest common multiple are distributive over each other.

Proof:
=== LCM Distributive over GCD ===
Let $p_s$ be any of the prime divisors of $a, b$ or $c$, and let $s_a, s_b$ and $s_c$ be its exponent in each of those numbers.
Let $x = \lcm \set {a, \gcd \set {b, c} }$.
Then from GCD and LCM from Prime Decomposition, the exponent of $p_s$ in $x$ is $\max \set {s_a, \min \set {s_b, s_c} }$.
From Max and Min Operations are Distributive over Each Other, $\max$ distributes over $\min$.
Therefore:
: $\max \set {s_a, \min \set {s_b, s_c} } = \min \set {\max \set {s_a, s_b}, \max \set {s_a, s_c} }$
Hence it follows that LCM is distributive over GCD.
{{qed|lemma}}
Theorem: Divisor Count Function from Prime Decomposition

Let $n$ be an integer such that $n \ge 2$.
Let the prime decomposition of $n$ be:
:$n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$
Let $\map {\sigma_0} n$ be the divisor count function of $n$.
Then:
:$\ds \map {\sigma_0} n = \prod_{j \mathop = 1}^r \paren {k_j + 1}$

Proof:
We have:
:$d \divides n \implies \forall i: 1 \le i \le r: d = p_1^{l_1} p_2^{l_2} \ldots p_1^{l_1}, 0 \le l_i \le k_i$
For each $i$, there are $k_i + 1$ choices for $l_i$, making $\paren {k_1 + 1} \paren {k_2 + 1} \cdots \paren {k_r + 1}$ choices in all.
By the Fundamental Theorem of Arithmetic and hence the uniqueness of prime decomposition, each of these choices results in a different number, therefore a distinct divisor.
{{qed}}
Theorem: Divisor Count Function from Prime Decomposition

Let $n$ be an integer such that $n \ge 2$.
Let the prime decomposition of $n$ be:
:$n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$
Let $\map {\sigma_0} n$ be the divisor count function of $n$.
Then:
:$\ds \map {\sigma_0} n = \prod_{j \mathop = 1}^r \paren {k_j + 1}$

Proof:
From Divisor Count Function of Power of Prime we have:
:$\forall j \in \closedint 1 r: \map {\sigma_0} {p_j^{k_j} } = k_j + 1$
The result follows immediately from Divisor Count Function is Multiplicative.
{{qed}}
Theorem: N less than M to the N

:$\forall m, n \in \Z_{>0}: m > 1 \implies n < m^n$

Proof:
{{begin-eqn}}
{{eqn | l = n
      | r = \underbrace {1 + 1 + \cdots + 1}_{\text {$n$ times} }
      | c = 
}}
{{eqn | o = <
      | r = 1 + m + m^2 + \cdots + m^{n - 1}
      | c = as $m > 1$
}}
{{eqn | r = \frac {m^n - 1} {m - 1}
      | c = Sum of Geometric Sequence
}}
{{eqn | o = \le
      | r = m^n - 1
      | c = as $m - 1 \ge 1$
}}
{{eqn | o = <
      | r = m^n
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Basis Representation Theorem

Let $b \in \Z: b > 1$.
For every $n \in \Z_{> 0}$, there exists one and only one sequence $\sequence {r_j}_{0 \mathop \le j \mathop \le t}$ such that:
:$(1): \quad \ds n = \sum_{k \mathop = 0}^t r_k b^k$
:$(2): \quad \ds \forall k \in \closedint 0 t: r_k \in \N_b$
:$(3): \quad r_t \ne 0$
This unique sequence is called the '''representation of $n$ to the base $b$''', or, informally, we can say '''$n$ is (written) in base $b$'''.

Proof:
Let $\map {s_b} n$ be the number of ways of representing $n$ to the base $b$.
We need to show that $\map {s_b} n = 1$ always.
Now, it is possible that some of the $r_k = 0$ in a particular representation.
So we may exclude these terms, and it will not affect the representation.
So, suppose:
:$n = r_k b^k + r_{k - 1} b^{k - 1} + \cdots + r_t b^t$
where $r_k \ne 0, r_t \ne 0$.
Then:
{{begin-eqn}}
{{eqn | l = n - 1
      | r = r_k b^k + r_{k - 1} b^{k - 1} + \cdots + r_t b^t - 1
      | c = 
}}
{{eqn | r = r_k b^k + r_{k - 1} b^{k - 1} + \cdots + \paren {r_t - 1} b^t + b^t - 1
      | c = 
}}
{{eqn | r = r_k b^k + r_{k - 1} b^{k - 1} + \cdots + \paren {r_t - 1} b^t + \sum_{j \mathop = 0}^{t - 1} {\paren {b - 1} b^j}
      | c = Sum of Geometric Sequence
}}
{{end-eqn}}
Note that we have already specified that $b > 1$.
So for each representation of $n$ to the base $b$, we can find a representation of $n - 1$.
If $n$ has another representation to the base $b$, then the same procedure will generate a new representation of $n - 1$.
Thus:
:$(1): \quad \map {s_b} n \le \map {s_b} {n - 1}$
Note that this holds even if $n$ has no representation at all, because if this is the case, then:
:$\map {s_b} n = 0 \le \map {s_b} {n - 1}$
So for $m, n \in \N$ such that $m \ge n$, the inequality $(1)$ implies the following:
:$\forall m, n: \map {s_b} m \le \map {s_b} {m - 1} \le \ldots \le \map {s_b} {n + 1} \le \map {s_b} n$
From N less than M to the N and the fact that $b^n$ has at least one  representation (itself), we see:
:$1 \le \map {s_b} {b^n} \le \map {s_b} n \le \map {s_b} 1$
To determine the value of $\map {s_b} 1$, note that:
:$\forall i \in \Z_{>0}: b^i > 1$
We have that every term of the sum in $(1)$ is non-negative.
So, $r_i = 0$ for every $i > 0$.
The  representation of $1$ must be:
:$1 = r_0 b^0 = r_0$
Thus:
:$\map{s_b} 1 = 1$
Therefore, the entries at either end of the inequality are $1$.
Hence all the intermediate entries must also be $1$.
So:
:$\map {s_b} n = 1$
and the theorem has been proved.
{{qed}}
Theorem: Sum of Geometric Sequence

Let $x$ be an element of one of the standard number fields: $\Q, \R, \C$ such that $x \ne 1$.
Let $n \in \N_{>0}$.
Then:
:$\ds \sum_{j \mathop = 0}^{n - 1} x^j = \frac {x^n - 1} {x - 1}$

Proof:
By the Distributive Property:
:$a + a r + a r^2 + \cdots + a r^{n - 1} = a \paren {1 + r + r^2 + \cdots + r^{n - 1} }$
The result follows from Sum of Geometric Sequence.
{{qed}}