nyuuzyou/wikis huggingface dataset:
Integer as Sum of Three Squares

== Theorem ==
Let $r$ be a positive integer.
Then $r$ can be expressed as the sum of three squares it is not of the form:
:$4^n \paren {8 m + 7}$
for some $m, n \in \Z_{\ge 0}$.
=== Sequence ===
== Proof ==
=== Sufficient Condition ===
Suppose $r$ is not of the form $4^n \paren {8 m + 7}$.
Then we need to show that it can always be expressed as the sum of three squares.
=== Necessary Condition ===
From Square Modulo 8, the squares modulo $8$ are $0, 1$ and $4$.
So the sum of three squares can be congruent modulo $8$ to any of the values $0, 1, 2, 3, 4, 5$ or $6$, but not $7$.
So no number of the form $8 m + 7$ can be the sum of three squares.
Now, suppose that $\exists n \ge 1, m \ge 0$ such that:
:$4^n \paren {8 m + 7} = x^2 + y^2 + z^2$
As the is congruent modulo 4 to $0$, and as squares modulo 4 are either $0$ or $1$, it must be that $x, y$ and $z$ are all even.
Putting $x = 2 x_1, y = 2 y_1, z = 2 z_1$, we get:
:$4^{n - 1} \paren {8 m + 7} = x_1^2 + y_1^2 + z_1^2$
If $n - 1 > 1$ then $x_1, y_1$ and $z_1$ are all still even, and the argument can be repeated:
:$4^{n - 2} \paren {8 m + 7} = x_2^2 + y_2^2 + z_2^2$
Thus we descend through all powers of $4$ till $8 m + 7$ itself is expressed as the sum of three squares.
But this is impossible, as we saw above.
So the assumption that $4^n \paren {8 m + 7}$ can be expressed as the sum of three squares is false.
== Sources ==
* : $\text {3-5}$ The Use of Computers in Number Theory: Exercise $4$
* : $3$
* : $4$
* : $3$
* : $4$
* 
* 
Category:Sums of Squares
Integer as Sum of Two Squares

== Theorem ==
Let $n$ be a positive integer.
Then:
: $n$ can be expressed as the sum of two squares
:
:each of its prime divisors of the form $4 k + 3$ (if any) occur to an even power.
== Proof ==
Let us extract the largest square divisor of $n$, and write:
:$n = m^2 r$
where $r$ is square-free.
=== Necessary Condition ===
Suppose $r$ has no prime divisor in the form $4 k + 3$.
If $r = 1$ then $n^2 = m^2 + 0^2$ and nothing needs to be proved.
If $r > 1$ then $r$ is a product of one or more primes, each of which is either $2$ or in the form $4 k + 1$.
Now from Fermat's Two Squares Theorem, each of these can be expressed as the sum of two squares.
By the extension to the Brahmagupta-Fibonacci Identity, the product of all these can itself be expressed as the sum of two squares.
So $r = a^2 + b^2$, say.
Then:
:$n = m^2 \paren {a^2 + b^2} = \paren {m a}^2 + \paren {m b}^2$
So $n$ can be expressed as the sum of two squares.
=== Sufficient Condition ===
Now suppose that $n$ can be expressed as the sum of two squares, say:
:$n = m^2 r = a^2 + b^2$
First, any common divisor of $a$ and $b$ may be cancelled as follows.
If $\gcd \set {a, b} = d$, then we can write:
:$a = a' d, b = b' d$
where $\gcd \set {a', b'} = 1$ from Integers Divided by GCD are Coprime.
So:
:$m^2 r = d^2 \paren {a'^2 + b'^2}$
As $r$ is square-free, $d \divides m$ and so, writing $m' = \dfrac m d$, we get:
:$m'^2 r = a'^2 + b'^2$
We need to show that $r$ has no prime factor of the form $4 k + 3$.
 $p = 4 k + 3$ divides $r$.
