avewright/proofwiki-math huggingface dataset:
Theorem: Forward Difference of Falling Factorial

Let $f: \R \to \R$ be a real function.
Let $\Delta$ denote the forward difference operator.
Let $x^{\underline m}$ be the $m$th falling factorial of $x$
Then:
:$\map \Delta {x^{\underline m} } = m x^{\underline {m - 1} }$

Proof:
From the definitions:
{{begin-eqn}}
{{eqn | l = \map \Delta {x^{\underline m} }
      | r = \paren {x + 1}^{\underline m} - x^{\underline m}
      | c = {{Defof|Forward Difference Operator}}
}}
{{eqn | r = \prod_{k \mathop = 0}^{m - 1} \paren {x + 1 - k} - \prod_{k \mathop = 0}^{m - 1} \paren {x - k}
      | c = {{Defof|Falling Factorial|$m$th Falling Factorial}}
}}
{{eqn | r = \paren {x + 1} \prod_{k \mathop = 1}^{m - 1} \paren {x + 1 - k} - \paren {x - m + 1} \prod_{k \mathop = 0}^{m - 2} \paren {x - k}
      | c = 
}}
{{eqn | r = \paren {x + 1} \prod_{k \mathop = 0}^{m - 2} \paren {x - k} - \paren {x - m + 1} \prod_{k \mathop = 0}^{m - 2} \paren {x - k}
      | c = Translation of Index Variable of Product
}}
{{eqn | r = \paren {\paren {x + 1} - \paren {x - m + 1} } \prod_{k \mathop = 0}^{m - 2} \paren {x - k}
      | c = 
}}
{{eqn | r = m x^{\underline{m - 1} }
      | c = {{Defof|Falling Factorial|$m$th Falling Factorial}}
}}
{{end-eqn}}
{{qed}}
Category:Finite Calculus
f61fprcnzkv94xizg5sqgl1273y41vr
Theorem: Chen's Theorem

Every sufficiently large even integer is the sum of either:
:$(1): \quad$ two primes, or 
:$(2): \quad$ a prime and a semiprime.

Proof:
{{ProofWanted}}
{{Namedfor|Chen Jingrun|cat = Chen}}
Theorem: Binomial Coefficient involving Prime

Let $p$ be a prime number.
Let $\dbinom n p$ be a binomial coefficient.
Then:
:$\dbinom n p \equiv \floor {\dfrac n p} \pmod p$
where:
:$\floor {\dfrac n p}$
denotes the floor function.

Proof:
Follows directly from Lucas' Theorem:
:$\dbinom n k \equiv \dbinom {\floor {n / p} } {\floor {k / p} } \dbinom {n \bmod p} {k \bmod p} \pmod p$
where $k = p$.
Then:
:$k \bmod p = 0$
and so by Binomial Coefficient with Zero:
:$\dbinom {n \bmod p} {k \bmod p} = 1$
Also:
:$\floor {k / p} = 1$
and by Binomial Coefficient with One:
:$\dbinom {\floor {n / p} } {\floor {k / p} } = \floor {\dfrac n p}$
Thus:
:$\dbinom n p \equiv \floor {\dfrac n p} \times 1 \pmod p$
Hence the result.
{{qed}}
Theorem: Binomial Coefficient of Prime Minus One Modulo Prime

Let $p$ be a prime number.
Then:
:$0 \le k \le p - 1 \implies \dbinom {p - 1} k \equiv \left({-1}\right)^k \pmod p$
where $\dbinom {p - 1} k$ denotes a binomial coefficient.

