nyuuzyou/wikis huggingface dataset:
Integer Less One divides Power Less One

== Theorem ==
Let $q, n \in \Z_{>0}$.
Then:
:$\paren {q - 1} \divides \paren {q^n - 1}$
where $\divides$ denotes divisibility.
=== Corollary ===
== Proof ==
From Sum of Geometric Sequence:
:$\ds \frac {q^n - 1} {q - 1} = \sum_{k \mathop = 0}^{n - 1} q^k$
That is:
:$q^n - 1 = r \paren {q - 1}$
where $r = 1 + q + q^2 + \cdots + q^{n - 1}$.
As Integer Addition is Closed and Integer Multiplication is Closed, it follows that $r \in \Z$.
Hence the result by definition of divisor of integer.
== Sources ==
* : $\S 2.4$: The rational numbers and some finite fields: Further Exercises $5$
Category:Number Theory
Integer Less One divides Power Less One/Corollary

== Corollary to Integer Less One divides Power Less One ==
Let $m, n, q \in \Z_{>0}$.
Let:
:$m \divides n$
where $\divides$ denotes divisibility.
Then:
:$\paren {q^m - 1} \divides \paren {q^n - 1}$
=== Converse to Corollary ===
== Proof ==
By hypothesis:
:$m \divides n$
By definition of divisibility:
:$\exists k \in \Z: k m = n$
Thus:
:$q^n = q^{k m} = \paren {q^m}^k$
Then by Integer Less One divides Power Less One:
:$\paren {q^m - 1} \divides \paren {\paren {q^m}^k - 1}$
Hence the result.
== Sources ==
* : $\S 2.4$: The rational numbers and some finite fields: Further Exercises $5$
Category:Number Theory
Integer Less One divides Power Less One/Corollary/Converse

== Converse of Corollary to Integer Less One divides Power Less One ==
Let $m, n, q \in \Z_{>0}$.
Let
:$\paren {q^m - 1} \divides \paren {q^n - 1}$
where $\divides$ denotes divisibility.
Then:
:$m \divides n$
== Proof ==
By the Division Theorem:
:$\exists a, b \in \Z: n = m a + b, 0 \le b < m$
Then:
:$q^n \equiv q^{m a} q^b \equiv q^b \equiv 1 \pmod {\paren {q^m - 1} }$
But:
:$q^b - 1 < q^m - 1$
So:
:$q^b - 1 = 0$
and so $b = 0$.
Hence the result.
== Sources ==
* : $\S 2.4$: The rational numbers and some finite fields: Further Exercises $6$
Category:Number Theory
Integer Multiple of Integer Combination is Integer Combination

== Lemma ==
Let $a, b \in \Z$ be integers.
Let $S = \set {a x + b y: x, y \in \Z}$ be the set of integer combinations of $a$ and $b$.
Let $u \in S$.
Let $n \in \Z$.
Then $n u \in S$.
== Proof ==
Let $u = a x + b y$ where both $x$ and $y$ are integers.
Then:
As Integer Multiplication is Closed, both $n x$ and $n y$ are integers.
Hence the result.
== Sources ==
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Lemma $1$
Category:Integer Combinations
Integer Multiples Closed under Addition

== Theorem ==
Let $n \Z$ be the set of integer multiples of $n$.
Then the algebraic structure $\struct {n \Z, +}$ is closed under addition.
== Proof ==
Let $x, y \in n \Z$.
Then $\exists p, q \in \Z: x = n p, y = n q$.
So $x + y = n p + n q = n \paren {p + q}$ where $p + q \in \Z$.
Thus $x + y \in n \Z$ and so $\struct {n \Z, +}$ is closed.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Example $8.1$
Category:Integer Addition
Category:Algebraic Closure
Integer Multiples Closed under Multiplication