Then:
:$a'^2 + b'^2 \equiv 0 \implies a'^2 \equiv -b'^2 \pmod p$
If $p \divides a'$ we would have:
:$p \divides b'$
which contradicts $\gcd \set {a', b'} = 1$.
So:
:$\gcd \set {a', p} = \gcd \set {b', p} = 1$
and we can apply Fermat's Little Theorem:
:$a'^{p-1} \equiv b'^{p-1} \equiv 1 \pmod p$
So, we put $p = 4 k + 3$:
$-1 \equiv 1 \pmod p$ is not possible for an odd prime.
So we have obtained our contradiction.
The result follows.
== Sources ==
* : Chapter $7$: Patterns in Numbers: Fermat
Category:Sums of Squares
Integer as Sums and Differences of Consecutive Squares

== Theorem ==
Every integer $k$ can be represented in infinitely many ways in the form:
:$k = \pm 1^2 \pm 2^2 \pm 3^3 \pm \dots \pm m^2$
for some (strictly) positive integer $m$ and some choice of signs $+$ or $-$.
== Proof ==
First we notice that:
Now we prove a weaker form of the theorem by induction:
:Every positive integer $k$ can be represented in at least one way in the form:
::$k = \pm 1^2 \pm 2^2 \pm 3^3 \pm \dots \pm m^2$
:for some (strictly) positive integer $m$ and some choice of signs $+$ or $-$.
=== Basis for the Induction ===
From the identity above we have:
Also we have, more or less trivially:
:$1 = + 1^2$
:$2 = - 1^2 - 2^2 - 3^2 + 4^2$
:$3 = - 1^2 + 2^2$
This is the basis for the induction.
=== Induction Hypothesis ===
This is the induction hypothesis:
:For some positive integer $k$, we have:
::$k = \pm 1^2 \pm 2^2 \pm 3^3 \pm \dots \pm m^2$
:for some (strictly) positive integer $m$ and some choice of signs $+$ or $-$.
Now we need to show true for $n = k + 4$:
::$k + 4 = \pm 1^2 \pm 2^2 \pm 3^3 \pm \dots \pm {m_2}^2$
:for some (strictly) positive integer $m_2$ and some choice of signs $+$ or $-$.
=== Induction Step ===
This is the induction step:
which is of the required form.
Hence every positive integer $k$ can be represented in at least one way in the required form.
From the identity above we can also conclude:
therefore if $k$ can be written as:
:$k = \pm 1^2 \pm 2^2 \pm 3^3 \pm \dots \pm m^2$
it can also be written as:
:$k = \pm 1^2 \pm 2^2 \pm 3^3 \pm \dots \pm m^2 + \paren {m + 1}^2 - \paren {m + 2}^2 - \paren {m + 3}^2 + \paren {m + 4}^2 - \paren {m + 5}^2 + \paren {m + 6}^2 + \paren {m + 7}^2 - \paren {m + 8}^2$
and:
:$k = \pm 1^2 \pm 2^2 \pm 3^3 \pm \dots \pm \paren {m + 8}^2 + \paren {m + 9}^2 - \paren {m + 10}^2 - \paren {m + 11}^2 + \paren {m + 12}^2 - \paren {m + 13}^2 + \paren {m + 14}^2 + \paren {m + 15}^2 - \paren {m + 16}^2$
and so on.
Hence every positive integer $k$ can be represented in infinitely many ways in the required form.
Finally we cover the case where $k$ is a negative integer.
Since $-k$ is a positive integer, it can be represented in infinitely many ways in the required form.
For every representation of $-k$ in this way, by flipping every $+$ and $-$ sign, we end up with a representation of $- \paren {- k} = k$.
Hence every integer $k$, positive or negative, can be represented in infinitely many ways in the required form.
== Example ==
== Also see ==
* Definition:Erdős-Surányi Sequence
== Historical Note ==
== Sources ==
* : No. $250$
Category:Squares
Category:Integer as Sums and Differences of Consecutive Squares
Integer as Sums and Differences of Consecutive Squares/Examples

== Example of use of Integer as Sums and Differences of Consecutive Squares ==
Since the proof above is constructive, we can follow the proof and derive:
and its associated family of solutions:
and so on.
However this may not give the least number of squares that this works for.
In fact we have:
from Triangular Number as Alternating Sum and Difference of Squares.
Category:Integer as Sums and Differences of Consecutive Squares
Integer both Square and Triangular

