avewright/proofwiki-math huggingface dataset:
Theorem: Division Theorem/Positive Divisor/Existence

For every pair of integers $a, b$ where $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
From Division Theorem: Positive Divisor: Positive Dividend: Existence:
:$\forall a, b \in \Z, a \ge 0, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$
That is, the result holds for positive $a$.
{{qed|lemma}}
It remains to be shown that the statement holds for $a < 0$.
From Division Theorem: Positive Divisor: Positive Dividend:
:$\exists \tilde q, \tilde r \in \Z: \size a = \tilde q b + \tilde r, 0 \le \tilde r < b$
where $\size a$ denotes the absolute value of $a$: by definition $\size a \ge 0$.
As $a < 0$ it follows by definition of absolute value that $\size a = -a$.
This gives:
{{begin-eqn}}
{{eqn | l = a
      | r = -\size a
      | c = 
}}
{{eqn | r = -\paren {\tilde q b + \tilde r}
      | c = 
}}
{{eqn | r = b \paren {-\tilde q} + \paren {-\tilde r}
      | c = 
}}
{{end-eqn}}
Let $\tilde r = 0$.
Then:
:$q = -\tilde q, r = \tilde r = 0$
which gives:
:$a = q b + r, 0 \le r < b$
as required.
Otherwise:
:$0 < \tilde r < b \implies 0 < b - \tilde r < b$
which suggests a rearrangement of the expression for $a$ above:
{{begin-eqn}}
{{eqn | l = a
      | r = b \paren {-\tilde q} + \paren {-\tilde r}
      | c = 
}}
{{eqn | r = b \paren {-\tilde q} - b + b - \tilde r
      | c = 
}}
{{eqn | r = b \paren {-1 - \tilde q} + \paren {b - \tilde r}
      | c = 
}}
{{end-eqn}}
Taking:
:$q = \paren {-1 - \tilde q}$
and:
:$r = \paren {b - \tilde r}$
the required result follows.
Uniqueness of $q$ and $r$ follow from the Uniqueness of $\tilde q$ and $\tilde r$.
{{qed}}
Theorem: Division Theorem/Positive Divisor/Existence

For every pair of integers $a, b$ where $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
Let:
: $q = \floor {\dfrac a b}, t = \dfrac a b - \floor {\dfrac a b}$
where $\floor {\, \cdot \,}$ denotes the floor function.
Thus $q \in \Z$ and $t \in \hointr 0 1$.
So:
:$\dfrac a b = q + t$
and so:
:$(1): \quad a = q b + r$
where $r = t d$.
Since $a, q, b \in \Z$, it follows from $(1)$ that:
:$r = a - q b$
and so $r \in \Z$ also.
Since $0 \le t < 1$ and $b > 0$, it follows that:
:$0 \le t b < b$
that is:
:$0 \le r < b$
{{qed}}
Theorem: Division Theorem/Positive Divisor/Existence

For every pair of integers $a, b$ where $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
Let there exist $q \in Z$ such that $a - b q = 0$.
Then $a = b q$ as required, with $r = 0$.
Otherwise, let $S$ be defined as the set of all positive integers of the form $a - z b$ where $z$ is an integer:
:$S = \set {x \in \Z_{\ge 0}: \exists z \in \Z: x = a - z b}$
Setting $z = 0$ it is seen that $a \in S$, so $S \ne \O$.
From Set of Integers Bounded Below by Integer has Smallest Element, $S$ has a smallest element.
Let $r$ be the smallest element of $S$.
Let $r = a - b q$.
As there does not exist $q \in Z$ such that $a - b q = 0$:
:$r > 0$
Suppose $r = b$.
Then $a = b \paren {q + 1}$ and it has already been declared that there does not exist such a $q + 1 \in Z$.
Suppose $r > b$.
Then $x = a - b \paren {q + 1} \in S$ such that $x < r$, which contradicts the assumption that $r$ is the smallest element of $S$.
Hence the result.
{{qed}}
Theorem: Division Theorem/Positive Divisor/Uniqueness/Proof 2