== Theorem ==
Let $n \Z$ be the set of integer multiples of $n$.
Then the algebraic structure $\struct {n \Z, \times}$ is closed under multiplication.
== Proof ==
Let $x, y \in n \Z$.
Then $\exists p, q \in \Z: x = n p, y = n q$.
So $x y = n p \cdot n q = n \paren {n p q}$ where $n p q \in \Z$.
Thus $x y \in n \Z$ and so $\struct {n \Z, \times}$ is closed.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Example $8.1$
Category:Integer Multiplication
Category:Algebraic Closure
Integer Multiples Greater than Positive Integer Closed under Addition

== Theorem ==
Let $n \Z$ be the set of integer multiples of $n$.
Let $p \in \Z: p \ge 0$ be a positive integer.
Let $S \subseteq n \Z$ be defined as:
:$S := \set {x \in n \Z: x > p}$
that is, the set of integer multiples of $n$ greater than $p$.
Then the algebraic structure $\struct {S, +}$ is closed under addition.
== Proof ==
Let $x, y \in S$.
From Integer Multiples Closed under Addition, $x + y \in n \Z$.
As $x, y > p$ we have that:
:$\exists r \in \Z_{>0}: x = p + r$
:$\exists s \in \Z_{>0}: y = p + s$
Thus it follows that:
So $x + y > p$ and $x + y \in n \Z$.
Hence by definition $x + y \in S$, and so $S$ is closed under addition.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Example $8.1$
Category:Integer Addition
Category:Algebraic Closure
Integer Multiples Greater than Positive Integer Closed under Multiplication

== Theorem ==
Let $n \Z$ be the set of integer multiples of $n$.
Let $p \in \Z: p \ge 0$ be a positive integer.
Let $S \subseteq n \Z$ be defined as:
:$S := \set {x \in n \Z: x > p}$
that is, the set of integer multiples of $n$ greater than $p$.
Then the algebraic structure $\struct {S, \times}$ is closed under multiplication.
== Proof ==
Let $x, y \in S$.
From Integer Multiples Closed under Multiplication, $x y \in n \Z$.
As $x, y > p$ we have that:
:$\exists r \in \Z_{>0}: x = p + r$
:$\exists s \in \Z_{>0}: y = p + s$
Thus it follows that:
So $x y > p$ and $x y \in n \Z$.
Hence by definition $x y \in S$, and so $S$ is closed under multiplication.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Example $8.1$
Category:Integer Multiplication
Category:Algebraic Closure
Integer Multiples form Commutative Ring

== Theorem ==
Let $n \Z$ be the set of integer multiples of $n$.
Then $\struct {n \Z, +, \times}$ is a commutative ring.
Unless $n = 1$, $\struct {n \Z, +, \times}$ is not a ring with unity.
== Proof ==
From Integer Multiples under Addition form Infinite Cyclic Group, $\struct {n \Z, +}$ is a cyclic group
From Cyclic Group is Abelian, $\struct {n \Z, +}$ is abelian.
From Integer Multiples Closed under Multiplication and Integer Multiplication is Associative, we have that $\struct {n \Z, \times}$ is a semigroup.
From Integer Multiplication Distributes over Addition it follows that $\struct {n \Z, +, \times}$ is a ring.
From Integer Multiplication is Commutative we have that $\struct {n \Z, +, \times}$ is a commutative ring.
So $\struct {n \Z, +, \times}$ is a commutative ring.
The unity of $\struct {\Z, +, \times}$ is $1$.
But unless $n = 1$, we have that $1 \notin n \Z$.
As $\struct {\Z, +, \times}$ is an integral domain, all its elements are cancellable, by the Cancellation Law for Ring Product of Integral Domain.
We have that Subrings of Integers are Sets of Integer Multiples.
From Identity of Cancellable Monoid is Identity of Submonoid it follows that $\struct {n \Z, +, \times}$ has no unity, because if it did, that unity would be $1$.
== Examples ==
== Sources ==
* : Chapter $1$: Rings - Definitions and Examples: $2$: Some examples of rings: Ring Example $1$
Category:Integers
Category:Commutative Rings
Category:Integer Multiples form Commutative Ring
Integer Multiples under Addition form Infinite Cyclic Group