== Theorem ==
Consider a pair of (strictly) positive integers $m$ and $n$ such that $n < m$.
Then:
:$\dfrac m n$ is a best rational approximation to the square root of $2$
:
:$\paren {m n}^2$ is both square and triangular.
== Proof ==
== Examples ==
== Sources ==
* : $36$
* : $36$
Category:Square Numbers
Category:Triangular Numbers
Category:Square Root of 2
Category:Integer both Square and Triangular
Integer both Square and Triangular/Examples

== Examples of Integer both Square and Triangular ==
The following integers are both square and triangular:
:
$\paren {m n}^2$ 	$m$ 	$2 n^2 \pm 1 = m^2$ 	$\dfrac {2 n^2 \paren {2 n^2 \pm 1} } 2$	$m n$ 	$\dfrac m n$
$1 = 1^2$ 	$1$ 	$2 = 2 \times 1^2 - 1$ 	$\dfrac {2 \times \paren {2 - 1} } 2$ 	$1 = 1 \times 1$ 	$1$
$36 = 6^2$ 	$3$ 	$9 = 2 \times 2^2 + 1$ 	$\dfrac {8 \paren {8 + 1} } 2$ 	$6 = 3 \times 2$ 	$1 \cdotp 5$
$1225 = 35^2$ 	$7$ 	$49 = 2 \times 5^2 - 1$ 	$\dfrac {50 \paren {50 - 1} } 2$ 	$35 = 7 \times 5$ 	$1 \cdotp 4$
$41 \, 616 = 204^2$	$17$	$289 = 2 \times 12^2 + 1$	$\dfrac {288 \paren {288 + 1} } 2$ 	$204 = 17 \times 12$	$1 \cdotp 41 \dot 6$
== Sources ==
* : Chapter $1$: Some Preliminary Considerations: $1.3$ Early Number Theory: Problems $1.3$: $6 \ \text {(b)}$
* : $36$
* : $36$
Category:Integer both Square and Triangular
Integer both Square and Triangular/Mistake

== Source Work ==
:
:The Dictionary
::$1225$
:
:The Dictionary
::$1225$
== Mistake ==
:It is the second number to be simultaneously square and triangular.
== Correction ==
To be technically accurate, it is in fact the $3$rd, after $1$ and $36$.
== Sources ==
* : $1225$
* : $1225$
Category:Mistakes/Curious and Interesting Numbers
Integer equals Ceiling iff Number between Integer and One Less

== Theorem ==
Let $x \in \R$ be a real number.
Let $\ceiling x$ be the ceiling of $x$.
Let $n \in \Z$ be an integer.
Then:
:$\ceiling x = n \iff n - 1 < x \le n$
== Proof ==
=== Necessary Condition ===
Let $n - 1 < x \le n$.
From Number not greater than Integer iff Ceiling not greater than Integer:
:$x \le n \implies \ceiling x \le n$
From Number is between Ceiling and One Less:
:$x \le \ceiling x$
and so:
:$n - 1 < \ceiling x$
We have that:
:$\forall m, n \in \Z: m - 1 < n \iff m \le n$
and so:
:$n \le \ceiling x$
So we have:
:$\ceiling x \le n$
and:
:$n \le \ceiling x$
Thus:
:$n - 1 < x \le n \implies \ceiling x = n$
=== Sufficient Condition ===
Let $\ceiling x = n$.
From Number is between Ceiling and One Less:
:$x \le \ceiling x$
and so:
:$x \le n$
Also from Number is between Ceiling and One Less:
:$\ceiling x - 1 < x$
and so:
:$n - 1 < x$
Thus:
:$\ceiling x = n \implies n - 1 < x \le n$.
Hence the result:
:$\ceiling x = n \iff n - 1 < x \le n$
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $3 \ \text{(f)}$
Category:Ceiling Function
Integer equals Ceiling iff between Number and One More