For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
Let $a = q b + r$ where $q, r \in \Z$ and $0 \le r < b$.
Thus:
:$\dfrac a b = q + \dfrac r b$
and:
:$0 \le \dfrac r b \le \dfrac {b - 1} b < 1$
So:
:$q = \floor {\dfrac a b}$
and so:
:$r = a - b \floor {\dfrac a b}$
Thus, given $a$ and $b$, the numbers $q$ and $r$ are unique determined.
{{qed}}
Theorem: Division Theorem/Positive Divisor/Uniqueness

For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
{{:Division Theorem/Positive Divisor/Positive Dividend/Uniqueness/Proof 1}}
Theorem: Division Theorem/Positive Divisor/Uniqueness

For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
Let $a = q b + r$ where $q, r \in \Z$ and $0 \le r < b$.
Thus:
:$\dfrac a b = q + \dfrac r b$
and:
:$0 \le \dfrac r b \le \dfrac {b - 1} b < 1$
So:
:$q = \floor {\dfrac a b}$
and so:
:$r = a - b \floor {\dfrac a b}$
Thus, given $a$ and $b$, the numbers $q$ and $r$ are unique determined.
{{qed}}
Theorem: Division Theorem/Positive Divisor/Uniqueness

For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
Suppose that:
:$a = b q_1 + r_1 = b q_2 + r_2$
where both $0 \le r_1 < b$ and $0 \le r_2 < b$.
{{WLOG}}, suppose $r_1 \ge r_2$.
Then:
:$r_1 - r_2 = b \paren {q_2 - q_1}$
That is:
:$b \divides \paren {r_2 - r_1}$
where $\divides$ denotes divisibility.
But:
:$r_1 - r_2 < b$
while from Absolute Value of Integer is not less than Divisors: Corollary:
:$r_1 - r_2 \ge b$
unless from Integer Divides Zero $r_1 - r_2 = 0$.
So $r_1 = r_2$ and it follows directly that $q_1 = q_2$.
{{qed}}
Theorem: Division Theorem/Positive Divisor/Existence/Proof 3

For every pair of integers $a, b$ where $b > 0$, there exist integers $q, r$ such that $a = q b + r$ and $0 \le r < b$:
:$\forall a, b \in \Z, b > 0: \exists q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
Let there exist $q \in Z$ such that $a - b q = 0$.
Then $a = b q$ as required, with $r = 0$.
Otherwise, let $S$ be defined as the set of all positive integers of the form $a - z b$ where $z$ is an integer:
:$S = \set {x \in \Z_{\ge 0}: \exists z \in \Z: x = a - z b}$
Setting $z = 0$ it is seen that $a \in S$, so $S \ne \O$.
From Set of Integers Bounded Below by Integer has Smallest Element, $S$ has a smallest element.
Let $r$ be the smallest element of $S$.
Let $r = a - b q$.
As there does not exist $q \in Z$ such that $a - b q = 0$:
:$r > 0$
Suppose $r = b$.
Then $a = b \paren {q + 1}$ and it has already been declared that there does not exist such a $q + 1 \in Z$.
Suppose $r > b$.
Then $x = a - b \paren {q + 1} \in S$ such that $x < r$, which contradicts the assumption that $r$ is the smallest element of $S$.
Hence the result.
{{qed}}
Theorem: Division Theorem/Positive Divisor/Uniqueness/Proof 3

For every pair of integers $a, b$ where $b > 0$, the integers $q, r$ such that $a = q b + r$ and $0 \le r < b$ are unique:
:$\forall a, b \in \Z, b > 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < b$

Proof:
It is given by Division Theorem: Positive Divisor: Existence that such $q$ and $r$ exist.
Suppose that:
:$a = b q_1 + r_1 = b q_2 + r_2$
where both $0 \le r_1 < b$ and $0 \le r_2 < b$.
{{WLOG}}, suppose $r_1 \ge r_2$.
Then:
:$r_1 - r_2 = b \paren {q_2 - q_1}$
That is:
:$b \divides \paren {r_2 - r_1}$
where $\divides$ denotes divisibility.
But:
:$r_1 - r_2 < b$
while from Absolute Value of Integer is not less than Divisors: Corollary:
:$r_1 - r_2 \ge b$
unless from Integer Divides Zero $r_1 - r_2 = 0$.
So $r_1 = r_2$ and it follows directly that $q_1 = q_2$.
{{qed}}
Theorem: Integer Coprime to all Factors is Coprime to Whole

