avewright/proofwiki-math huggingface dataset:
Theorem: Unity Function is Completely Multiplicative

Let $f_1: \Z_{> 0} \to \Z_{> 0}$ be the constant function:
:$\forall n \in \Z_{> 0}: f_1 \left({n}\right) = 1$
Then $f_1$ is completely multiplicative.

Proof:
:$\forall m, n \in \Z_{> 0}: f_1 \left({m n}\right) = 1 = f_1 \left({m}\right) f_1 \left({n}\right)$
{{qed}}
Category:Completely Multiplicative Functions
mhowtsfcrt0p94l8q38papewimpdmo0
Theorem: Identity Function is Completely Multiplicative

Let $I_{\Z_{>0}}: \Z_{>0} \to \Z_{>0}$ be the identity function:
:$\forall n \in \Z_{>0}: I_{\Z_{>0}} \left({n}\right) = n$
Then $I_{\Z_{>0}}$ is completely multiplicative.
{{Questionable|Completely multiplicativity is defined for fields but $\Z_{>0}$ is not a field}}

Proof:
:$\forall m, n \in \Z_{>0}: I_{\Z_{>0}} \left({m n}\right) = m n = I_{\Z_{>0}} \left({m}\right) I_{\Z_{>0}} \left({n}\right)$
{{qed}}
Category:Completely Multiplicative Functions
Category:Identity Mappings
6ye9ue17l3wvccd3re221wv600xe3tm
Theorem: Divisor Count Function is Multiplicative

The divisor count function:
:$\ds \tau: \Z_{>0} \to \Z_{>0}: \map {\sigma_0} n = \sum_{d \mathop \divides n} 1$
is multiplicative.

Proof:
Let $f_1: \Z_{>0} \to \Z_{>0}$ be the constant function:
:$\forall n \in \Z_{>0}: \map {f_1} n = 1$
Thus we have:
:$\ds \map {\sigma_0} n = \sum_{d \mathop \divides n} 1 = \sum_{d \mathop \divides n} \map {f_1} d$
But from Unity Function is Completely Multiplicative, $f_1$ is multiplicative.
The result follows from Sum Over Divisors of Multiplicative Function.
{{qed}}
Theorem: Divisor Sum Function is Multiplicative

The divisor sum function:
:$\ds {\sigma_1}: \Z_{>0} \to \Z_{>0}: \map {\sigma_1} n = \sum_{d \mathop \divides n} d$
is multiplicative.

Proof:
Let $I_{\Z_{>0}}: \Z_{>0} \to \Z_{>0}$ be the identity function:
:$\forall n \in \Z_{>0}: \map {I_{\Z_{>0} } } n = n$
Thus we have:
:$\ds \map {\sigma_1} n = \sum_{d \mathop \divides n} d = \sum_{d \mathop \divides n} \map {I_{\Z_{>0} } } d$
But from Identity Function is Completely Multiplicative, $I_{\Z_{>0} }$ is multiplicative.
The result follows from Sum Over Divisors of Multiplicative Function.
{{qed}}
Theorem: Divisor Sum Function is Multiplicative

The divisor sum function:
:$\ds {\sigma_1}: \Z_{>0} \to \Z_{>0}: \map {\sigma_1} n = \sum_{d \mathop \divides n} d$
is multiplicative.