== Theorem ==
Let $n \Z$ be the set of integer multiples of $n$.
Then $\struct {n \Z, +}$ is a countably infinite cyclic group.
It is generated by $n$ and $-n$:
:$n \Z = \gen n$
:$n \Z = \gen {-n}$
Hence $\struct {n \Z, +}$ can be justifiably referred to as the additive group of integer multiples.
== Proof ==
From Integer Multiples under Addition form Subgroup of Integers, $\struct {n \Z, +}$ is a subgroup of the additive group of integers $\struct {\Z, +}$.
From Integers under Addition form Infinite Cyclic Group, $\struct {\Z, +}$ is a cyclic group.
So by Subgroup of Cyclic Group is Cyclic, $\struct {n \Z, +}$ is a cyclic group.
The final assertions follow from Subgroup of Infinite Cyclic Group is Infinite Cyclic Group.
== Also see ==
* Definition:Additive Group of Integer Multiples
== Sources ==
* : $\S 5.4$. Cyclic groups: Example $99$
Category:Additive Groups of Integer Multiples
Category:Infinite Cyclic Group
Category:Sets of Integer Multiples
Integer Multiples under Addition form Subgroup of Integers

== Theorem ==
Let $\struct {\Z, +}$ denote the additive group of integers.
Let $n \Z$ be the set of integer multiples of $n$.
Then $\struct {n \Z, +}$ is a subgroup of $\struct {\Z, +}$.
Hence $\struct {n \Z, +}$ can be justifiably referred to as the additive group of integer multiples.
== Proof ==
Clearly $0 \in n \Z$ so $n \Z \ne \O$.
Now suppose $x, y \in n \Z$.
Then $\exists r, s \in \Z: x = n r, y = n s$.
Also, $-y = - n s$.
So $x - y = n \paren {r - s}$.
As $r - s \in \Z$ it follows that $x - y \in n \Z$.
So by the One-Step Subgroup Test it follows that $\struct {n \Z, +}$ is a subgroup of the additive group of integers $\struct {\Z, +}$.
== Also see ==
* Definition:Additive Group of Integer Multiples
== Sources ==
* : $\S 5.2$. Subgroups: Example $92$
* : Chapter $5$: Cosets and Lagrange's Theorem: Example $5.7$
Category:Additive Groups of Integer Multiples
Category:Additive Group of Integers
Integer Multiples under Multiplication form Semigroup

== Theorem ==
Let $n \Z$ be the set of integer multiples of $n$.
Then $\struct {n \Z, \times}$ is a semigroup.
If $\size n > 1$ then $\struct {n \Z, \times}$ has no identity.
== Proof ==
=== Closure ===
Let $p, q \in n \Z$.
Then for some $p', q' \in \Z$:
:$p = n p'$
:$q = n q'$
Hence:
:$p q = \paren {n p'} \paren {n q'}$
By the commutativity and associativity of integer multiplication:
:$p q = n \paren {n \paren {p' q'} }$
Hence $p q \in n \Z$ and $n \Z$ is closed under $\times$.
=== Assocativity ===
By definition $n \Z \subseteq \Z$.
Hence $\times$ is associative on $n \Z$ as a direct results of Restriction of Associative Operation is Associative.
=== Identity Element ===
If $\size n = 1$ then $\paren {n \Z, \times}$ is a monoid from Integers under Multiplication form Countably Infinite Commutative Monoid.
If $n \ne 1$ then $\left({n \Z, \times}\right)$ is a semigroup but not a monoid as it is without an identity as $1 \notin n \Z$.
== Sources ==
* : $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups
* : $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups: Exercise $1$
* : $2$: Examples of Groups and Homomorphisms: $13$
Category:Sets of Integer Multiples
Category:Examples of Semigroups
Integer Multiplication Distributes over Addition