== Theorem ==
Let $x \in \R$ be a real number.
Let $\ceiling x$ be the ceiling of $x$.
Let $n \in \Z$ be an integer.
Then:
:$\ceiling x = n \iff x \le n < x + 1$
== Proof ==
=== Necessary Condition ===
Let $x \le n < x + 1$.
From $x \le n$, we have by Number not greater than Integer iff Ceiling not greater than Integer:
:$\ceiling x \le n$
From $n < x + 1$:
:$n - 1 < x$
Hence by Number greater than Integer iff Ceiling greater than Integer:
:$n - 1 < \ceiling x$
We have that:
:$\forall m, n \in \Z: m < n \iff m \le n - 1$
and so:
:$n \le \ceiling x$
Thus as:
:$\ceiling x \le n$
and:
:$\ceiling x \ge n$
it follows that:
:$\ceiling x = n$
=== Sufficient Condition ===
Let $\ceiling x = n$.
Then:
:$\ceiling x \le n$
By Number not greater than Integer iff Ceiling not greater than Integer:
:$x \le n$
From Number is between Ceiling and One Less:
:$\ceiling x - 1 < x$
and so adding $1$ to both sides:
:$\ceiling x < x + 1$
and so :
:$n < x + 1$
So:
:$\ceiling x = n \implies x \le n < x + 1$
Hence the result:
:$\ceiling x = n \iff x \le n < x + 1$
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $3 \ \text{(f)}$
Category:Ceiling Function
Integer equals Floor iff Number between Integer and One More

== Theorem ==
Let $x \in \R$ be a real number.
Let $\floor x$ denote the floor of $x$.
Let $n \in \Z$ be an integer.
Then:
:$\floor x = n \iff n \le x < n + 1$
== Proof ==
=== Necessary Condition ===
Let $n \le x < n + 1$.
From Number not less than Integer iff Floor not less than Integer:
:$n \le x \implies n \le \floor x$
By definition of the floor of $x$:
:$\floor x \le x$
and so by hypothesis:
:$\floor x < n + 1$
We have that:
:$\forall m, n \in \Z: m \le n \iff m < n + 1$
and so:
:$\floor x \le n$
So we have:
:$n \le \floor x$
and:
:$\floor x \le n$
Thus:
:$n \le x < n + 1 \implies \floor x = n$
=== Sufficient Condition ===
Let $\floor x = n$.
By definition of the floor of $x$:
:$\floor x \le x$
and so by hypothesis:
:$n \le x$
Also by definition of the floor of $x$:
:$x < \floor x + 1$
and so by hypothesis:
:$x < n + 1$
Thus:
:$\floor x = n \implies n \le x < n + 1$.
Hence the result:
:$\floor x = n \iff n \le x < n + 1$
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $3 \ \text{(e)}$
Category:Floor Function
Integer equals Floor iff between Number and One Less

== Theorem ==
Let $x \in \R$ be a real number.
Let $\floor x$ denote the floor of $x$.
Let $n \in \Z$ be an integer.
Then:
:$\floor x = n \iff x - 1 < n \le x$
== Proof ==
=== Necessary Condition ===
Let $x - 1 < n \le x$.
From $n \le x$, we have by Number not less than Integer iff Floor not less than Integer:
:$n \le \floor x$
From $x - 1 < n$:
:$x < n + 1$
Hence by Number less than Integer iff Floor less than Integer:
:$\floor x < n + 1$
We have that:
:$\forall m, n \in \Z: m \le n \iff m < n + 1$
and so:
:$\floor x \le n$
Thus as:
:$n \le \floor x$
and:
:$\floor x \le n$
it follows that:
:$\floor x = n$
=== Sufficient Condition ===
Let $\floor x = n$.
Then:
:$\floor x \ge n$
By Number not less than Integer iff Floor not less than Integer:
:$n \le x$
By definition of the floor of $x$:
:$x < \floor x + 1$
and so subtracting $1$ from both sides:
:$x - 1 < \floor x$
and so by hypothesis:
:$x - 1 < n$
So:
:$\floor x = n \implies x - 1 < n \le x$
Hence the result:
:$\floor x = n \iff x - 1 < n \le x$
== Sources ==
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $3 \ \text{(e)}$
Category:Floor Function
Integer has Multiplicative Order Modulo n iff Coprime to n