Proof:
From Binomial Coefficient of Prime, we have:
:$\dbinom p k \equiv 0 \pmod p$
when $1 \le k \le p - 1$.
From Pascal's Rule:
:$\dbinom {p-1} k + \dbinom {p - 1} {k - 1} = \dbinom p k \equiv 0 \pmod p$
This certainly holds for $k = 1$, and so we have:
:$\dbinom {p - 1} 1 + \dbinom {p - 1} 0 = \dbinom p 1 \equiv 0 \pmod p$
But from Binomial Coefficient with Zero:
:$\dbinom {p - 1} 0 = 1 \equiv 1 \pmod p$
So:
:$\dbinom {p - 1} 1 \equiv -1 \pmod p$
Then:
:$\dbinom {p - 1} 2 + \dbinom {p - 1} 1 = \dbinom p 2 \equiv 0 \pmod p$
and so:
:$\dbinom {p - 1} 2 \equiv 1 \pmod p$
The result follows.
{{qed}}
Theorem: Binomial Coefficient of Prime Plus One Modulo Prime

Let $p$ be a prime number.
Then:
:$2 \le k \le p - 1 \implies \dbinom {p + 1} k \equiv 0 \pmod p$
where $\dbinom {p + 1} k$ denotes a binomial coefficient.

Proof:
From Binomial Coefficient of Prime, we have:
:$\dbinom p k \equiv 0 \pmod p$
when $1 \le k \le p - 1$.
From Pascal's Rule:
:$\dbinom {p + 1} k = \dbinom p {k - 1} + \dbinom p k$
The result follows immediately.
{{qed}}
Theorem: Set of Prime Numbers is Infinite

The number of primes is infinite.

Proof:
{{AimForCont}} there exists a greatest prime number $N$.
Hence, let $S$ denote the finite set of all prime numbers.
Euclid's Theorem states that:
:For any finite set of prime numbers, there exists a prime number not in that set.
Hence there exists $N'$ not in $S$.
If $N' < N$ then $N \in S$.
Hence:
:$N' > N$
which contradicts the assumption the $N$ is the greatest prime number.
The result follows by Proof by Contradiction.
{{qed}}
Theorem: Set of Prime Numbers is Infinite

The number of primes is infinite.

Proof:
Define a topology on the integers $\Z$ by declaring a subset $U \subseteq \Z$ to be an open set {{iff}} it is either:
:the empty set $\O$
or:
:a union of sequences $\map S {a, b}$ such that $a \ne 0$, where:
::$\map S {a, b} = \set {a n + b: n \in \Z} = a \Z + b$
In other words, $U$ is open {{iff}} every $x \in U$ admits some non-zero integer $a$ such that $\map S {a, x} \subseteq U$.
The open set axioms are verified as follows:
;{{Open-set-axiom|1|nolink}}: All unions of open sets are open:
For any set of open sets $U_i$ and $x$ in their union $U$, any of the numbers $a_i$ for which $\map S {a_i, x} \subseteq U_i$ also shows that $\map S {a_i, x} \subseteq U$.
;{{Open-set-axiom|2|nolink}}: The intersection of two (and hence finitely many) open sets is open:
Let $U_1$ and $U_2$ be open sets.
Let $x \in U_1 \cap U_2$ (with integers $a_1$ and $a_2$ establishing membership).
Set $a$ to be the lowest common multiple of $a_1$ and $a_2$.
Then:
:$\map S {a, x} \subseteq \map S {a_i, x} \subseteq U_1 \cap U_2$
;{{Open-set-axiom|3|nolink}}: By definition, $\O$ is open: $\Z$ is just the sequence $\map S {1, 0}$, and so is open as well.
The topology is quite different from the usual Euclidean one, and has two notable properties:
:$(1): \quad$ Since any non-empty open set contains an infinite sequence, no finite set can be open. Put another way, the complement of a finite set cannot be a closed set.
:$(2): \quad$ The basis sets $\map S {a, b}$ are both open and closed: they are open by definition, and we can write $\map S {a, b}$ as the complement of an open set as follows:
:$\ds \map S {a, b} = \Z \setminus \bigcup_{j \mathop = 1}^{a - 1} \map S {a, b + j}$
The only integers that are not integer multiples of prime numbers are $-1$ and $+1$, that is:
:$\ds \Z \setminus \set {-1, +1} = \bigcup_{\text {$p$ prime} } \map S {p, 0}$
By the first property, the set on the {{LHS}} cannot be closed.
On the other hand, by the second property, the sets $\map S {p, 0}$ are closed.
So, if there were only finitely many prime numbers, then the set on the {{RHS}} would be a finite union of closed sets, and hence closed.
Therefore by Proof by Contradiction, there must be infinitely many prime numbers.
{{qed}}
Theorem: Set of Prime Numbers is Infinite

