# User:Ascii/ProofWiki Sampling Notes for Theorems/Number Theory

1. Set of Integers Bounded Below by Integer has Smallest Element
Let $\Z$ be the set of integers.
Let $\le$ be the ordering on the integers.
Let $\O \subset S \subseteq \Z$ such that $S$ is bounded below in $\struct {\Z, \le}$.
Then $S$ has a smallest element.
2. Set of Integers Bounded Above by Integer has Greatest Element
Let $\Z$ be the set of integers.
Let $\le$ be the ordering on the integers.
Let $\O \subset S \subseteq \Z$ such that $S$ is bounded above in $\struct {\Z, \le}$.
Then $S$ has a greatest element.
3. Division Theorem
$\forall a, b \in \Z, b \ne 0: \exists! q, r \in \Z: a = q b + r, 0 \le r < \left\lvert{b}\right\rvert$
4. Integer Divisor Results/One Divides all Integers
$\forall n \in \Z: 1 \divides n \land -1 \divides n$
5. Integer Divisor Results/Integer Divides Itself
$\forall n \in \Z: n \divides n$
6. Integer Divisor Results/Integer Divides its Negative
$\forall n \in \Z: n \divides (-n)$
7. Integer Divisor Results/Integer Divides its Absolute Value
$\forall n \in \Z: n \divides \left \lvert {n}\right \rvert$
$\forall n \in \Z: \left \lvert {n}\right \rvert \divides n$
8. Integer Divisor Results/Integer Divides Zero
$\forall n \in \Z: n \divides 0$
9. Zero Divides Zero
$\forall n \in \Z: 0 \divides n \implies n = 0$
10. Divisor Relation is Transitive
$\forall x, y, z \in \Z: x \divides y \land y \divides z \implies x \divides z$
11. Divisor Relation is Antisymmetric
$\forall a, b \in \Z_{>0}: a \divides b \land b \divides a \implies a = b$
12. Divisor Relation on Positive Integers is Partial Ordering
The divisor relation is a partial ordering of $\Z_{>0}$.
13. Integer Divisor Results/Divisors of Negative Values
$\forall m, n \in \Z: m \divides n \iff -m \divides n \iff m \divides -n \iff -m \divides -n$
14. Common Divisor Divides Integer Combination
15. Existence of Greatest Common Divisor
$\forall a, b \in \Z: a \ne 0 \lor b \ne 0$, there exists a largest $d \in \Z_{>0}$ such that $d \divides a$ and $d \divides b$.
That is, the greatest common divisor of $a$ and $b$ always exists.
16. Greatest Common Divisor is at least 1
The greatest common divisor of $a$ and $b$ is at least $1$: $\forall a, b \in \Z_{\ne 0}: \gcd \set {a, b} \ge 1$
17. GCD of Integer and Divisor
$a, b \in \Z_{>0}: a \divides b \implies \gcd \left\{{a, b}\right\} = a$
18. GCD for Negative Integers
$\gcd \left\{{a, b}\right\} = \gcd \left\{{\left|{a}\right|, b}\right\} = \gcd \left\{{a, \left|{b}\right|}\right\} = \gcd \left\{{\left|{a}\right|, \left|{b}\right|}\right\}$
$\gcd \left\{{a, b}\right\} = \gcd \left\{{-a, b}\right\} = \gcd \left\{{a, -b}\right\} = \gcd \left\{{-a, -b}\right\}$
19. GCD with Zero
$\forall a \in \Z_{\ne 0}: \gcd \left\{{a, 0}\right\} = \left\lvert{a}\right\rvert$
20. Bézout's Lemma
Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Then $\exists x, y \in \Z: a x + b y = \gcd \left\{{a, b}\right\}$
That is, $\gcd \left\{{a, b}\right\}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \left\{{a, b}\right\}$ is the smallest positive integer combination of $a$ and $b$.
21. Solution of Linear Diophantine Equation
22. GCD with Remainder
Let $a, b \in \Z$ and $q, r \in \Z$ such that $a = q b + r$.
Then $\gcd \left\{{a, b}\right\} = \gcd \left\{{b, r}\right\}$.
23. Coprime Relation for Integers is Non-Reflexive
24. Coprime Relation for Integers is Not Reflexive
25. Coprime Relation for Integers is Not Antireflexive
26. Coprime Relation for Integers is Symmetric
27. Coprime Relation for Integers is Not Antisymmetric
28. Coprime Relation for Integers is Non-transitive
29. Coprime Relation for Integers is Not Transitive
30. Coprime Relation for Integers is Not Antitransitive
31. Integer Combination of Coprime Integers
Two integers are coprime if and only if there exists an integer combination of them equal to $1$: $\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
32. Divisor of Sum of Coprime Integers
Let $a, b, c \in \Z_{>0}$ such that: $a \perp b$ and $c \divides \paren {a + b}$
Then $a \perp c$ and $b \perp c$
33. Integers Divided by GCD are Coprime
Any pair of integers, not both zero, can be reduced to a pair of coprime ones by dividing them by their GCD:
$\gcd \left\{{a, b}\right\} = d \iff \dfrac a d, \dfrac b d \in \Z \land \gcd \left\{{\dfrac a d, \dfrac b d}\right\} = 1$
34. Euclid's Lemma
Let $a, b, c \in \Z$ and $a \divides b c$.
Then $a \divides c$.
1. Existence of Lowest Common Multiple
Let $a, b \in \Z: a b \ne 0$.
The lowest common multiple of $a$ and $b$, denoted $\lcm \set {a, b}$, always exists.
1. Product of GCD and LCM
$\lcm \set {a, b} \times \gcd \set {a, b} = \size {a b}$
1. 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} }$
And $\gcd \set {a, \lcm \set {b, c} } = \lcm \set {\gcd \set {a, b}, \gcd \set {a, c} }$
1. Divisor of One of Coprime Numbers is Coprime to Other