Let $a, b \in \Z$.
Let $\ds b = \prod_{j \mathop = 1}^r b_j$
Let $a$ be coprime to each of $b_1, \ldots, b_r$.
Then $a$ is coprime to $b$.

Proof:
From Integer Combination of Coprime Integers:
:$\forall j \in \set {1, 2, \ldots, r}: a x_j + b_j y_j = 1$
for some $x_j, y_j \in \Z$.
Thus:
:$\ds \prod_{j \mathop = 1}^r b_j y_j = \prod_{j \mathop = 1}^r \paren {1 - a x_j}$
But $\ds \prod_{j \mathop = 1}^r \paren {1 - a x_j}$ is of the form $1 - a z$.
Thus:
{{begin-eqn}}
{{eqn | l = \prod_{j \mathop = 1}^r b_j \prod_{j \mathop = 1}^r y_j
      | r = 1 - a z
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a z + b y
      | r = 1
      | c = where $\ds y = \prod_{j \mathop = 1}^r y_j$
}}
{{end-eqn}}
and so, by Integer Combination of Coprime Integers, $a$ and $b$ are coprime.
{{qed}}
Theorem: All Factors Divide Integer then Whole Divides Integer

Let $S = \set {a_1, a_2, \ldots, a_r} \subseteq \Z$ be a finite subset of the integers.
Let $S$ be pairwise coprime.
Let:
:$\forall j \in \set {1, 2, \ldots, r}: a_r \divides b$
where $\divides$ denotes divisibility.
Then:
:$\ds \prod_{j \mathop = 1}^r a_j \divides b$

Proof:
Proof by induction:
In the following, it is assumed at all times that $S = \set {a_1, a_2, \ldots, a_r} \subseteq \Z$ is pairwise coprime.
For all $r \in \N_{> 1}$, let $\map P r$ be the proposition:
:$\ds \prod_{j \mathop = 1}^r a_j \divides b$
Theorem: Piecewise Continuous Function with One-Sided Limits is Bounded

Let $f$ be a real function defined on a closed interval $\closedint a b$.
Let $f$ be a piecewise continuous function with one-sided limits.
Then $f$ is a bounded piecewise continuous function.