Proof:
Let $a, b$ be coprime integers.
Because $a$ and $b$ have no common divisor, the divisors of $a b$ are integers of the form $a_i b_j$, where $a_i$ is a divisor of $a$ and $b_j$ is a divisor of $b$.
That is, any divisor $d$ of $a b$ is in the form:
:$d = a_i b_j$
in a unique way, where $a_i \divides a$ and $b_j \divides b$.
We can list the divisors of $a$ and $b$ as 
:$1, a_1, a_2, \ldots, a$
and:
:$1, b_1, b_2, \ldots, b$
and so their divisor sums are:
:$\ds \map {\sigma_1} a = \sum_{i \mathop = 1}^r a_i$
:$\ds \map {\sigma_1} b = \sum_{j \mathop = 1}^s b_j$
Consider all divisors of $a b$ with the same $a_i$.
Their sum is:
{{begin-eqn}}
{{eqn | l = \sum_{j \mathop = 1}^s a_i b_j
      | r = a_i \sum_{j \mathop = 1}^s b_j
      | c = 
}}
{{eqn | r = a_i \map {\sigma_1} b
      | c = 
}}
{{end-eqn}}
Summing for all $a_i$:
{{begin-eqn}}
{{eqn | l = \map {\sigma_1} {a b}
      | r = \sum_{i \mathop = 1}^r \paren {a_i \map {\sigma_1} b}
      | c = 
}}
{{eqn | r = \paren {\sum_{i \mathop = 1}^r a_i} \map {\sigma_1} b
      | c = 
}}
{{eqn | r = \map {\sigma_1} a \map {\sigma_1} b
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Primes of form Power of Two plus One

Let $n \in \N$ be a natural number.
Let $2^n + 1$ be prime.
Then $n = 2^k$ for some natural number $k$.

Proof:
Suppose $n$ has an odd divisor apart from $1$.
Then $n$ can be expressed as $n = \paren {2 r + 1} s$.
So:
{{begin-eqn}}
{{eqn | l = 2^n + 1
      | r = 2^{\paren {2 r + 1} s} + 1
      | c = 
}}
{{eqn | r = \paren {2^s}^{\paren {2 r + 1} } + 1^{\paren {2 r + 1} }
      | c = 
}}
{{eqn | r = \paren {2^s + 1} \paren {2^{2 r s} - 2^{\paren {2 r - 1} s} + 2^{\paren {2 r - 2} s} - \cdots - 2^s + 1}
      | c = Sum of Odd Positive Powers
}}
{{end-eqn}}
and so $2^n + 1$ is not prime.
Hence $2^n + 1$ can be prime only if $n$ has only even divisors.
That is, if $n = 2^k$ for some natural number $k$.
{{qed}}
Theorem: Primes of form Power of Two plus One

Let $n \in \N$ be a natural number.
Let $2^n + 1$ be prime.
Then $n = 2^k$ for some natural number $k$.

Proof:
A specific instance of Primes of form Power plus One:
$q^n + 1$ is prime only if:
:$(1): \quad q$ is even
and
:$(2): \quad n$ is of the form $2^k$ for some positive integer $k$.
As $2$ is even, the result applies.
{{qed}}
Theorem: Integer has Multiplicative Order Modulo n iff Coprime to n

Let $a$ and $n$ be integers.
Let the multiplicative order of $a$ modulo $n$ exist.
Then:
:$a \perp n$
that is, $a$ and $n$ are coprime.

Proof:
=== Necessary Condition ===
Suppose $c \in \Z_{>0}$ is the multiplicative order of $a$ modulo $n$.
Then by definition:
:$a^c \equiv 1 \pmod n$
Hence, by definition:
:$a^c = k n + 1$
for some $k \in \Z$.
Thus:
:$a r + n s = 1$
where:
:$r = a^{c - 1}$
:$s = -k$
It follows from Integer Combination of Coprime Integers that $a$ and $n$ are coprime.
{{qed|lemma}}
Theorem: Integer to Power of Multiple of Order

Let $a$ and $n$ be integers.
Let $a \perp n$, that is, let $a$ and $b$ be coprime.
Let $c \in \Z_{>0}$ be the multiplicative order of $a$ modulo $n$.
Then $a^k \equiv 1 \pmod n$ {{iff}} $k$ is a multiple of $c$.

Proof:
First note from Integer has Multiplicative Order Modulo n iff Coprime to n that unless $a \perp n$ the multiplicative order of $a$ modulo $n$ does not exist.
Theorem: Sum of Infinite Geometric Sequence

Let $S$ be a standard number field, that is $\Q$, $\R$ or $\C$.
Let $z \in S$.
Let $\size z < 1$, where $\size z$ denotes:
:the absolute value of $z$, for real and rational $z$
:the complex modulus of $z$ for complex $z$.
Then $\ds \sum_{n \mathop = 0}^\infty z^n$ converges absolutely to $\dfrac 1 {1 - z}$.

Proof:
{{begin-eqn}}
{{eqn | l = \sum_{n \mathop = 1}^\infty z^n
      | r = -z^0 + \sum_{n \mathop = 0}^\infty z^n
      | c =
}}
{{eqn | r = -1 + \frac 1 {1 - z}
      | c = Sum of Infinite Geometric Sequence
}}
{{eqn | r = \frac {z - 1 + 1} {1 - z}
      | c =
}}
{{eqn | r = \frac z {1 - z}
      | c =
}}
{{end-eqn}}
{{qed}}
Theorem: Sum of Infinite Geometric Sequence

Let $S$ be a standard number field, that is $\Q$, $\R$ or $\C$.
Let $z \in S$.
Let $\size z < 1$, where $\size z$ denotes:
:the absolute value of $z$, for real and rational $z$
:the complex modulus of $z$ for complex $z$.
Then $\ds \sum_{n \mathop = 0}^\infty z^n$ converges absolutely to $\dfrac 1 {1 - z}$.

Proof:
{{begin-eqn}}
{{eqn | l = \sum_{n \mathop = 1}^\infty z^n
      | r = \sum_{n \mathop = 1}^\infty z \cdot z^{n - 1}
      | c =
}}
{{eqn | r = z \sum_{n \mathop = 1}^\infty z^{n - 1}
      | c =
}}
{{eqn | r = z \sum_{m \mathop = 0}^\infty z^m
      | c = setting $m = n - 1$
}}
{{eqn | r = z \frac 1 {1 - z}
      | c = Sum of Infinite Geometric Sequence
}}
{{eqn | r = \frac z {1 - z}
      | c =
}}
{{end-eqn}}
{{qed}}
Theorem: Sum of Infinite Geometric Sequence

Let $S$ be a standard number field, that is $\Q$, $\R$ or $\C$.
Let $z \in S$.
Let $\size z < 1$, where $\size z$ denotes:
:the absolute value of $z$, for real and rational $z$
:the complex modulus of $z$ for complex $z$.
Then $\ds \sum_{n \mathop = 0}^\infty z^n$ converges absolutely to $\dfrac 1 {1 - z}$.

Proof:
From Sum of Geometric Sequence, we have:
:$\ds s_N = \sum_{n \mathop = 0}^N z^n = \frac {1 - z^{N + 1} } {1 - z}$
We have that $\size z < 1$.
So by Sequence of Powers of Number less than One:
:$z^{N + 1} \to 0$ as $N \to \infty$
Hence $s_N \to \dfrac 1 {1 - z}$ as $N \to \infty$.
The result follows.
{{qed|lemma}}
It remains to demonstrate absolute convergence:
The absolute value of $\size z$ is just $\size z$.
By assumption:
:$\size z < 1$
So $\size z$ fulfils the same condition for convergence as $z$.
Hence:
:$\ds \sum_{n \mathop = 0}^\infty \size z^n = \frac 1 {1 - \size z}$
{{qed}}
Theorem: Sum of Infinite Geometric Sequence

Let $S$ be a standard number field, that is $\Q$, $\R$ or $\C$.
Let $z \in S$.
Let $\size z < 1$, where $\size z$ denotes:
:the absolute value of $z$, for real and rational $z$
:the complex modulus of $z$ for complex $z$.
Then $\ds \sum_{n \mathop = 0}^\infty z^n$ converges absolutely to $\dfrac 1 {1 - z}$.

Proof:
By the Chain Rule for Derivatives and {{Corollary|Nth Derivative of Reciprocal of Mth Power|disp = $n$th Derivative of Reciprocal of $m$th Power}}:
:$\dfrac {\d^n} {\d z^n} \dfrac 1 {1 - z} = \dfrac {n!} {\paren {1 - z}^{n + 1} }$
Thus the Maclaurin series expansion of $\dfrac 1 {1 - z}$ is:
:$\ds \sum_{n \mathop = 0}^\infty \frac {z^n} {n!} \dfrac {n!} {\paren {1 - 0}^{n + 1} }$
whence the result.
{{qed}}
Theorem: Sum of Infinite Geometric Sequence

Let $S$ be a standard number field, that is $\Q$, $\R$ or $\C$.
Let $z \in S$.
Let $\size z < 1$, where $\size z$ denotes:
:the absolute value of $z$, for real and rational $z$
:the complex modulus of $z$ for complex $z$.
Then $\ds \sum_{n \mathop = 0}^\infty z^n$ converges absolutely to $\dfrac 1 {1 - z}$.

Proof:
Let $S = \ds \sum_{n \mathop = 0}^\infty z^n$.
Then:
{{begin-eqn}}
{{eqn | l = z S
      | r = z \sum_{n \mathop = 0}^\infty z^n
      | c = 
}}
{{eqn | r = \sum_{n \mathop = 0}^\infty z^{n + 1}
      | c = 
}}
{{eqn | r = \sum_{n \mathop = 1}^\infty z^n
      | c = Translation of Index Variable of Summation
}}
{{eqn | r = S - z^0
      | c = 
}}
{{eqn | r = S - 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 1
      | r = \paren {1 - z} S
      | c = 
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Sum of Infinite Geometric Sequence

Let $S$ be a standard number field, that is $\Q$, $\R$ or $\C$.
Let $z \in S$.
Let $\size z < 1$, where $\size z$ denotes:
:the absolute value of $z$, for real and rational $z$
:the complex modulus of $z$ for complex $z$.
Then $\ds \sum_{n \mathop = 0}^\infty z^n$ converges absolutely to $\dfrac 1 {1 - z}$.

Proof:
{{begin-eqn}}
{{eqn | l = \frac 1 {1 - z}
      | r = \frac 1 {1 + \paren {-z} }
      | c = 
}}
{{eqn | r = \sum_{k \mathop = 0}^\infty \paren {-1}^k \paren {-z}^k
      | c = Power Series Expansion for $\dfrac 1 {1 + z}$
}}
{{eqn | r = \sum_{k \mathop = 0}^\infty \paren {-1}^k \paren {-1}^k z^k
      | c = 
}}
{{eqn | r = \sum_{k \mathop = 0}^\infty \paren {-1}^{2 k} z^k
      | c = 
}}
{{eqn | r = \sum_{k \mathop = 0}^\infty z^k
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Square of Riemann Zeta Function

:$\ds \map {\zeta^2} z = \sum_{k \mathop = 1}^\infty \frac {\map {\sigma_0} k} {k^z}$
where:
:$\zeta$ is the Riemann zeta function
:$\sigma_0$ is the divisor count function.

Proof:
{{begin-eqn}}
{{eqn | l = \map {\zeta^2} z
      | r = \paren {\sum_{n \mathop = 1}^\infty \frac 1 {n^z} } \paren {\sum_{n \mathop = 1}^\infty \frac 1 {n^z} }
      | c = 
}}
{{eqn | r = \paren {1 + \frac 1 {2^z} + \frac 1 {3^z} + \frac 1 {4^z} + \frac 1 {5^z} + \frac 1 {6^z} + \cdots} \paren {1 + \frac 1 {2^z} + \frac 1 {3^z} + \frac 1 {4^z} + \frac 1 {5^z} + \frac 1 {6^z} + \cdots} 
      | c = 
}}
{{end-eqn}}
Expanding this product, we get:
{{begin-eqn}}
{{eqn | r = 1 + \frac 1 {2^z} + \frac 1 {3^z} + \frac 1 {4^z} + \frac 1 {5^z} + \frac 1 {6^z} + \cdots
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \frac 1 {2^z} + \frac 1 {4^z} + \frac 1 {6^z} + \frac 1 {8^z} + \frac 1 {10^z} + \frac 1 {12^z} + \cdots
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \frac 1 {3^z} + \frac 1 {6^z} + \frac 1 {9^z} + \frac 1 {12^z} + \frac 1 {15^z} + \frac 1 {18^z} + \cdots
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \frac 1 {4^z} + \frac 1 {8^z} + \frac 1 {12^z} + \frac 1 {16^z} + \frac 1 {20^z} + \frac 1 {24^z} + \cdots
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \frac 1 {5^z} + \frac 1 {10^z} + \frac 1 {15^z} + \frac 1 {20^z} + \frac 1 {25^z} + \frac 1 {30^z} + \cdots
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \frac 1 {6^z} + \frac 1 {12^z} + \frac 1 {18^z} + \frac 1 {24^z} + \frac 1 {30^z} + \frac 1 {36^z} + \cdots
      | c = 
}}
{{eqn | ro= \vdots
      | o = 
      | c = 
}}
{{eqn | r = 1 + \frac 2 {2^z} + \frac 2 {3^z} + \frac 3 {4^z} + \frac 2 {5^z} + \frac 4 {6^z} + \cdots
      | c = 
}}
{{end-eqn}}
We see that each $\dfrac 1 {n^z}$ term in this sum will occur as many times as there are ways represent $n$ as $a b$, counting order.
But this is precisely the number of divisors of $n$, since each way of representing $n = a b$ corresponds to the first term $a$ of the product.
Hence this sum is:
:$\ds \sum_{n \mathop = 1}^\infty \frac {\map {\sigma_0} n} {z^n}$
as desired.
{{qed}}
Category:Riemann Zeta Function
s151nqcncqylz48hnwrxuietmm10fun
Theorem: Derivative of Riemann Zeta Function

The derivative of the Riemann zeta function is:
:$\ds \map {\zeta'} z = \frac {\d \zeta} {\d z} = -\sum_{n \mathop = 2}^\infty \frac {\map \ln n} {n^z}$

Proof:
{{begin-eqn}}
{{eqn | l = \frac {\d \zeta} {\d z}
      | r = \map {\frac \d {\d z} } {\sum_{n \mathop = 1}^\infty n^{-z} }
      | c = {{Defof|Riemann Zeta Function}}
}}
{{eqn | r = \sum_{n \mathop = 1}^\infty \map {\frac \d {\d z} } {n^{-z} }
      | c = Sum Rule for Derivatives/General Result
}}
{{eqn | r = \sum_{n \mathop = 1}^\infty \paren {-\map \ln n n^{-z} }
      | c = Derivative of Exponential Function
}}
{{eqn | r = -\sum_{n \mathop = 1}^\infty \frac {\map \ln n} {n^z}
      | c = Exponent Combination Laws/Negative Power
}}
{{eqn | r = -\sum_{n \mathop = 2}^\infty \frac {\map \ln n} {n^z}
      | c = Natural Logarithm of 1 is 0
}}
{{end-eqn}}
{{qed}}
Theorem: Order of Divisor Count Function

For all $x \ge 1$:
:$\ds \sum_{n \mathop \le x} \map {\sigma_0} n = x \log x + \paren {2 \gamma - 1} x + \map \OO {\sqrt x}$
where:
:$\gamma$ is the Euler-Mascheroni constant
:$\map {\sigma_0} n$ is the divisor count function.

Proof:
{{ProofWanted}}
Category:Number Theory
swpkcthxo9hdv7mpwo3j0q8es7awl5q
Theorem: Order of Möbius Function

Let $\mu$ denote the Möbius function .
Then:
:$\ds \sum_{n \mathop \le N} \map \mu n = \map o N$
where $o$ denotes little-o notation.

Proof:
Let $\map \Re z$ be the real part of a complex variable $z$.
By Dirichlet Series is Analytic, the Riemann zeta function is analytic.
By Trivial Zeroes of Riemann Zeta Function are Even Negative Integers, the Riemann zeta function has no zeroes in $\map \Re z > 1$.
Thus the reciprocal of the Riemann zeta function is analytic in $\map \Re z > 1$.
By Reciprocal of Riemann Zeta Function, this means that $\ds \sum_{n \mathop = 1}^\infty \map \mu n n^{-z}$ converges to an analytic function in $\map \Re z > 1$.
By taking $a_n = \map \mu n$ in Ingham's Theorem on Convergent Dirichlet Series:
:$\ds \sum_{n \mathop = 1}^\infty \frac {\map \mu n} {n^z}$ converges for $\map \Re z \ge 1$.
Taking $z = 1$, we are given a convergent sum:
:$\ds \sum_{n \mathop = 1}^\infty \frac {\map \mu n} n$
Clearly:
:$\ds \sum_{n \mathop = 1}^N \frac {\map \mu n} n \ge \sum_{n \mathop = 1}^N \frac {\map \mu n} N$
{{mistake|$\map \mu n$ can be negative so this isn't obvious, indeed it's not even true}}
but:
:$\ds \lim_{N \mathop \to \infty} \sum_{n \mathop = 1}^N \frac {\map \mu n} n = \lim_{z \mathop \to 1} \frac 1 {\map \zeta z}$
Since Harmonic Series is Divergent, $\dfrac 1 {\map \zeta z}$ goes to $0$ by Reciprocal of Null Sequence.
Hence also:
:$\ds \lim_{N \mathop \to \infty} \sum_{n \mathop = 1}^N \frac {\map \mu n} N = 0$
{{qed}}
Category:Möbius Function
Category:Analytic Number Theory
pgk9oqtka2pe7hey0z4qwdbxrgr22nb
Theorem: Alexander Polynomial is a Knot Invariant

The Alexander polynomial of an elementary knot $K$ is invariant under Reidemeister moves.

Proof:
{{ProofWanted}}
Category:Knot Theory
cfk3l9xnijecc9vcqsutu3c1dsb9y4m
Theorem: Power Function is Completely Multiplicative

Let $K$ be a field.
Let $z \in K$.
Let $f_z: K \to K$ be the mapping defined as:
:$\forall x \in K: \map {f_z} x = x^z$
Then $f_z$ is completely multiplicative.

Proof:
Let $r, s \in K$.
Then:
{{begin-eqn}}
{{eqn | l = \map {f_z} {r s}
      | r = \paren {r s}^z
      | c = Definition of $f_z$
}}
{{eqn | r = \paren r^z \paren s^z
      | c = Power of Product in Abelian Group
}}
{{eqn | r = \map {f_z} r \map {f_z} s
      | c = Definition of $f_z$
}}
{{end-eqn}}
{{Qed}}
Category:Field Theory
Category:Completely Multiplicative Functions
mgncxgh8ryx05ehwtz20lnt2btj6pmj
Theorem: Euler Phi Function of Product with Prime

Let $p$ be prime and $n \in \Z: n \ge 1$.
Then:
:$\map \phi {p n} = \begin{cases} \paren {p - 1} \map \phi n & : p \nmid n \\ p \map \phi n & : p \divides n \end{cases}$
where:
:$\map \phi n$ denotes the Euler $\phi$ function of $n$
:$\divides$ denotes divisibility.
Thus for all $n \ge 1$ and for any prime $p$, we have that $\map \phi n$ divides $\map \phi {p n}$.

Proof:
First suppose that $p \nmid n$.
Then by Prime not Divisor implies Coprime, $p \perp n$.
So by Euler Phi Function is Multiplicative, $\map \phi {p n} = \map \phi p \map \phi n$.
It follows from Euler Phi Function of Prime that $\map \phi {p n} = \paren {p - 1} \map \phi n$.
Now suppose that $p \divides n$.
Then $n = p^k m$ for some $k, m \in \Z: k, m \ge 1$ such that $p \perp m$.
Then:
{{begin-eqn}}
{{eqn | l = \map \phi {p n}
      | r = \map \phi {p^{k + 1} m}
      | c = 
}}
{{eqn | r = \map \phi {p^{k + 1} } \map \phi m
      | c = Euler Phi Function is Multiplicative
}}
{{eqn | r = p^{k + 1} \paren {1 - \frac 1 p} \map \phi m
      | c = Euler Phi Function of Prime Power
}}
{{end-eqn}}
At the same time:
{{begin-eqn}}
{{eqn | l = p \map \phi n
      | r = p \map \phi {p^k m}
      | c = 
}}
{{eqn | r = p \map \phi {p^k} \map \phi m
      | c = Euler Phi Function is Multiplicative
}}
{{eqn | r = p p^k \paren {1 - \frac 1 p} \map \phi m
      | c = Euler Phi Function of Prime Power
}}
{{eqn | r = p^{k + 1} \paren {1 - \frac 1 p} \map \phi m
      | c = 
}}
{{end-eqn}}
{{qed}}
Category:Euler Phi Function
88bxoy0easnh1dp5r1ybxjm5t1kkhfn
Theorem: Euler Phi Function is Even for Argument greater than 2

Let $n \in \Z: n \ge 1$.
Let $\map \phi n$ be the Euler $\phi$ function of $n$.
Then $\map \phi n$ is even {{iff}} $n > 2$.

Proof:
We have:
{{begin-eqn}}
{{eqn | l = \map \phi 1
      | r = 1
      | c = {{EulerPhiLink|1}}
}}
{{eqn | l = \map \phi 2
      | r = 1
      | c = {{EulerPhiLink|2}}
}}
{{end-eqn}}
Now let $n \ge 3$.
There are two possibilities:
Theorem: Divisor Sum of Integer

Let $n$ be an integer such that $n \ge 2$.
Let $\map {\sigma_1} n$ be the divisor sum of $n$.
That is, let $\map {\sigma_1} n$ be the sum of all positive divisors of $n$.
Let the prime decomposition of $n$ be:
:$\ds n = \prod_{1 \mathop \le i \mathop \le r} p_i^{k_i} =  p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$
Then:
:$\ds \map {\sigma_1} n = \prod_{1 \mathop \le i \mathop \le r} \frac {p_i^{k_i + 1} - 1} {p_i - 1}$

Proof:
We have that the Divisor Sum Function is Multiplicative.
From Value of Multiplicative Function is Product of Values of Prime Power Factors, we have:
:$\map f n = \map f {p_1^{k_1} } \map f {p_2^{k_2} } \ldots \map f {p_r^{k_r} }$
From Divisor Sum of Power of Prime, we have:
:$\ds \map {\sigma_1} {p_i^{k_i} } = \frac {p_i^{k_i + 1} - 1} {p_i - 1}$
Hence the result.
{{qed}}
Theorem: Product of Divisor Sum and Euler Phi Functions

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} \ldots p_r^{k_r}$
Let $\map {\sigma_1} n$ be the divisor sum function of $n$.
Let $\map \phi n$ be the Euler phi function of $n$.
Then:
:$\ds \map {\sigma_1} n \map \phi n = n^2 \prod_{1 \mathop \le i \mathop \le r} \paren {1 - \frac 1 {p_i^{k_i + 1} } }$

Proof:
{{improve|Better to start with $\ds \map \phi n {{=}} n \prod_{p \mathop \divides n} \paren {1 - \frac 1 p}$ and then a lot of the gnarliness goes away}}
From Euler Phi Function of Integer:
:$\ds \map \phi n = \prod_{1 \mathop \le i \mathop \le r} p_i^{k_i - 1} \paren {p_i - 1}$
From Divisor Sum of Integer:
:$\ds \map {\sigma_1} n = \prod_{1 \mathop \le i \mathop \le r} \frac {p_i^{k_i + 1} - 1} {p_i - 1}$
So:
:$\ds \map {\sigma_1} n \map \phi n = \prod_{1 \mathop \le i \mathop \le r} \paren {\frac {p_i^{k_i + 1} - 1} {p_i - 1} } p_i^{k_i - 1} \paren {p_i - 1}$
Taking a general factor of this product:
{{begin-eqn}}
{{eqn | l = \paren {\frac {p_i^{k_i + 1} - 1} {p_i - 1} } p_i^{k_i - 1} \paren {p_i - 1}
      | r = \paren {p_i^{k_i + 1} - 1} p_i^{k_i - 1}
      | c = cancelling $p_i - 1$ top and bottom
}}
{{eqn | r = p_i^{2 k_i} - p_i^{k_i - 1}
      | c = multiplying out the bracket
}}
{{eqn | r = p_i^{2 k_i} \paren {1 - \frac 1 {p_i^{k_i + 1} } }
      | c = extracting $p_i^{2 k_i}$ as a factor
}}
{{end-eqn}}
So:
:$\ds \map {\sigma_1} n \map \phi n = \prod_{1 \mathop \le i \mathop \le r} p_i^{2 k_i} \paren {1 - \frac 1 {p_i^{k_i + 1} } }$
Hence:
:$\ds \prod_{1 \mathop \le i \mathop \le r} p_i^{2 k_i} = \paren {\prod_{1 \mathop \le i \mathop \le r} p_i^{k_i} }^2 = n^2$
and the result follows.
{{qed}}
Category:Divisor Sum Function
Category:Euler Phi Function
134kh4o4yzg1n8srebu36p3yu1fcvjj
Theorem: Primitive Root is Generator of Reduced Residue System

Let $a$ be a primitive root of $n$.
Then:
:$\set {a, a^2, a^3, \ldots, a^{\map \phi n} }$
where $\map \phi n$ is the Euler phi function of $n$, is the reduced residue system of $n$.
Thus the first $\map \phi n$ powers of $a$ "generates" the reduced residue system of $n$.
We say that $a$ is a '''generator''' of the reduced residue system of $n$.

Proof:
Let $R = \set {a, a^2, a^3, \ldots, a^{\map \phi n} }$.
Each element of $R$ is coprime to $n$ as $a \perp n$.
Suppose $a^r \equiv a^s \pmod n$ where $1 \le r \le s \le \map \phi n$.
Then $a^{r - s} \equiv 1 \pmod n$.
From the definition of primitive root, the multiplicative order of $a$ modulo $n$ is $\map \phi n$.
So from Integer to Power of Multiple of Order $\map \phi n$ divides $r - s$ and so $r = s$.
So no two elements are congruent modulo $n$.
So as $R$ contains $\map \phi n$ integers none of which are congruent modulo $n$ to any of the others, $R$ is a reduced residue system of $n$.
{{qed}}
Category:Number Theory
2i49gxwzm9orc3dwk6zhygzt8ms0ck7
Theorem: Order Modulo n of Power of Integer

Let $a$ have multiplicative order $c$ modulo $n$.
Then for any $k \ge 1$, $a^k$ has multiplicative order $\dfrac c {\gcd \set {c, k}}$ modulo $n$.

Proof:
Let $a$ have multiplicative order $c$ modulo $n$.
Consider $a^k$ and let $d = \gcd \set {c, k}$.
Let $c = d c'$ and $k = d k'$ where $\gcd \set {c', k'} = 1$ from Integers Divided by GCD are Coprime.
We want to show that the multiplicative order $a^k$ modulo $n$ is $c'$.
Let the order $a^k$ modulo $n$ be $r$.
Then:
{{begin-eqn}}
{{eqn | l = \paren {a^k}^{c'}
      | r = \paren {a^{d k'} }^{c/d}
      | c = 
}}
{{eqn | r = a^{k' c}
      | c = 
}}
{{eqn | r = \paren {a^c}^{k'}
      | c = 
}}
{{eqn | o = \equiv
      | r = \paren 1^{k'}
      | rr= \pmod n
      | c = 
}}
{{eqn | o = \equiv
      | r = 1
      | rr= \pmod n
      | c = 
}}
{{end-eqn}}
So, by Integer to Power of Multiple of Order, $c'$ is a multiple of $r$, that is, $r \divides c'$.
On the other hand, $a^{k r} = \paren {a^k}^r \equiv 1 \pmod n$, and so $k r$ is a multiple of $c$.
Substituting for $k$ and $c$, we see that $d k' r$ is a multiple of $d c'$ which shows $c'$ divides $k' r$.
But from Euclid's Lemma (which applies because $\gcd \set {c', k'} = 1$), we have that $c'$ divides $r$, or $c' \divides r$.
So, as $c' \divides r$ and $r \divides c'$, from Divisor Relation on Positive Integers is Partial Ordering, it follows that $c' = r$.
{{qed}}
Category:Number Theory
i86kpykhhvvv74r92vzvwtus4qmcmiw