Possible:

1. Divisors of Product of Coprime Integers
Let $a \divides b c$, where $b \perp c$.
Then $a = r s$, where $r \divides b$ and $s \divides c$.

# Congruence

1. Congruence Modulo Integer is Equivalence Relation
For all $z \in \Z$, congruence modulo $z$ is an equivalence relation.
Let $m \in \Z$ be an integer.
Then addition modulo $m$ on the set of integers modulo $m$ is closed: $\forall \eqclass x m, \eqclass y m \in \Z_m: \eqclass x m +_m \eqclass y m \in \Z_m$.
$\forall \eqclass x m, \eqclass y m, \eqclass z m \in \Z_m: \paren {\eqclass x m +_m \eqclass y m} +_m \eqclass z m = \eqclass x m +_m \paren {\eqclass y m +_m \eqclass z m}$
Modulo addition is commutative: $\forall x, y, z \in \Z: x + y \pmod m = y + x \pmod m$
5. 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$.
6. Modulo Multiplication is Associative
Multiplication modulo $m$ is associative: $\forall \left[\!\left[{x}\right]\!\right]_m, \left[\!\left[{y}\right]\!\right]_m, \left[\!\left[{z}\right]\!\right]_m \in \Z_m: \left({\left[\!\left[{x}\right]\!\right]_m \times_m \left[\!\left[{y}\right]\!\right]_m}\right) \times_m \left[\!\left[{z}\right]\!\right]_m = \left[\!\left[{x}\right]\!\right]_m \times_m \left({\left[\!\left[{y}\right]\!\right]_m \times_m \left[\!\left[{z}\right]\!\right]_m}\right)$
7. 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$

### The Binomial Theorem

1. Binomial Theorem

### Fibonacci

1. Fibonacci Number with Negative Index
2. Cassini's Identity
$F_{n + 1} F_{n - 1} - F_n^2 = \paren {-1}^n$
3. Fibonacci Number in terms of Smaller Fibonacci Numbers
4. Fibonacci Number in terms of Larger Fibonacci Numbers