== Theorem ==
Let $a$ and $n$ be integers.
Let the multiplicative order of $a$ modulo $n$ exist.
Then:
:$a \perp n$
that is, $a$ and $n$ are coprime.
== Proof ==
=== Necessary Condition ===
Suppose $c \in \Z_{>0}$ is the multiplicative order of $a$ modulo $n$.
Then by definition:
:$a^c \equiv 1 \pmod n$
Hence, by definition:
:$a^c = k n + 1$
for some $k \in \Z$.
Thus:
:$a r + n s = 1$
where:
:$r = a^{c - 1}$
:$s = -k$
It follows from Integer Combination of Coprime Integers that $a$ and $n$ are coprime.
=== Sufficient Condition ===
Suppose $a \perp n$.
Then by Euler's Theorem (Number Theory):
:$a^{\map \phi n} \equiv 1 \pmod n$
where $\map \phi n$ is the Euler Phi Function of $n$.
Hence the multiplicative order of $a$ modulo $n$ exists, by taking $c = \map \phi n$.
Category:Coprime Integers
Category:Modulo Arithmetic
Integer is Congruent Modulo Divisor to Remainder

== Theorem ==
Let $a \in \Z$.
Let $a$ have a remainder $r$ on division by $m$.
Then:
:$a \equiv r \pmod m$
where the notation denotes that $a$ and $r$ are congruent modulo $m$.
=== Corollary ===
== Proof ==
Let $a$ have a remainder $r$ on division by $m$.
Then:
:$\exists q \in \Z: a = q m + r$
Hence by definition of congruence modulo $m$:
:$a \equiv r \pmod m$
== Sources ==
* : $\S 14.2 \ \text{(i)}$: Congruence modulo $m$ ($m \in \N$)
Category:Modulo Arithmetic
Integer is Congruent Modulo Divisor to Remainder/Corollary

== Corollary to Integer is Congruent Modulo Divisor to Remainder ==
Let $a \equiv b \pmod m$ denote that $a$ and $b$ are congruent modulo $m$.
$a \equiv b \pmod m$ $a$ and $b$ have the same remainder when divided by $m$.
== Proof ==
Follows directly from:
: Integer is Congruent Modulo Divisor to Remainder
: Congruence Modulo Real Number is Equivalence Relation.
Category:Modulo Arithmetic
Integer is Congruent to Integer less than Modulus

== Theorem ==
Let $m \in \Z$.
Then each integer is congruent (modulo $m$) to precisely one of the integers $0, 1, \ldots, m - 1$.
== Proof ==
=== Proof of Existence ===
Let $a \in \Z$.
Then from the Division Theorem: $\exists r \in \set {0, 1, \ldots, m - 1}: a \equiv r \pmod m$.
=== Proof of Uniqueness ===
Suppose that:
:$\exists r_1, r_2 \in \set {0, 1, \ldots, m - 1}: a \equiv r_1 \pmod m \land a \equiv r_2 \pmod m$
Then:
:$\exists r_1, r_2 \in \Z: a = q_1 m + r_1 = q_2 m + r_2$
This contradicts the uniqueness clause in the Division Theorem.
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)}$
* : $\S 14.2 \ \text{(ii)}$: Congruence modulo $m$ ($m \in \N$)
Category:Modulo Arithmetic
Integer is Coprime to 1

== Theorem ==
Every integer is coprime to $1$.
That is:
:$\forall n \in \Z: n \perp 1$
== Proof ==
Follows from the definitions of coprime and greatest common divisor as follows.
When $n \in \Z: n \ne 0$ we have:
:$\gcd \set {n, 1} = 1$
Then by definition again:
:$\gcd \set {n, 0} = n$
and so when $n = 1$ we have:
:$\gcd \set {1, 0} = 1$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $10$
* : $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $12$
Category:Coprime Integers
Integer is Divisor Modulo m of Every Integer iff Coprime to m