== Theorem ==
The operation of multiplication on the set of integers $\Z$ is distributive over addition:
:$\forall x, y, z \in \Z: x \times \paren {y + z} = \paren {x \times y} + \paren {x \times z}$
:$\forall x, y, z \in \Z: \paren {y + z} \times x = \paren {y \times x} + \paren {z \times x}$
=== Corollary ===
== Proof ==
Let us define $\Z$ as in the formal definition of integers.
That is, $\Z$ is an inverse completion of $\N$.
From Natural Numbers form Commutative Semiring, we have that:
:All elements of $\N$ are cancellable for addition
:Addition and multiplication are commutative and associative on the natural numbers $\N$
:Natural number multiplication is distributive over natural number addition.
The result follows from the Extension Theorem for Distributive Operations.
== Sources ==
* : Introduction $\S 5$: The system of integers
* : $\S 2.5$: Theorem $2.23: \ \text{(iii)}$
* : Chapter $\text {IV}$: Rings and Fields: $20$. The Integers
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: $\mathbf Z. \, 5$
* : $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization
* : $\S 1$
Category:Integer Addition
Category:Integer Multiplication
Category:Examples of Distributive Operations
Integer Multiplication Distributes over Addition/Corollary

== Corollary to Integer Multiplication Distributes over Addition ==
The operation of multiplication on the set of integers $\Z$ is distributive over subtraction:
:$\forall x, y, z \in \Z: x \times \paren {y - z} = \paren {x \times y} - \paren {x \times z}$
:$\forall x, y, z \in \Z: \paren {y - z} \times x = \paren {y \times x} - \paren {z \times x}$
== Proof ==
Category:Integer Multiplication
Category:Subtraction
Category:Examples of Distributive Operations
Integer Multiplication Identity is One

== Theorem ==
The identity of integer multiplication is $1$:
:$\exists 1 \in \Z: \forall a \in \Z: a \times 1 = a = 1 \times a$
== Proof ==
Let us define $\eqclass {\tuple {a, b} } \boxtimes$ as in the formal definition of integers.
That is, $\eqclass {\tuple {a, b} } \boxtimes$ is an equivalence class of ordered pairs of natural numbers under the congruence relation $\boxtimes$.
$\boxtimes$ is the congruence relation defined on $\N \times \N$ by $\tuple {x_1, y_1} \boxtimes \tuple {x_2, y_2} \iff x_1 + y_2 = x_2 + y_1$.
In order to streamline the notation, we will use $\eqclass {a, b} {}$ to mean $\eqclass {\tuple {a, b} } \boxtimes$, as suggested.
From the method of construction, $\eqclass {c + 1, c} {}$, where $c$ is any element of the natural numbers $\N$, is the isomorphic copy of $1 \in \N$.
To ease the algebra, we will take $\eqclass {1, 0} {}$ as a canonical instance of this equivalence class.
Thus it is to be shown that:
:$\forall a, b \in \N: \eqclass {a, b} {} \times \eqclass {1, 0} {} = \eqclass {a, b} {} = \eqclass {1, 0} {} \times \eqclass {a, b} {}$
From Natural Numbers form Commutative Semiring, we take it for granted that:
:addition and multiplication are commutative and associative on the natural numbers $\N$
:natural number multiplication is distributive over natural number addition.
So:
So:
:$\eqclass {a, b} {} \times \eqclass {1, 0} {} = \eqclass {a, b} {}$
The identity $\eqclass {a, b} {} = \eqclass {1, 0} {} \times \eqclass {a, b} {}$ is demonstrated similarly.
== Sources ==
* : $\S 2.5$: Theorem $2.24$
* : Chapter $\text {IV}$: Rings and Fields: $20$. The Integers: Theorem $20.10$
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: $\mathbf Z. \, 3$
* : $\S 1$
Category:Integer Multiplication
Integer Multiplication has Zero