Proof:
Let $f$ be a piecewise continuous function with one-sided limits.
By definition, there exists a finite subdivision $\set {x_0, x_1, \ldots, x_n}$ of $\closedint a b$, where $x_0 = a$ and $x_n = b$, such that $f$ is continuous on $\openint {x_{i − 1} } {x_i}$ for every $i \in \set {1, 2, \ldots, n}$.
For every $i \in \set {1, 2, \ldots, n}$, we define a function $f_i$ with domain $\closedint {x_{i − 1} } {x_i}$, as follows:
$\quad\map {f_i} x := \begin{cases}
\ds \lim_{x \mathop \to x_{i − 1}^+} \map f x & : x = x_{i - 1} \\
\map f x & : x \in \openint {x_{i - 1} } {x_i} \\
\ds \lim_{x \mathop \to x_i^-} \map f x & : x = x_i
\end{cases}$
The one-sided limits in this definition exist because $f$ is piecewise continuous with one-sided limits.
We have that $f$ is continuous on $\openint {x_{i - 1} } {x_i}$.
We also have that $f_i = f$ on $\openint {x_{i - 1} } {x_i}$.
Therefore $f_i$ is also continuous on $\openint {x_{i - 1} } {x_i}$.
By definition, $f_i$ is right-continuous at $x_{i − 1}$ and left-continuous at $x_i$.
Therefore, $f_i$ is continuous throughout its domain $\closedint {x_{i − 1} } {x_i}$.
By Continuous Function on Compact Subspace of Euclidean Space is Bounded and Closed Real Interval is Compact in Metric Space, $f_i$ is bounded.
Therefore, $f_i$ is bounded on $\closedint {x_{i − 1} } {x_i}$.
We have that $\openint {x_{i - 1} } {x_i}$ constitutes a subset of $\closedint {x_{i − 1} } {x_i}$.
Thus $f_i$ is also bounded on $\openint {x_{i - 1} } {x_i}$.
As $f_i = f$ on $\openint {x_{i - 1} } {x_i}$, $f$ is also bounded on $\openint {x_{i - 1} } {x_i}$.
We have that:
:$f$ is bounded on the intervals $\openint {x_{i - 1} } {x_i}$
and
:the set of these intervals is finite.
Hence the set of bounds of $f$ on these intervals is itself bounded.
The bound of this set of bounds serves as a bound for $f$ on each of the intervals $\openint {x_{i - 1} } {x_i}$.
Therefore, this bound is a bound for $f$ on the union of these intervals.
That is, $f$ is bounded on the union of $\openint {x_{i - 1} } {x_i}$ for all $i \in \set {1, 2, \ldots, n}$.
The only points left to consider are the points in the set $\set {x_0, x_1, \ldots, x_n}$. 
Since this set is finite, the maximum $\map \max {\size {\map f {x_0} }, \size {\map f {x_1} }, \ldots, \size {\map f {x_n} } }$ is finite and serves as a bound for $f$ on $\set {x_0, x_1, \ldots, x_n}$.
Thus $f$ is bounded on the whole of its domain $\closedint a b$.
Hence $f$ is a bounded piecewise continuous function.
{{qed}}
Theorem: Upper Bounds for Prime Numbers/Result 1

:$\forall n \in \N: \map p n \le 2^{2^{n - 1} }$

Proof:
Proof by strong induction:
Let us write $p_n = \map p n$.
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\map p n \le 2^{2^{n - 1} }$
Theorem: Upper Bounds for Prime Numbers/Result 2

:$\forall n \in \N: \map p n \le \paren {p \paren {n - 1} }^{n - 1} + 1$

Proof:
Let us write $p_n = \map p n$.
Let us take $N = p_1 p_2 \cdots p_n + 1$.
By the same argument as in Euclid's Theorem, we have that either $N$ is prime, or it is not.
If $N$ is prime, then either $N = p_{n + 1}$ or not, in which case $N > p_{n + 1}$.
In the second case, $N$ has a prime factor not in $\set {p_1, p_2, \ldots, p_n}$
Therefore it must have a prime factor greater than any of $\set {p_1, p_2, \ldots, p_n}$.
In any case, the next prime after $p_n$ can be no greater than $p_1 p_2 \cdots p_n + 1$.
Hence the result.
{{qed}}
Theorem: Upper Bounds for Prime Numbers/Result 3

: $\forall n \in \N_{>1}: p \left({n}\right) < 2^n$

Proof:
Let us write $p_n = p \left({n}\right)$.
From Bertrand's Conjecture, for each $n \ge 2$ there exists a prime $p$ such that $n < p < 2 n$.
For all $n \in \N_{>0}$, let $P \left({n}\right)$ be the proposition:
: $p_n < 2^n$
$P(1)$ is the statement:
:$p_1 = 2 = 2^1$
As this does not fulfil the criterion:
:$p \left({n}\right) < 2^n$
it is not included in the result.
Theorem: Product of Integers of form 4n + 1

Let $m, n \in \Z$ such that both $m$ and $n$ are of the form $4 k + 1$ where $k \in \Z$.
Then $m n$ is also of the form $4 k + 1$.