The number of primes is infinite.

Proof:
{{AimForCont}} that there are only $N$ prime numbers.
Let the set of all primes be:
:$\Bbb P = \set {p_1, p_2, \ldots, p_N}$
By the Fundamental Theorem of Arithmetic, every integer $k > 1$ can be expressed in the form:
:$k = {p_1}^{a_1} {p_2}^{a_2} \dotsm {p_N}^{a_N}$
Let $n > 1$ be fixed.
Let $a$ be the largest exponent occurring in the prime decomposition of all positive integers $k \le n$.
Then:
:$\ds \sum_{k \mathop = 1}^n \frac 1 k \le \prod_{j \mathop = 1}^N \paren {\sum_{k \mathop = 0}^a \frac 1 { {p_j}^k} }$
is expressible in the form:
{{begin-eqn}}
{{eqn | n = 1
      | l = 1 + \frac 1 2 + \frac 1 3 + \dotsb + \frac 1 n
      | o = \le
      | r = \paren {1 + \frac 1 {p_1} + \frac 1 { {p_1}^2} + \dotsb + \frac 1 { {p_1}^a} }
      | c = 
}}
{{eqn | o =
      | ro= \times
      | r = \paren {1 + \frac 1 {p_2} + \frac 1 { {p_2}^2} + \dotsb + \frac 1 { {p_2}^a} }
      | c = 
}}
{{eqn | o =
      | ro= \times
      | r = \ \dotsb
      | c = 
}}
{{eqn | o =
      | ro= \times
      | r = \paren {1 + \frac 1 {p_N} + \frac 1 { {p_N}^2} + \dotsb + \frac 1 { {p_N}^a} }
      | c = 
}}
{{end-eqn}}
which can be seen by multiplying out the factors on the {{RHS}}.
But from Sum of Infinite Geometric Sequence:
:$1 + x + x^2 + \dotsb = \dfrac 1 {1 - x}$
for all $x$ such that $\size x < 1$.
Thus the factors in $(1)$ are less than the numbers:
:$\dfrac 1 {1 - 1 / p_1}, \dfrac 1 {1 - 1 / p_2}, \dotsb, \dfrac 1 {1 - 1 / p_N}$
and so:
:$1 + \dfrac 1 2 + \dfrac 1 3 + \dotsb + \dfrac 1 n < \dfrac {p_1} {p_1 - 1} \dfrac {p_2} {p_2 - 1} \dotsm \dfrac {p_N} {p_N - 1}$
We have chosen $n > 1$ arbitrarily, so this holds for every $n > 1$.
This contradicts the result Harmonic Series is Divergent.
Hence the result, by Proof by Contradiction.
{{qed}}
Theorem: Set of Prime Numbers is Infinite

The number of primes is infinite.

Proof:
{{AimForCont}} there exist only a finite number of primes.
From Sum of Reciprocals of Powers as Euler Product:
:$\ds \sum_{n \mathop \ge 1} \dfrac 1 {n^z} = \prod_p \frac 1 {1 - p^{-z} }$
When $z = 1$ this gives:
:$\ds \sum_{n \mathop \ge 1} \dfrac 1 n = \prod_p \frac 1 {1 - 1 / p}$
{{mistake|You cannot choose $z{{=}}1$ because Sum of Reciprocals of Powers as Euler Product requires $\map \Re z > 1$.}}
As {{hypothesis}} there exist only a finite number of primes, the {{RHS}} is also finite.
But from Harmonic Series is Divergent, the {{LHS}} diverges to infinity.
The result follows by Proof by Contradiction.
{{qed}}
Theorem: Set of Prime Numbers is Infinite