== Theorem ==
The set of integers under multiplication $\struct {\Z, \times}$ has a zero element, which is $0$.
== Proof ==
Let us define $\eqclass {\tuple {a, b} } \boxminus$ as in the formal definition of integers.
That is, $\eqclass {\tuple {a, b} } \boxminus$ is an equivalence class of ordered pairs of natural numbers under the congruence relation $\boxminus$.
$\boxminus$ is the congruence relation defined on $\N \times \N$ by $\tuple {x_1, y_1} \boxminus \tuple {x_2, y_2} \iff x_1 + y_2 = x_2 + y_1$.
In order to streamline the notation, we will use $\eqclass {a, b} {}$ to mean $\eqclass {\tuple {a, b} } \boxminus$, as suggested.
From the method of construction, $\eqclass {c, c} {}$, where $c$ is any element of the natural numbers $\N$, is the identity of $\struct {\Z, +}$.
To ease the algebra, we will take $\eqclass {0, 0} {}$ as a canonical instance of this equivalence class.
We need to show that:
$\forall a, b, c \in \N: \eqclass {a, b} {} \times \eqclass {0, 0} {} = \eqclass {0, 0} {} = \eqclass {0, 0} {} \times \eqclass {a, b} {}$.
From Natural Numbers form Commutative Semiring, we can take it for granted that addition and multiplication are commutative on the natural numbers $\N$.
== Sources ==
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: Exercise $3$
Category:Integer Multiplication
Integer Multiplication is Associative

== Theorem ==
The operation of multiplication on the set of integers $\Z$ is associative:
:$\forall x, y, z \in \Z: x \times \paren {y \times z} = \paren {x \times y} \times z$
== Proof ==
From the formal definition of integers, $\eqclass {a, b} {}$ is an equivalence class of ordered pairs of natural numbers.
Let $x = \eqclass {a, b} {}$, $y = \eqclass {c, d} {}$ and $z = \eqclass {e, f} {}$ for some $x, y, z \in \Z$.
Then:
== Sources ==
* : Introduction $\S 5$: The system of integers
* : $\S 2.5$: Theorem $2.23: \ \text{(ii)}$
* : Chapter $\text {IV}$: Rings and Fields: $20$. The Integers: Theorem $20.10$
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: $\mathbf Z. \, 1$
* : $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization
* : $\S 1$
Category:Integer Multiplication
Category:Examples of Associative Operations‎
Category:Associative Law of Multiplication
Integer Multiplication is Closed

== Theorem ==
The set of integers is closed under multiplication:
:$\forall a, b \in \Z: a \times b \in \Z$
== Proof ==
Let us define $\eqclass {\tuple {a, b} } \boxminus$ as in the formal definition of integers.
That is, $\eqclass {\tuple {a, b} } \boxminus$ is an equivalence class of ordered pairs of natural numbers under the congruence relation $\boxminus$.
$\boxminus$ is the congruence relation defined on $\N \times \N$ by:
:$\tuple {x_1, y_1} \boxminus \tuple {x_2, y_2} \iff x_1 + y_2 = x_2 + y_1$
In order to streamline the notation, we will use $\eqclass {a, b} {}$ to mean $\eqclass {\tuple {a, b} } \boxminus$, as suggested.
Integer multiplication is defined as:
:$\forall a, b, c, d \in \N: \eqclass {a, b} {} \times \eqclass {c, d} {} = \eqclass {a c + b d, a d + b c} {}$
We have that:
:$\forall a, b, c, d \in \N: \eqclass {a, b} {} \in \Z, \eqclass {c, d} {} \in \Z$
Also:
:$\forall a, b, c, d \in \N: \eqclass {a, b} {} \times \eqclass {c, d} {} = \eqclass {a c + b d, a d + b c} {}$
But:
:$a c + b d \in \N, a d + b c \in \N$
So:
:$\forall a, b, c, d \in \N: \eqclass {a c + b d, a d + b c} {} \in \Z$
Therefore integer multiplication is closed.
== Sources ==
* : Chapter $1$: Integral Domains: $\S 2$. Operations: Example $1$
* : $1$: Complex Numbers: The Real Number System: $2$
* : $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization
* : $1$: Set Theory and Logic: $\S 4$: The Integers and the Real Numbers
Category:Integer Multiplication
Category:Algebraic Closure
Integer Multiplication is Commutative