Proof:
Let $m = 4 k_1 + 1, n = 4 k_2 + 1$.
Then:
{{begin-eqn}}
{{eqn | l = m n
      | r = \paren {4 k_1 + 1} \paren {4 k_2 + 1}
      | c = 
}}
{{eqn | r = 4 k_1 \cdot 4 k_2 + 4 k_1 + 4 k_2 + 1
      | c = Integer Multiplication Distributes over Addition
}}
{{eqn | r = \paren {4 k_1 \cdot 4 k_2 + 4 k_1 + 4 k_2} + 1
      | c = Integer Addition is Associative
}}
{{eqn | r = 4 \paren {k_1 \cdot 4 k_2 + k_1 + k_2} + 1
      | c = Integer Multiplication Distributes over Addition
}}
{{eqn | r = 4 \paren {4 k_1 k_2 + k_1 + k_2} + 1
      | c = Integer Multiplication is Commutative
}}
{{eqn | r = 4 k + 1
      | c = where $k = 4 k_1 k_2 + k_1 + k_2 \in \Z$
}}
{{end-eqn}}
{{qed}}
Theorem: Infinite Number of Primes of form 4n - 1

There are infinitely many prime numbers of the form $4 n - 1$.

Proof:
{{AimForCont}} the contrary.
That is, suppose there is a finite number of prime numbers of the form $4 n - 1$.
Let there be $k$ of them: $p_1, p_2, \ldots, p_k$.
Let $S = \set {p_1, p_2, \ldots, p_k}$.
Let $N$ be constructed as:
:$\ds N = 4 \prod_{i \mathop = 1}^k p_i - 1$
If $N$ is a prime number, then it is of the form $4 n - 1$.
But then we have that $N \notin S$, which means that $S$ is not the complete set of prime numbers of the form $4 n - 1$.
Therefore $N$ must be composite.
Suppose all the prime factors of $N$ are of the form $4 n + 1$.
Then from Product of Integers of form $4 n + 1$ it follows that $N$ itself is of the form $4 n + 1$.
Therefore $N$ must have at least one prime factor $p$ of the form $4 n - 1$.
Suppose $p \in S$.
We have that:
:$\ds p \divides 4 \prod_{i \mathop = 1}^k p_i$
and so:
:$\ds p \divides 4 \prod_{i \mathop = 1}^k p_i - p$
So:
:$N = q p + \left({p - 1}\right)$
where:
:$q = \dfrac {\ds 4 \prod_{i \mathop = 1}^k p_i - p} p$
So applying the Euclidean Algorithm:
{{begin-eqn}}
{{eqn | l = \gcd \set {N, p}
      | r = \gcd \set {p - 1, p}
      | c = 
}}
{{eqn | r = \gcd \set {p - 1, 1}
      | c = 
}}
{{eqn | r = 1
      | c = 
}}
{{end-eqn}}
So if $p \in S$, then it cannot be a divisor of $N$.
Therefore there must be a prime numbers of the form $4 n - 1$ which is not in $S$.
Therefore $S$ is not the complete set of prime numbers of the form $4 n - 1$.
Therefore the assumption that $S$ is finite was false.
Hence the result.
{{qed}}
Theorem: Integer Coprime to Modulus iff Linear Congruence to 1 exists

Let $a, m \in \Z$.
The linear congruence:
:$a x \equiv 1 \pmod m$
has a solution $x$ {{iff}} $a$ and $m$ are coprime.

Proof:
{{begin-eqn}}
{{eqn | l = a x
      | o = \equiv
      | r = 1
      | rr= \pmod m
      | c = 
}}
{{eqn | ll=\leadstoandfrom
      | q = \exists y \in \Z
      | l = a x + m y
      | r = 1
      | c = {{Defof|Congruence Modulo Integer}}
}}
{{end-eqn}}
From Integer Combination of Coprime Integers:
:$a \perp m \iff \exists x, y \in \Z: a x + m y = 1$
That is, such an $x$ exists {{iff}} $a$ and $m$ are coprime.
{{qed}}
Theorem: Integer Coprime to Modulus iff Linear Congruence to 1 exists/Corollary

Let $p$ be a prime number.
The linear congruence:
:$a x \equiv 1 \pmod p$
has a solution $x$ {{iff}} $a \not \equiv 0 \pmod p$.

Proof:
By definition of congruence:
:$a \not \equiv 0 \pmod p \iff p \nmid a$
where $p \nmid a$ denotes that $p$ is not a divisor of $a$.
From Prime not Divisor implies Coprime:
:$p \nmid a \iff p \perp a$
where $p \perp a$ denotes that $p$ and $a$ are coprime.
The result follows from Integer Coprime to Modulus iff Linear Congruence to 1 exists.
{{qed}}
Theorem: Solution of Linear Congruence/Existence

