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

From ProofWiki
Jump to navigation Jump to search
  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. 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. Fibonacci Number in terms of Smaller Fibonacci Numbers
  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