== Theorem ==
The operation of multiplication on the set of integers $\Z$ is commutative:
:$\forall x, y \in \Z: x \times y = y \times x$
== Proof ==
From the formal definition of integers, $\eqclass {a, b} {}$ is an equivalence class of ordered pairs of natural numbers.
Let $x = \eqclass {a, b} {}$ and $y = \eqclass {c, d} {}$ for some $x, y \in \Z$.
Then:
== Sources ==
* : Introduction $\S 5$: The system of integers
* : $\S 2.5$: Theorem $2.23: \ \text{(i)}$
* : Chapter $\text {IV}$: Rings and Fields: $20$. The Integers: Theorem $20.10$
* : Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers: $\mathbf Z. \, 2$
* : $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization
* : $\S 1$
Category:Integer Multiplication
Category:Examples of Commutative Operations
Category:Commutative Law of Multiplication
Integer Multiplication is Well-Defined/Proof 1

== Theorem ==
== Proof ==
Let us define $\eqclass {\tuple {a, b} } \boxtimes$ as in the formal definition of integers.
That is, $\eqclass {\tuple {a, b} } \boxtimes$ is an equivalence class of ordered pairs of natural numbers under the congruence relation $\boxtimes$.
$\boxtimes$ is the congruence relation defined on $\N \times \N$ by $\tuple {x_1, y_1} \boxtimes \tuple {x_2, y_2} \iff x_1 + y_2 = x_2 + y_1$.
In order to streamline the notation, we will use $\eqclass {a, b} {}$ to mean $\eqclass {\tuple {a, b} } \boxtimes$, as suggested.
We need to show that $\eqclass {a, b} {} = \eqclass {p, q} {} \land \eqclass {c, d} {} = \eqclass {r, s} {} \implies \eqclass {a, b} {} \times \eqclass {c, d} {} = \eqclass {p, q} {} \times \eqclass {r, s} {}$.
We have $\eqclass {a, b} {} = \eqclass {p, q} {} \land \eqclass {c, d} {} = \eqclass {r, s} {} \iff a + q = b + p \land c + s = d + r$ by the definition of $\boxtimes$.
From the definition of integer multiplication, we have:
:$\forall a, b, c, d \in \N: \eqclass {a, b} {} \times \eqclass {c, d} {} = \eqclass {a c + b d, a d + b c} {}$
So, suppose that $\eqclass {a, b} {} = \eqclass {p, q} {}$ and $\eqclass {c, d} {} = \eqclass {r, s} {}$.
Both $+$ and $\times$ are commutative and associative on $\N$. Thus:
So we have $a c + b d + p s + q r = a d + b c + p r + q s$ and so, by the definition of $\boxtimes$, we have:
:$\eqclass {a c + b d, a d + b c} {} = \eqclass {p r + q s, p s + q r} {}$
So, by the definition of integer multiplication, this leads to:
:$\eqclass {a, b} {} \times \eqclass {c, d} {} = \eqclass {p, q} {} \times \eqclass {r, s} {}$
Thus integer multiplication has been shown to be well-defined.
== Sources ==
* : Introduction $\S 5$: The system of integers
Category:Integer Multiplication is Well-Defined
Integer Multiplication is Well-Defined/Proof 2