The number of primes is infinite.

Proof:
{{AimForCont}} there exist $n$ prime numbers.
Consider the Fermat number $F_n$.
From Goldbach's Theorem, $F_n$ is coprime to each of $F_0$ to $F_{n - 1}$.
Therefore there must be a prime number which is a divisor of $F_n$ which is not a divisor of any of $F_0$ to $F_n$.
But, again from Goldbach's Theorem, each of $F_0$ to $F_{n - 1}$ is coprime to every other Fermat number.
So all the $n$ prime numbers must have been exhausted being used as prime factors of $F_0$ to $F_{n - 1}$.
So there must be more prime numbers than $n$.
The result follows by Proof by Contradiction.
{{qed}}
Theorem: Set of Prime Numbers is Infinite

The number of primes is infinite.

Proof:
Let $p_1, p_2, \ldots, p_j$ be the first $j$ primes.
For each real $x$ and natural number $j$, let:
:$\map {M_j} x = \set {n \in \N \mid n \le x, \, n \text { is not divisible by any prime } p \text { with } p > p_j}$
Define:
:$\map {N_j} x = \# \map {M_j} x$
Let $n \in \map {M_j} x$ for some $x$, $j$. 
We can write: 
:$n = n_*^2 m$
where $n_*$ and $m$ are integers with $m$ square-free.
By the Fundamental Theorem of Arithmetic, we may uniquely write: 
:$\ds m = \prod_{i \mathop = 1}^j p_j^{e_j}$
where $e_j \in \set {0, 1}$.
Since there are $2$ choices for each $e_j$, there are $2^j$ possible values of $m$.
Note that since $m \ge 1$, we have: 
:$n_*^2 \le n \le x$
so:
:$n_* \le \sqrt n \le \sqrt x$
So, there at most $\sqrt x$ possible values of $n_*$. 
So, there are at most $2^j \sqrt x$ possible values of $n$.
That is:
:$\map {N_j} x \le 2^j \sqrt x$
{{AimForCont}} that there are only finitely many primes.
In particular, assume that there are $k$ primes. 
Then:
:$\map {N_k} x = x$
for each $x$, since there are no primes exceeding $p_k$. 
So, we have: 
:$x \le 2^k \sqrt x$
for all $x$. 
But this does not hold for all $x$, for example taking $x = 2^{2 k} + 1$. 
So, we have arrived at a contradiction.
So there are infinitely many primes.
{{qed}}
Theorem: Factorial Divisible by Binary Root

Let $n \in \Z: n \ge 1$.
Let $n$ be expressed in binary notation:
:$n = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_r}$
where $e_1 > e_2 > \cdots > e_r \ge 0$.
Let $n!$ be the factorial of $n$.
Then $n!$ is divisible by $2^{n - r}$, but not by $2^{n - r + 1}$.

Proof:
A direct application of Factorial Divisible by Prime Power.
{{qed}}
Category:Factorials
Category:Binary Notation
lhbklcp3l1qd7gzyj76tln0qu2wmrl6
Theorem: Quotient and Remainder to Number Base

Let $n \in \Z: n > 0$ be an integer.
Let $n$ be expressed in base $b$:
:$\ds n = \sum_{j \mathop = 0}^m {r_j b^j}$
that is:
:$n = \sqbrk {r_m r_{m - 1} \ldots r_2 r_1 r_0}_b$
Then:
:$\ds \floor {\frac n b} = \sqbrk {r_m r_{m - 1} \ldots r_2 r_1}_b$
:$n \bmod b = r_0$
where:
:$\floor {\, \cdot \,}$ denotes the floor function;
:$n \bmod b$ denotes the modulo operation.