== Theorem ==
Let $m, n \in \Z$ be integers.
Then:
:$n$ is coprime to $m$
:
:$n$ is a divisor modulo $m$ to every integer.
== Proof ==
== Sources ==
* 
* 
Category:Divisors Modulo Integer
Category:Modulo Division
Integer is Expressible as Product of Primes

== Theorem ==
Let $n$ be an integer such that $n > 1$.
Then $n$ can be expressed as the product of one or more primes.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Also see ==
* Expression for Integer as Product of Primes is Unique
== Sources ==
* : Chapter $\text {B}.2$: More about Numbers: Irrationals, Perfect Numbers and Mersenne Primes
* : Chapter $\text {B}.16$: The Sequence of Primes: Problem $1 \ \text{(a)}$
* : Chapter $7$: Patterns in Numbers: Euclid
Category:Integer is Expressible as Product of Primes
Category:Fundamental Theorem of Arithmetic
Category:Prime Decompositions
Category:Prime Numbers
Category:Factorization
Integer is Expressible as Product of Primes/Proof 1

== Theorem ==
== Proof ==
 this supposition is false.
Let $m$ be the smallest integer which can not be expressed as the product of primes.
As a prime number is trivially a product of primes, $m$ can not itself be prime.
Hence:
:$\exists r, s \in \Z: 1 < r < m, 1 < s < m: m = r s$
As $m$ is our least counterexample, both $r$ and $s$ can be expressed as the product of primes.
Say $r = p_1 p_2 \cdots p_k$ and $s = q_1 q_2 \cdots q_l$, where all of $p_1, \ldots, p_k, q_1, \ldots, q_l$ are prime.
Hence $m = r s = p_1 p_2 \cdots p_k q_1 q_2 \cdots q_l$, which is a product of primes.
Hence there is no such counterexample.
== Sources ==
* : $\S 13.1$: The fundamental theorem of arithmetic
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Theorem $4$
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $6$
* : $\S 1.14$: Exercise $19 \ \text{(c)}$
Category:Integer is Expressible as Product of Primes
Integer is Expressible as Product of Primes/Proof 2

== Theorem ==
== Proof ==
If $n$ is prime, the result is immediate.
Let $n$ be composite.
Then by Composite Number has Two Divisors Less Than It:
:$\exists r, s \in \Z: n = r s, 1 < r < n, 1 < s < n$
This being the case, the set $S_1 = \set {d: d \divides n, 1 < d < n}$ is nonempty, and bounded below by $1$.
By Set of Integers Bounded Below by Integer has Smallest Element, $S_1$ has a smallest element, which we will call $p_1$.
 $p_1$ is composite.
By Composite Number has Two Divisors Less Than It, there exist $a, b$ such that $a, b \divides p_1$ and $1 < a < p_1, 1 < b < p_1$.
But by Divisor Relation on Positive Integers is Partial Ordering, it follows that $a, b \divides n$ and hence $a, b \in S_1$.
This contradicts the assertion that $p_1$ is the smallest element of $S_1$.
Thus, $p_1$ is necessarily prime.
We may now write $n = p_1 n_1$, where $n > n_1 > 1$.
If $n_1$ is prime, the proof is complete.
Otherwise, the set $S_2 = \set {d: d \divides n_1, 1 < d < n_1}$ is nonempty, and bounded below by $1$.
By the above argument, the smallest element $p_2$ of $S_2$ is prime.
Thus we may write $n_1 = p_2 n_2$, where $1 < n_2 < n_1$.
This gives us $n = p_1 p_2 n_2$.
If $n_2$ is prime, we are done.
Otherwise, we continue this process.
Since $n > n_1 > n_2 > \cdots > 1$ is a (strictly) decreasing sequence of positive integers, there must be a finite number of $n_i$'s.
That is, we will arrive at some prime number $n_{k - 1}$, which we will call $p_k$.
This results in the prime decomposition $n = p_1 p_2 \cdots p_k$.
== Sources ==
* : $\text I$: The Series of Primes: $1.2$ Prime numbers: Theorem $1$
Category:Integer is Expressible as Product of Primes
Integer is Expressible as Product of Primes/Proof 3