$a x \equiv b \pmod n$ has at least one solution {{iff}}:
:$\gcd \set {a, n} \divides b$
that is, {{iff}} $\gcd \set {a, n}$ is a divisor of $b$.

Proof:
Consider the linear congruence $a x \equiv b \pmod n$.
Suppose $\exists x_0 \in \Z: a x_0 \equiv b \pmod n$.
Then $\exists y_0 \in Z: a x_0 - b = n y_0$ by definition of congruence.
Thus $x = x_0, y = y_0$ is a solution to the linear Diophantine equation $a x - n y = b$.
On the other hand, if $x = x_0, y = y_0$ is a solution to the linear Diophantine equation $a x - n y = b$, then it follows that $a x \equiv b \pmod n$.
Hence:
:the problem of finding all integers satisfying the linear congruence $a x \equiv b \pmod n$ 
is the same problem as:
:the problem of finding all the $x$ values in the linear Diophantine equation $a x - n y = b$.
From Solution of Linear Diophantine Equation:
The linear Diophantine equation $a x - n y = b$ has at least one solution {{iff}}:
:$\gcd \set {a, n} \divides b$
Hence the result.
{{qed}}
Theorem: Solution of Linear Congruence/Number of Solutions

Let $\gcd \set {a, n} = d$.
Then $a x \equiv b \pmod n$ has $d$ solutions which are given by the unique solution modulo $\dfrac n d$ of the congruence:
:$\dfrac a d x \equiv \dfrac b d \paren {\bmod \dfrac n d}$

Proof:
From Solution of Linear Congruence: Existence:
:the problem of finding all integers satisfying the linear congruence $a x \equiv b \pmod n$ 
is the same problem as:
:the problem of finding all the $x$ values in the linear Diophantine equation $a x - n y = b$.
From Integers Divided by GCD are Coprime:
:$\gcd \set {\dfrac a d, \dfrac n d} = 1$
So the {{RHS}} has a unique solution modulo $\dfrac n d$, say:
:$x \equiv x_1 \paren {\bmod \dfrac n d}$
So the integers $x$ which satisfy $a x \equiv b \pmod n$ are exactly those of the form $x = x_1 + k \dfrac n d$ for some $k \in \Z$.
Consider the set of integers:
: $\set {x_1, x_1 + \dfrac n d, x_1 + 2 \dfrac n d, \ldots, x_1 + \paren {d - 1} \dfrac n d}$
None of these are congruent modulo $n$ and none differ by as much as $n$.
Further, for any $k \in Z$, we have that $x_1 + k \dfrac n d$ is congruent modulo $n$ to one of them.
To see this, write $k = d q + r$ where $0 \le r < d$ from the Division Theorem.
Then:
{{begin-eqn}}
{{eqn | l = x_1 + k \frac n d
      | r = x_1 + \paren {d q + r} \frac n d
      | c = 
}}
{{eqn | r = x_1 + n q + r \frac n d
      | c = 
}}
{{eqn | o = \equiv
      | r = x_1 + r \frac n d
      | rr= \pmod n
      | c = 
}}
{{end-eqn}}
So these are the $d$ solutions of $a x \equiv b \pmod n$.
{{qed}}
Theorem: Solution of Linear Congruence/Unique iff Coprime to Modulus

$a x \equiv b \pmod n$ has a unique solution {{iff}} $\gcd \set {a, n} = 1$.

Proof:
=== Sufficient Condition ===
{{ProofWanted}}
Theorem: Ring Direct Product of Modulo Integers is Isomorphic to Ring Modulo Product iff Coprime

Let $m, n \in \Z_{>1}$.
Let $\struct {\Z_m, +_m, \times_m}$ and $\struct {\Z_n, +_n, \times_n}$ be the rings of integers modulo $m$ and $n$ respectively.
Let $\struct {\Z_m \times \Z_n}$ be the direct product of $\Z_m$ and $\Z_n$.
Let $\struct {\Z_{m n}, +_{m n}, \times_{m n} }$ be the ring of integers modulo $mn$.
Then $\struct {\Z_m \times \Z_n}$ is isomorphic to $\struct {\Z_{m n}, +_{m n}, \times_{m n} }$ {{iff}} $m$ and $n$ are coprime.