Proof:
From the Quotient-Remainder Theorem, we have:
:$\exists q, r \in \Z: n = q b + r$
where $0 \le b < r$.
We have that:
{{begin-eqn}}
{{eqn | l = n
      | r = \sum_{j \mathop = 0}^m {r_j b^j}
      | c = 
}}
{{eqn | r = \sum_{j \mathop = 1}^m {r_j b^j} + r_0
      | c = 
}}
{{eqn | r = b \sum_{j \mathop = 1}^m {r_j b^{j-1} } + r_0
      | c = 
}}
{{end-eqn}}
Hence we can express $n = q b + r$ where:
:$\ds q = \sum_{j \mathop = 1}^m {r_j b^{j - 1} }$
:$r = r_0$
where:
:$\ds \sum_{j \mathop = 1}^m {r_j b^{j - 1} } = \sqbrk {r_m r_{m - 1} \ldots r_2 r_1}_b$
The result follows from the definition of the modulo operation.
{{qed}}
Theorem: Factorial Divisible by Prime Power

Let $n \in \Z: n \ge 1$.
Let $p$ be a prime number.
Let $n$ be expressed in base $p$ notation:
:$\ds n = \sum_{j \mathop = 0}^m r_j p^j$
where $0 \le r_j < p$.
Let $n!$ be the factorial of $n$.
Let $p^\mu$ be the largest power of $p$ which divides $n!$, that is:
:$p^\mu \divides n!$
:$p^{\mu + 1} \nmid n!$
Then:
:$\mu = \dfrac {n - \map {s_p} n} {p - 1}$
where $\map {s_p} n$ is the digit sum of $n$ to base $p$.

