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 Identity

    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. Number is Divisor iff Modulo is Zero
2. Integer is Congruent to Integer less than Modulus

1. Congruence Modulo Integer is Equivalence Relation

   For all $z \in \Z$, congruence modulo $z$ is an equivalence relation.

2. Modulo Addition is Closed/Integers

   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$.

3. Modulo Addition is Associative

   $\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}$

4. Modulo Addition is Commutative

   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. Honsberger's Identity
4. Fibonacci Number in terms of Larger Fibonacci Numbers

1. Divisibility of Fibonacci Number
2. Sum of Sequence of Fibonacci Numbers
3. Sum of Sequence of Odd Index Fibonacci Numbers
4. Sum of Sequence of Even Index Fibonacci Numbers
5. Sum of Sequence of Products of Consecutive Fibonacci Numbers
6. Lucas Number as Sum of Fibonacci Numbers

1. Consecutive Fibonacci Numbers are Coprime
2. GCD of Fibonacci Numbers
3. Vajda's Identity/Formulation 1