Proof:
{{ProofWanted|First a homomorphism is established between $\struct {\Z_m \times \Z_n}$ and $\struct {\Z_m \times \Z_n}$. Then it is demonstrated that $\phi: \struct {\Z_m \times \Z_n} \to \Z_{m n}$ is a bijection. Some of this has already been done, I'm fairly sure.}}
Theorem: Trivial Norm on Division Ring is Norm

Let $\struct {R, +, \circ}$ be a division ring, and denote its ring zero by $0_R$.
Then the trivial norm $\norm {\, \cdot \,}: R \to \R_{\ge 0}$, which is given by:
:$ \norm x = \begin{cases} 0 & \text { if } x = 0_R\\ 1 & \text { otherwise} \end{cases}$
defines a norm on $R$.

Proof:
Proving each of the norm axioms one by one:
Theorem: Trivial Norm on Division Ring is Non-Archimedean

Let $\struct {R, +, \circ}$ be a division ring whose ring zero is $0_R$.
Then the trivial norm $\norm {\, \cdot \,}: R \to \R_{\ge 0}$, which is given by:
:$\norm x = \begin{cases}
  0 & : x = 0_R \\
  1 & : \text{ otherwise}
\end{cases}$
is non-archimedean:
:$\norm {x + y} \le \max \set {\norm x, \norm y}$

Proof:
Let $x, y = 0_R$.
Then:
:$\norm x, \norm y = 0$
Therefore:
:$\max \set {\norm x, \norm y} = 0$.
Hence:
{{begin-eqn}}
{{eqn | l = \norm {x + y}
      | r = \norm {0_R + 0_R}
      | c = 
}}
{{eqn | r = \norm {0_R}
      | c = 
}}
{{eqn | r = 0
      | c = 
}}
{{eqn | r = \max \set {\norm x, \norm y} 
      | c = 
}}
{{end-eqn}}
Let $x \ne 0_R$ or $y \ne 0_R$.
Then:
:$\norm x = 1$ or $\norm y = 1$
Therefore:
:$\max \set {\norm x, \norm y} = 1$.
Hence:
{{begin-eqn}}
{{eqn | l = \norm {x + y}
      | o = \le
      | r = 1
      | c = {{Defof|Trivial Norm on Division Ring}}
}}
{{eqn | r = \max \set {\norm x, \norm y}
      | c = 
}}
{{end-eqn}}
{{qed}}
Category:Trivial Norms
s5has14axjeaicsn7dkar1jr2vq0ibz
Theorem: Ring of Integers Modulo m is Ring

For all $m \in \N: m \ge 2$, the ring of integers modulo $m$:
:$\struct {\Z_m, +_m, \times_m}$
is a commutative ring with unity $\eqclass 1 m$.
The zero of $\struct {\Z_m, +_m, \times_m}$ is $\eqclass 0 m$.

Proof:
First we check the ring axioms:
:{{Ring-axiom|A}}
::The Integers Modulo $m$ under Addition form Abelian Group.
::From Modulo Addition has Identity, $\eqclass 0 m$ is the identity of the additive group $\struct {\Z_m, +_m}$.
From Integers Modulo m under Multiplication form Commutative Monoid:
:{{Ring-axiom|M0}}:
::$\struct {\Z_m, \times_m}$ is closed.
:{{Ring-axiom|M1}}:
::$\struct {\Z_m, \times_m}$ is associative.
:{{Ring-axiom|M2}}:
::$\struct {\Z_m, \times_m}$ has an identity $\eqclass 1 m$.
:{{Ring-axiom|C}}:
::$\struct {\Z_m, \times_m}$ is commutative.
Then:
:{{Ring-axiom|D}}:
::$\times_m$ distributes over $+_m$ in $\Z_m$.
{{qed}}