Proof:
If $p > n$, then $\map {s_p} n = n$ and we have that:
:$\dfrac {n - \map {s_p} n} {p - 1} = 0$
which ties in with the fact that $\floor {\dfrac n p} = 0$.
Hence the result holds for $p > n$.
So, let $p \le n$.
From De Polignac's Formula, we have that:
{{begin-eqn}}
{{eqn | l = \mu
      | r = \sum_{k \mathop > 0} \floor {\frac n {p^k} }
      | c = 
}}
{{eqn | r = \floor {\frac n p} + \floor {\frac n {p^2} } + \floor {\frac n {p^3} } + \cdots + \floor {\frac n {p^s} }
      | c = 
}}
{{end-eqn}}
where $p^s < n < p^{s + 1}$.
From Quotient and Remainder to Number Base: General Result:
:$\ds \floor {\frac n {p^k} } = \sqbrk {r_m r_{m - 1} \ldots r_{k + 1} r_k}_p = \sum_{j \mathop = 0}^{m - k} r_j p^j$
where $0 \le r_j < p$.
Hence:
{{begin-eqn}}
{{eqn | l = \mu
      | r = \sum_{k \mathop > 0} \paren {\sum_{j \mathop = 0}^{m - k} r_j p^j}
      | c = 
}}
{{eqn | r = r_m p^{m - 1} + r_{m - 1} p^{m - 2} + \cdots + r_2 p + r_1
      | c = 
}}
{{eqn | o = +
      | r = r_m p^{m - 2} + r_{m - 1} p^{m - 3} + \cdots + r_2
      | c = 
}}
{{eqn | o = +
      | r = \cdots
      | c = 
}}
{{eqn | o = +
      | r = r_m p + r_{m - 1}
      | c = 
}}
{{eqn | o = +
      | r = r_m
      | c = 
}}
{{eqn | r = r_m \sum_{j \mathop = 0}^{m - 1} p^j + r_{m - 1} \sum_{j \mathop = 0}^{m - 2} p^j + \cdots + r_2 \sum_{j \mathop = 0}^1 p^j + r_1 \sum_{j \mathop = 0}^0 p^j
      | c = 
}}
{{eqn | r = \sum_{k \mathop = 1}^m \paren {r_k \sum_{j \mathop = 0}^{k - 1} p^j}
      | c = 
}}
{{eqn | r = \sum_{k \mathop = 1}^m \paren {r_k \frac {p^k - 1} {p - 1} }
      | c = from Sum of Geometric Sequence
}}
{{eqn | r = \frac 1 {p - 1} \paren {\sum_{k \mathop = 1}^m r_k p^k - \sum_{k \mathop = 1}^m r_k}
      | c = 
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Wilson's Theorem/Corollary 2

Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Let $p$ be a prime factor of $n!$ with multiplicity $\mu$.
Let $n$ be expressed in a base $p$ representation as:
{{begin-eqn}}
{{eqn | l = n
      | r = \sum_{j \mathop = 0}^m a_j p^j
      | c = where $0 \le a_j < p$
}}
{{eqn | r = a_0 + a_1 p + a_2 p^2 + \cdots + a_m p^m
      | c = for some $m > 0$
}}
{{end-eqn}}
Then:
:$\dfrac {n!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dotsb a_m! \pmod p$

Proof:
Proof by induction:
Let $\map P n$ be the proposition:
:$\dfrac {n!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dotsm a_k! \pmod p$
where $p, a_0, \dots, a_k, \mu$ are as defined above.
=== Basis for the Induction ===
For $n = 1$:
:$a_0 = 1, \mu = 0$
$\map P 1$ reduces to:
:$\dfrac {1!} {p^0} \equiv \paren {-1}^0 1! \pmod p$
which holds trivially.
This is the basis for the induction.
=== Induction Hypothesis ===
This is our induction hypothesis:
:$\dfrac {r!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dots a_k! \pmod p$
Now we need to show true for $n = r + 1$:
:$\dfrac {\paren {r + 1}!} {p^{\mu'}} \equiv \paren {-1}^{\mu'} b_0! b_1! \dots b_k! \pmod p$
where $\ds r + 1 = \sum_{j \mathop = 0}^k b_j p^j$ is the base $p$ presentation of $r + 1$, and:
:$p^{\mu'} \divides \paren {r + 1}!$
:$p^{\mu' + 1} \nmid \paren {r + 1}!$
=== Induction Step ===
This is our induction step:
Let $p^m$ be the largest power of $p$ which divides $r + 1$, that is:
:$p^m \divides r + 1$
:$p^{m + 1} \nmid r + 1$
Then we must have:
:$b_m \ne 0$
:$b_j = 0$ for $0 \le j < m$
:$\mu' = \mu + m$
and consequently:
:$a_j = b_j$ for $j > m$
:$a_m + 1 = b_m$
:$a_j = p - 1$ for $0 \le j < m$
Thus:
{{begin-eqn}}
{{eqn | l = \frac {\paren {r + 1}!} {p^{\mu'} }
      | r = \frac {r!} {p^\mu} \times \frac {r + 1} {p^m}
}}
{{eqn | o = \equiv
      | r = \paren {-1}^\mu a_0! \dots a_{m - 1}! a_m! \dots a_k! \times \frac {r + 1} {p^m}
      | rr= \pmod p
      | c = Induction Hypothesis
}}
{{eqn | o = \equiv
      | r = \paren {-1}^\mu \paren {\paren {p - 1}!}^m \paren {b_m - 1}! b_{m + 1}! \dots b_k! \times \frac 1 {p^m} \sum_{j \mathop = m}^k b_j p^j
      | rr= \pmod p
      | c = from above
}}
{{eqn | o = \equiv
      | r = \paren {-1}^\mu \paren {-1}^m \paren {b_m - 1}! b_{m + 1}! \dots b_k! \times \sum_{j \mathop = m}^k b_j p^{j - m}
      | rr= \pmod p
      | c = Wilson's Theorem
}}
{{eqn | o = \equiv
      | r = \paren {-1}^{\mu'} \paren {b_m - 1}! b_{m + 1}! \dots b_k! b_m
      | rr= \pmod p
      | c = because $b_j p^{j - m} \equiv 0 \pmod p$ for $j - m > 0$
}}
{{eqn | o = \equiv
      | r = \paren {-1}^{\mu'} b_m! b_{m + 1}! \dots b_k!
      | rr= \pmod p
      | c = {{Defof|Factorial}}
}}
{{eqn | o = \equiv
      | r = \paren {-1}^{\mu'} b_0! \dots b_k!
      | rr= \pmod p
      | c = Factorial of Zero: $b_j = 0$ for $0 \le j < m$
}}
{{end-eqn}}
By the Principle of Mathematical Induction, $\map P n$ is true for all $n \in \Z_{>0}$.
{{qed}}
Theorem: Wilson's Theorem/Corollary 2

Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Let $p$ be a prime factor of $n!$ with multiplicity $\mu$.
Let $n$ be expressed in a base $p$ representation as:
{{begin-eqn}}
{{eqn | l = n
      | r = \sum_{j \mathop = 0}^m a_j p^j
      | c = where $0 \le a_j < p$
}}
{{eqn | r = a_0 + a_1 p + a_2 p^2 + \cdots + a_m p^m
      | c = for some $m > 0$
}}
{{end-eqn}}
Then:
:$\dfrac {n!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dotsb a_m! \pmod p$

Proof:
Consider the numbers of $\set {1, 2, \ldots, n}$ which are not multiples of $p$.
There are $\floor {\dfrac n p}$ complete sets of $p - 1$ such consecutive elements of $\set {1, 2, \ldots, n}$.
Each one of these has a product which is congruent to $-1 \pmod p$ by Wilson's Theorem.
There are also $a_0$ left over which are congruent to $a_0! \pmod p$.
Thus:
:the contributions of the divisors which are not multiples of $p$ is $\paren {-1}^{\floor {n / p} } a_0!$
:the contributions of the divisors which are multiples of $p$ is the same as the contribution in $\floor {\dfrac n p}!$
Thus the argument can be repeated on $\floor {\dfrac n p}!$ until the formula is complete.
{{qed}}
Theorem: Negative Number is Congruent to Modulus minus Number

:$\forall m, n \in \Z: -m \equiv n - m \pmod n$
where $\bmod n$ denotes congruence modulo $n$.

Proof:
Let $-m = r + k n$.
Then $-m + n = r + \paren {k + 1} n$
and the result follows directly by definition.
Theorem: Gaussian Integers form Subring of Complex Numbers

The ring of Gaussian integers:
:$\struct {\Z \sqbrk i, +, \times}$
forms a subring of the set of complex numbers $\C$.

Proof:
From Complex Numbers form Field, $\C$ forms a field.
By definition, a field is a ring.
Thus it is possible to use the Subring Test.
We note that $\Z \sqbrk i$ is not empty, as (for example) $0 + 0 i \in \Z \sqbrk i$.
Let $a + b i, c + d i \in \Z \sqbrk i$.
Then we have $-\paren {c + d i} = -c - d i$, and so:
{{begin-eqn}}
{{eqn | l = \paren {a + b i} + \paren {-\paren {c + d i} }
      | r = \paren {a + b i} + \paren {- c - d i}
      | c = 
}}
{{eqn | r = \paren {a + \paren {-c} } + \paren {b + \paren {-d} } i
      | c = 
}}
{{eqn | r = \paren {a - c} + \paren {b - d} i
      | c = 
}}
{{end-eqn}}
We have that $a, b, c, d \in \Z$ and $\Z$ is an integral domain, therefore by definition a ring.
So it follows that $a - c \in \Z$ and $b - d \in \Z$, and hence:
:$\paren {a - c} + \paren {b - d} i \in \Z \sqbrk i$
Now consider $\paren {a + b i} \paren {c + d i}$.
By the definition of complex multiplication, we have:
:$\paren {a + b i} \paren {c + d i} = \paren {a c - b d} + \paren {a d + b c} i$
As $a, b, c, d \in \Z$ and $\Z$ is a ring, it follows that:
:$a c - b d \in \Z$ and $ad + bc \in \Z$
So:
:$\paren {a + b i} \paren {c + d i} \in \Z \sqbrk i$
So by the Subring Test, $\Z \sqbrk i$ is a subring of $\C$.
{{qed}}
Theorem: Gaussian Rationals form Number Field

The set of Gaussian rationals $\Q \sqbrk i$, under the operations of complex addition and complex multiplication, forms a number field.

Proof:
By definition, a number field is a subfield of the field of complex numbers $\C$.
Recall the definition of the Gaussian rationals:
:$\Q \sqbrk i = \set {z \in \C: z = a + b i: a, b \in \Q}$
From Complex Numbers form Field, $\C$ forms a field.
Thus it is possible to use the Subfield Test.
$\Q \sqbrk i$ is not empty, as (for example) $0 + 0 i \in \Q \sqbrk i$.
Let $a + b i, c + d i \in \Q \sqbrk i$.
Then we have $-\paren {c + d i} = -c - d i$, and so:
{{begin-eqn}}
{{eqn | l = \paren {a + b i} + \paren {-\paren {c + d i} }
      | r = \paren {a + b i} + \paren {-c - d i}
      | c = 
}}
{{eqn | r = \paren {a + \paren {-c} } + \paren {b + \paren {-d} } i
      | c = 
}}
{{eqn | r = \paren {a - c} + \paren {b - d} i
      | c = 
}}
{{end-eqn}}
As $a, b, c, d \in \Q$ and $\Q$ is a field, it follows that $a - c \in \Q$ and $b - d \in \Q$, and hence $\paren {a - c} + \paren {b - d} i \in \Q \sqbrk i$.
Now consider $\paren {a + b i} \paren {c + d i}$.
By the definition of complex multiplication, we have:
:$\paren {a + b i} \paren {c + d i} = \paren {a c - b d} + \paren {a d + b c} i$
As $a, b, c, d \in \Q$ and $\Q$ is a field, it follows that $a c - b d \in \Q$ and $ad + bc \in \Q$ and so $\paren {a + b i} \paren {c + d i} \in \Q \sqbrk i$.
Finally, let $z = x + y i \in \Q \sqbrk i_{\ne 0} = \Q \sqbrk i \setminus \set {0 + 0 i}$, that is such that $x + y i \ne 0 + 0 i$.
Then, by Inverse for Complex Multiplication:
:$\dfrac 1 {x + y i} = \dfrac {x - y i} {x^2 + y^2}$
As $x$ and $y$ are not both zero, it follows that:
:$x^2 + y^2 \ne 0$ and so $x^2 + y^2 \in \Q_{\ne 0}$
Thus it follows that either $\dfrac x {x^2 + y^2} \in \Q_{\ne 0}$ or $\dfrac y {x^2 + y^2} \in \Q_{\ne 0}$ (or both, or course).
Thus $\dfrac 1 {x + y i} \in \Q \sqbrk i_{\ne 0}$.
So by the Subfield Test, $\Q \sqbrk i$ is a subfield of $\C$.
{{qed}}
Theorem: Complex Conjugation is Field Automorphism of Complex Numbers

Consider the field of complex numbers $\C$.
The operation of complex conjugation:
:$\forall z \in \C: z \mapsto \overline z$
is a field automorphism of $\C$.

Proof:
Let:
:$z_1 = x_1 + i y_1$
and:
:$z_2 = x_2 + i y_2$.
Let us define the mapping $\phi: \C \to \C$ defined as:
:$\forall z \in \C: \map \phi z = \overline z$
We check that $\phi$ has the morphism property:
By Sum of Complex Conjugates:
:$\map \phi {z_1 + z_2} = \map \phi {z_1} + \map \phi {z_2}$
By Product of Complex Conjugates:
:$\map \phi {z_1 z_2} = \map \phi {z_1} \map \phi {z_2}$
So the morphism property holds for both complex addition and complex multiplication.
Hence we can say that complex conjugation is a field homomorphism.
{{qed|lemma}}
From Complex Conjugation is Involution, we have that $\phi$ is an involution.
Hence {{afortiori}} $\phi$ is a bijection.
The result then follows by definition of field automorphism.
{{qed}}