== Theorem ==
== Proof ==
Consider the formal definition of the integers: $x = \eqclass {a, b} {}$ is an equivalence class of ordered pairs of natural numbers.
Consider the mapping $\phi: \N_{>0} \to \Z_{>0}$ defined as:
:$\forall u \in \N_{>0}: \map \phi u = u'$
where $u' \in \Z$ is the (strictly) positive integer $\eqclass {b + u, b} {}$.
Let:
:$v' = \eqclass {c + v, c} {}$
Then:
== Sources ==
* : Introduction $\S 5$: The system of integers
Category:Integer Multiplication is Well-Defined
Integer Partition/Examples/4

== Examples of Integer Partitions ==
The integer $4$ can be partitioned as follows:
:$4$
:$3 + 1$
:$2 + 2$
:$2 + 1 + 1$
:$1 + 1 + 1 + 1$
== Sources ==
* : Chapter $\text {A}.21$: Euler ()
* 
* 
Category:Examples of Integer Partitions
Integer Partition/Examples/5

== Examples of Integer Partitions ==
The integer $5$ can be partitioned as follows:
:$5$
:$4 + 1$
:$3 + 2$
:$3 + 1 + 1$
:$2 + 2 + 1$
:$2 + 1 + 1 + 1$
:$1 + 1 + 1 + 1 + 1$
== Sources ==
* : $\text {3-5}$ The Use of Computers in Number Theory: Exercise $8$
* : $\S 1.2.1$: Mathematical Induction
* 
Category:Examples of Integer Partitions
Integer Partition/Table

== Table of Integer Partitions ==
The following table presents a list of the number of integer partitions for all $n$ from $1$ to $30$.
In the following, $\map p n$ denotes the number of integer partitions for $n$.
:$\begin{array} {|r|r|}
\hline
n & \map p n \\
\hline
1 & 1 \\
2 & 2 \\
3 & 3 \\
4 & 5 \\
5 & 7 \\
6 & 11 \\
7 & 15 \\
8 & 22 \\
9 & 30 \\
10 & 42 \\
11 & 56 \\
12 & 77 \\
13 & 101 \\
14 & 135 \\
15 & 176 \\
16 & 231 \\
17 & 297 \\
18 & 385 \\
19 & 490 \\
20 & 627 \\
21 & 792 \\
22 & 1002 \\
23 & 1255 \\
24 & 1575 \\
25 & 1958 \\
26 & 2436 \\
27 & 3010 \\
28 & 3718 \\
29 & 4565 \\
30 & 5604 \\
\hline
\end{array}$
== Sources ==
* : $\text {3-5}$ The Use of Computers in Number Theory: Exercise $8$
* : $\S 1.2.1$: Mathematical Induction
* 
Category:Examples of Integer Partitions
Integer Power Function is Bijective iff Index is Odd

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $f_n: \R \to \R$ be the real function defined as:
:$\map {f_n} x = x^n$
Then $f_n$ is a bijection $n$ is odd.
== Proof ==
=== Even Index ===
Suppose $n$ is even.
Let $x \ne 0$.
Then $1^n = \paren {-1}^n$ by Power of Ring Negative, so $f_n$ is not injective.
Also, by Even Power is Non-Negative, $f_n$ is not surjective.
By definition, a bijection is both injective and surjective.
It follows that for even $n$, $f_n$ is not bijective.
=== Odd Index ===
Now suppose $n$ is odd.
From Odd Power Function is Strictly Increasing, $f_n$ is injective.
From Odd Power Function is Surjective, $f^n$ is surjective.
So when $n$ is odd, $f_n$ is both injective and surjective, and so by definition bijective.
Hence the result.
== Sources ==
* : Chapter $1$: Mappings: $\S 12 \beta$
Category:Real Functions
Category:Powers
Category:Bijections
Integer Power of Root of Unity is Root of Unity

== Theorem ==
Let $n \in \Z_{> 0}$ be a strictly positive integer.
Let $F$ be a field.
Let $\alpha$ be an $n$-th root of unity.
Let $k \in \Z$.
Then:
:$\alpha^k$ is an $n$-th root of unity.
== Proof ==
We have:
Category:Roots of Unity