== Theorem ==
== Proof ==
The proof proceeds by induction.
For all $n \in \N_{> 1}$, let $\map P n$ be the proposition:
:$n$ can be expressed as a product of prime numbers.
First note that if $n$ is prime, the result is immediate.
=== Basis for the Induction ===
$\map P 2$ is the case:
:$n$ can be expressed as a product of prime numbers.
As $2$ itself is a prime number, and the result is immediate.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P j$ is true, for all $j$ such that $2 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:For all $j \in \N$ such that $2 \le j \le k$, $j$ can be expressed as a product of prime numbers.
from which it is to be shown that:
:$k + 1$ can be expressed as a product of prime numbers.
=== Induction Step ===
This is the induction step:
If $k + 1$ is prime, then the result is immediate.
Otherwise, $k + 1$ is composite and can be expressed as:
:$k + 1 = r s$
where $2 \le r < k + 1$ and $2 \le s < k + 1$
That is, $2 \le r \le k$ and $2 \le s \le k$.
Thus by the induction hypothesis, both $r$ and $s$ can be expressed as a product of primes.
So $k + 1 = r s$ can also be expressed as a product of primes.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Second Principle of Mathematical Induction.
Therefore, for all $n \in \N_{> 1}$:
:$n$ can be expressed as a product of prime numbers.
== Sources ==
* : $\text {2-4}$ The Fundamental Theorem of Arithmetic: Theorem $\text {2-5}$
* : $\S 1.2.1$: Mathematical Induction: Exercise $5$
Category:Integer is Expressible as Product of Primes
Integer is Sum of Three Triangular Numbers

== Theorem ==
Let $n$ be a positive integer.
Then $n$ is the sum of $3$ triangular numbers.
== Proof ==
From Integer as Sum of Three Odd Squares, $8 n + 3$ is the sum of $3$ odd squares.
So:
By Closed Form for Triangular Numbers, each of $\dfrac {x \paren {x + 1} } 2$, $\dfrac {y \paren {y + 1} } 2$ and $\dfrac {z \paren {z + 1} } 2$ are triangular numbers.
== Also known as ==
This theorem is often referred to as Gauss's Eureka Theorem, from 's famous diary entry.
== Historical Note ==
== Sources ==
* : $3$
* : $3$
Category:Triangular Numbers
Integer is Sum of Three Triangular Numbers/Historical Note

== Historical Note on Integer is Sum of Three Triangular Numbers ==
 proved that every Integer is Sum of Three Triangular Numbers.
The $18$th entry in his diary, dated $10$th July $1796$, made when he was $19$ years old, reads:
:$**\Epsilon\Upsilon\Rho\Eta\Kappa\Alpha \quad \text{num} = \Delta + \Delta + \Delta.$
== Sources ==
* : $3$
* : $3$
Category:Historical Notes
Integer of form 6k + 5 is of form 3k + 2 but not Conversely

== Theorem ==
Let $n \in \Z$ be an integer of the form:
:$n = 6 k + 5$
where $k \in \Z$.
Then $n$ can also be expressed in the form:
:$n = 3 k + 2$
for some other $k \in \Z$.
However it is not necessarily the case that if $n$ can be expressed in the form:
:$n = 3 k + 2$
then it can also be expressed in the form:
:$n = 6 k + 5$
== Proof ==
Replacing $2 k + 1$ with $k$ gives the result.
Now consider $n = 8$.
We have that:
:$8 = 3 \times 2 + 2$
and so can be expressed in the form:
:$n = 3 k + 2$
However:
:$8 = 6 \times 1 + 2$
and is in the form:
:$n = 6 k + 2$
and so cannot be expressed in the form:
:$n = 6 k + 5$
== Sources ==
* : Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Problems $2.1$: $2$
Category:Modulo Arithmetic
Integer to Power of Itself Less One Falling is Factorial

== Theorem ==
Let $n \in \Z_{\ge 0}$ be a positive integer.
:$n^{\underline {n - 1} } = n!$
where:
:$n^{\underline {n - 1} }$ denotes the falling factorial
:$n!$ denotes the factorial.
== Proof ==
Category:Falling Factorials