nyuuzyou/wikis huggingface dataset:
Integers such that all Coprime and Less are Prime

== Theorem ==
The following positive integers have the property that all positive integers less than and coprime to it, excluding $1$, are prime:
:$1, 2, 3, 4, 6, 8, 12, 18, 24, 30$
There are no other positive integers with this property.
== Proof ==
Let $S_n$ denote the set of all positive integers less than and coprime to $n$, excluding $1$.
Let $\map P n$ denote the propositional function:
:All positive integers less than and coprime to $n$, excluding $1$, are prime.
We establish that $\map P n = \T$ for all the positive integers given:
From Schatunowsky's Theorem:
:$30$ is the greatest positive integer $n$ such that $\map P n$ is true
We note that for all primes $p$ greater than $3$, $p - 1$ is composite, and so $\map P p = \F$.
The remaining composite numbers less than $30$ are investigated:
That exhausts the list.
Hence the result.
== Sources ==
* : $\text {4-2}$ Residue Systems: Exercise $4$
* : $30$
* : $30$
Category:Euler Phi Function
Integers under Addition form Abelian Group

== Theorem ==
The set of integers under addition $\struct {\Z, +}$ forms an abelian group.
== Proof ==
From the definition of the integers, the algebraic structure $\struct {\Z, +}$ is an isomorphic copy of the inverse completion of $\struct {\N, +}$.
From Natural Numbers under Addition form Commutative Semigroup, $\struct {\N, +}$ is a commutative semigroup.
From Natural Number Addition is Cancellable all elements of $\struct {\N, +}$ are cancellable.
The result follows from Inverse Completion of Commutative Semigroup is Abelian Group.
Thus addition on $\Z$ is well-defined, closed, associative and commutative on $\Z$.
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.
=== Identity is Zero ===
From Construction of Inverse Completion: Identity of Quotient Structure, the identity of $\struct {\Z, +}$ is $\eqclass {c, c} {}$ for any $c \in \N$:
$\eqclass {c, c} {}$ is the equivalence class of pairs of elements $\N \times \N$ whose difference is zero.
Thus the identity of $\struct {\Z, +}$ is seen to be $0$.
Note that a perfectly good representative of $\eqclass {c, c} {}$ is $\eqclass {0, 0} {}$.
This usually keeps to a minimum the complexity of any arithmetic that is needed.
=== Construction of Inverses ===
From Construction of Inverse Completion: Invertible Elements in Quotient Structure, we see that every element of $\struct {\Z, +}$ has an inverse.
We can see that:
The above construction is valid because $a$ and $b$ are both in $\N$ and hence cancellable.
From Construction of Inverse Completion: Identity of Quotient Structure, $\eqclass {a + b, a + b} {}$ is a member of the equivalence class which is the identity of $\struct {\Z, +}$.
Thus the inverse of $\eqclass {a, b} {}$ is $\eqclass {b, a} {}$.
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 3$: Examples of Infinite Groups: $\text{(ii)}$
* : $\S 4.5$. Examples of groups: Example $80$
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Example $7.1$
* : $\S 1.3$: Example $1$
* : $\S 1$: Some examples of groups: Example $1.01$
* : Chapter $2$: Examples of Group Structure: $\S 32$
* : Chapter $4$: Mappings: Exercise $9$
* : $\S 34$. Examples of groups: $(1)$
* : $\S 3.2$: Groups; the axioms: Examples of groups $\text{(i)}$
* : $1$ Divisibility: $1.1$ The Euclidean algorithm and unique factorization
* 
* 
* : Chapter $1$: Basic Definitions and Results
* 
* 
* : $\S 1.5$
* : $\S 1.1$: Example $1$
Category:Additive Group of Integers
Category:Integer Addition
Category:Examples of Abelian Groups
Integers under Addition form Group

== Theorem ==
The set of integers under addition $\struct {\Z, +}$ forms a group.
== Proof ==
From Integers under Addition form Abelian Group, $\struct {\Z, +}$ forms an abelian group.
An abelian group is a group.
Hence the result.
== Sources ==
* 
* 
Category:Additive Group of Integers
Integers under Addition form Infinite Cyclic Group

== Theorem ==
The additive group of integers $\struct {\Z, +}$ is an infinite cyclic group which is generated by the element $1 \in \Z$.
== Proof ==
By Epimorphism from Integers to Cyclic Group and integer multiplication:
:$\forall n \in \Z: n = \map {+^n} 1 \in \gen 1$
Thus:
:$\struct {\Z, +} = \gen 1$
and thus, by the definition of a cyclic group, is cyclic.
== Sources ==
* : $\S 5.3$. Subgroup generated by a subset: Example $98$
* : Chapter $\text {IV}$: Rings and Fields: $25$. Cyclic Groups and Lagrange's Theorem: Theorem $25.2$
* : Chapter $\text{II}$: Groups: A Little Number Theory
* : Chapter $2$: Subgroups and Cosets: $\S 43$
* : $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups
* : $\S 1.2$
* : $\S 3.4$: Cyclic groups
Category:Infinite Cyclic Group
Category:Integer Addition
Category:Additive Group of Integers
Integers under Addition form Monoid

== Theorem ==
The set of integers under addition $\struct {\Z, +}$ forms a monoid.
== Proof ==
Follows directly from Integers under Addition form Abelian Group.
By definition, an abelian group is a group.
Also by definition, a group is a monoid.
Hence the result.
== Sources ==
* : $\S 3.1$: Monoids
Category:Integer Addition
Category:Examples of Monoids
Integers under Addition form Semigroup

== Theorem ==
The set of integers under addition $\struct {\Z, +}$ forms a semigroup.
== Proof ==
=== Closure ===
Integer Addition is Closed.
=== Associativity ===
Integer Addition is Associative.
The criteria for $\struct {\Z, +}$ to be a semigroup are seen to be satisfied. 
== Sources ==
* : Chapter $\text{I}$: Semi-Groups and Groups: $1$: Definition and examples of semigroups: Example $4$
* : $\S 29$. Semigroups: definition and examples
Category:Integer Addition
Category:Examples of Semigroups
Integers under Addition form Totally Ordered Group

== Theorem ==
Let $\struct {\Z, +}$ denote the additive group of integers.
Let $\le$ be the usual ordering on $\Z$.
Then the ordered structure $\struct {\Z, +, \le}$ is a totally ordered group.
== Proof ==
=== $\struct {\Z, +, \le}$ is an Ordered Structure ===
==== $(1)$ ====
By Integer Addition is Closed, $\struct {\Z, +}$ is an algebraic structure.
==== $(2)$ ====
$\le$ is an ordering on $\Z$.
Thus, $\struct {\Z, \le}$ is an ordered set.
==== $(3)$ ====
By Ordering is Preserved on Integers by Addition and Integer Addition is Commutative, $\le$ is compatible with $+$.
Thus, $\struct {\Z, +, \le}$ is an ordered structure.
=== $\struct {\Z, +, \le}$ is a Totally Ordered Structure ===
By definition, the ordered structure $\struct {\Z, +, \le}$ is a totally ordered structure $\le$ is a total ordering.
This follows from Ordering on Integers is Total Ordering.
=== $\struct {\Z, +, \le}$ is a Totally Ordered Group ===
By definition, the totally ordered structure $\struct {\Z, +, \le}$ is a totally ordered group $\struct {\Z, +}$ is a group.
This follows from Integers under Addition form Abelian Group.
Category:Integer Addition
Category:Additive Group of Integers
Integers under Multiplication do not form Group

== Theorem ==
The set of integers under multiplication $\struct {\Z, \times}$ does not form a group.
== Proof ==
In order to be classified as a group, the algebraic structure $\struct {\Z, \times}$ needs to fulfil the group axioms.
From Integers under Multiplication form Monoid, $\struct {\Z, \times}$ forms a monoid.
Therefore , and are satisfied.
However, from Invertible Integers under Multiplication, the only integers with inverses under multiplication are $1$ and $-1$.
As not all integers have inverses, it follows that $\struct {\Z, \times}$ is not a group.
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Algebraic Structures: $\S 7$: Semigroups and Groups: Example $7.2$
* : Chapter $1$: Definitions and Examples: Example $1.5$
Category:Integer Multiplication
Category:Examples of Groups
Integers under Multiplication form Countably Infinite Commutative Monoid

== Theorem ==
The set of integers under multiplication $\struct {\Z, \times}$ is a countably infinite commutative monoid.
== Proof ==
First we note that Integers under Multiplication form Monoid.
Then we have: 
=== Commutativity ===
Integer Multiplication is Commutative.
=== Infinite ===
Integers are Countably Infinite.
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Example $7.2$
* : $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups
* : $2$: Examples of Groups and Homomorphisms: $14$
Category:Integer Multiplication
Category:Examples of Commutative Monoids
Integers under Multiplication form Countably Infinite Semigroup

== Theorem ==
The set of integers under multiplication $\struct {\Z, \times}$ is a countably infinite semigroup.
== Proof ==
From Integers under Multiplication form Semigroup, $\struct {\Z, \times}$ is a countably infinite semigroup.
Then we have that the Integers are Countably Infinite.
The criteria for $\struct {\Z, \times}$ to be a countably infinite semigroup are seen to be satisfied. 
Category:Integer Multiplication
Category:Examples of Semigroups
Integers under Multiplication form Monoid

== Theorem ==
The set of integers under multiplication $\struct {\Z, \times}$ is a monoid.
== Proof ==
From Integers under Multiplication form Semigroup, $\struct {\Z, \times}$ is a semigroup.
From Integer Multiplication Identity is One, $\struct {\Z, \times}$ has an identity element, which is $1$.
All the criteria for being a monoid are thus seen to be fulfilled.
== Sources ==
* : $\S 3.1$: Monoids
Category:Integer Multiplication
Category:Examples of Monoids
Integers under Multiplication form Semigroup

== Theorem ==
The set of integers under multiplication $\struct {\Z, \times}$ is a semigroup.
== Proof ==
=== ===
Integer Multiplication is Closed, fulfilling .
=== ===
Integer Multiplication is Associative, fulfilling .
Hence the semigroup axioms are seen to be fulfilled.
Thus $\struct {\Z, \times}$ is a semigroup.
== Sources ==
* : Chapter $\text{I}$: Semi-Groups and Groups: $1$: Definition and examples of semigroups: Example $5$
* : $\S 29$. Semigroups: definition and examples: $(1)$
Category:Integer Multiplication
Category:Examples of Semigroups
Integers under Subtraction do not form Group

== Theorem ==
Let $\struct {\Z, -}$ denote the algebraic structure formed by the set of integers under the operation of subtraction.
Then $\struct {\Z, -}$ is not a group.
== Proof ==
It is to be demonstrated that $\struct {\Z, -}$ does not satisfy the group axioms.
First it is noted that Integer Subtraction is Closed.
Thus $\struct {\Z, -}$ fulfils .
However, we then have Subtraction on Numbers is Not Associative.
So, for example:
:$3 - \paren {2 - 1} = 2 \ne \paren {3 - 2} - 1 = 0$
Thus it has been demonstrated that $\struct {\Z, -}$ does not satisfy the group axioms.
Hence the result.
== Sources ==
* : $\S 1$: Some examples of groups
* : Chapter $1$: Definitions and Examples: Exercise $1 \ \text{(a)}$
Category:Integer Subtraction
Category:Examples of Groups
Integers under Subtraction do not form Semigroup

== Theorem ==
Let $\struct {\Z, -}$ denote the algebraic structure formed by the set of integers under the operation of subtraction.
Then $\struct {\Z, -}$ is not a semigroup.
== Proof ==
It is to be demonstrated that $\struct {\Z, -}$ does not satisfy the semigroup axioms.
We then have Subtraction on Numbers is Not Associative.
So, for example:
:$3 - \paren {2 - 1} = 2 \ne \paren {3 - 2} - 1 = 0$
Thus it has been demonstrated that $\struct {\Z, -}$ does not satisfy .
Hence the result.
== Sources ==
* : Chapter $1$: Rings - Definitions and Examples: Exercise $1$
Category:Integer Subtraction
Category:Examples of Semigroups
Integers under Subtraction form Magma

== Theorem ==
The set of integers $\Z$ under the operation of subtraction forms a magma.
== Proof ==
Recall the definition of magma:
:$\struct {S, \circ}$ is a magma $\forall a, b \in S: a \circ b \in S$:
That is, a magma is closed under its operation.
Recall that the operation of subtraction is defined as:
:$\forall a, b \in \Z: a - b := a + \paren {-b}$
Recall that the Integers under Addition form Group.
Hence:
:$\forall b \in \Z: -b \in \Z$
and:
:$\forall a, b \in \Z: a + \paren {-b} \in \Z$
That is:
:$\forall a, b \in \Z: a - b \in \Z$
Hence the result by definition of magma.
== Sources ==
* 
* 
Category:Integers
Category:Subtraction
Category:Examples of Magmas
Integers which are Divisor Sum for 3 Integers

== Theorem ==
The sequence of integers which are the divisor sum of $3$ different integers begins:
:$24, 42, 48, 60, 84, 90, \ldots$
== Proof ==
For a given $n$, to determine every $m$ such that $\map {\sigma_1} m = n$ can be determined by evaluating the divisor sum of all integers up to $n - 1$.
It is hence noted:
== Sources ==
* : $24$
Category:Divisor Sum Function
Integers whose Divisor Count equals Cube Root

== Theorem ==
There are $3$ positive integers whose divisor count function equals its cube root:
== Proof ==
Suppose $N = \map {\sigma_0} {N^3}$.
The case $N = 1$ is trivial.
Suppose $N$ is a prime power.
Write $N = p^n$.
By Divisor Count Function of Power of Prime:
:$N = \map {\sigma_0} {p^{3 n} } = 3 n + 1$
By Bernoulli's Inequality:
:$N = p^n \ge 1 + n \paren {p - 1}$
This gives us the inequality:
:$3 n + 1 \ge 1 + n \paren {p - 1}$
which can be simplified to:
:$3 \ge p - 1$
The only primes satisfying the inequality are $2$ and $3$.
We have:
Hence no prime powers satisfy the property.
Note that Divisor Count Function is Multiplicative.
To form an integer $N$ with our property, we must choose and multiply prime powers from the list above.
If we chose any $\tuple {p, n}$ with $\map {\sigma_0} {p^{4 n} } < p^n$, we must choose $2^m$ or $3^1$ in order for equality to possibly hold.
If $\tuple {2, 1}$ was chosen, $2^2 \nmid N$.
But $\map {\sigma_0} {2^3} = 4 \divides N$, which is a contradiction.
Suppose $\tuple {2, 2}$ was chosen.
Then $\map {\sigma_0} {2^6} = 7 \divides N$.
Then we must choose some $\tuple {7, n}$.
For $n = 1$, $\map {\sigma_0} {7^3} = 4$.
:$\map {\sigma_0} {2^6 \times 7^3} = 4 \times 7 = 28 = 2^2 \times 3$
:$\map {\sigma_0} {2^6 \times 7^3 \times p^{3 m} } = 28 \paren {3 m + 1} < 28 \times p^m$ for all $p \ne 2, 7$
For $n > 1$, $\map {\sigma_0} {2^6 \times 7^{3 n} } = 7 \paren {3 n + 1} < 4 \times 7^n$, a contradiction.
Suppose $\tuple {2, 3}$ was chosen.
Then:
:$\map {\sigma_0} {2^9} = 10 \divides N$
Then we must choose some $\tuple {5, n}$.
For $n = 1$, $\map {\sigma_0} {5^3} = 4$.
:$\map {\sigma_0} {2^9 \times 5^3} = 10 \times 4 = 40 = 2^3 \times 5$
:$\map {\sigma_0} {2^9 \times 5^3 \times p^{3 m} } = 40 \paren {3 m + 1} < 40 \times p^m$ for all $p \ne 2, 5$
For $n > 1$, $\map {\sigma_0} {2^9 \times 5^{3 n} } = 10 \paren {3 n + 1} < 2^3 \times 5^n$, a contradiction.
Suppose $\tuple {3, 1}$ was chosen.
Then $\map {\sigma_0} {3^3} = 4 \divides N$.
Then this case coincides the cases above.
Thus we have exhausted all cases.
== Sources ==
* : $21,952$
Category:Divisor Count Function
Category:Cube Numbers
Integers whose Divisor Sum equals Half Phi times Divisor Count

== Theorem ==
The following positive integers $n$ have the property where:
:$\map {\sigma_1} n = \dfrac {\map \phi n \times \map {\sigma_0} n} 2$
where:
:$\map {\sigma_1} n$ denotes the divisor sum function: the sum of the divisors of $n$
:$\map \phi n$ denotes the Euler $\phi$ function: the count of positive integers smaller than of $n$ which are coprime to $n$
:$\map {\sigma_0} n$ denotes the divisor count function: the count of the divisors of $n$:
These positive integers are:
:$35, 105, \ldots$
== Proof ==
We have:
== Also see ==
* Integers whose Phi times Divisor Count equal Divisor Sum
== Historical Note ==
== Sources ==
* : $105$
Category:Divisor Sum Function
Category:Euler Phi Function
Category:Divisor Count Function
Integers whose Divisor Sum equals Half Phi times Divisor Count/Historical Note

== Historical Note on Integers whose Divisor Sum equals Half Phi times Divisor Count ==
The intent of this result is unclear. Its statement by in his of $1997$ was erroneous, but no indication was given as to where it originated.
The On-Line Encyclopedia of Integer Sequences suggests that this result may be intended as:
:$\map {\sigma_1} n = \map \phi n \times \map j n$
where $\map j n$ is the count of $d \divides n$ such that $d \ge 3$ and $1 \le \dfrac n d \le d - 2$.
In such a case, the sequence begins:
:$35, 105, 248, 418, 594, 744, 812, 1254, \ldots$
It is also possible that the result may also have been intended to be:
:$\map {\sigma_1} n = \map \phi n \times \map k n$
where $\map k n$ is the count of $d \divides n$ such that $d < \sqrt n$.
Category:Historical Notes
Integers whose Divisor Sum equals Half Phi times Divisor Count/Mistake

== Source Work ==
:
:The Dictionary
::$105$
== Mistake ==
:$105$ is the second number $n$ such that $\map \phi n \times \map \nu n = \map \sigma n$, where $\map \nu n$ is the number of divisors of $n$. $\map \phi {105} = 48$, $\map \nu {105} = 8$ and $\map \sigma {105} = 192$.
:The first such number is $35$.
Elementary arithmetic shows that in fact $48 \times 8 = 384$, not $192$, and the result in fact appears to be:
:$\map \sigma n = \dfrac {\map \phi n \times \map \nu n} 2$.
The same applies to $35$.
The sequence such that $\map \phi n \times \map \nu n = \map \sigma n$ is in fact:
:$1, 3, 14, 42$
See Integers whose Phi times Divisor Count equal Divisor Sum.
== Sources ==
* : $105$
Category:Mistakes/Curious and Interesting Numbers
Integers whose Divisor Sum is Cube

== Theorem ==
The following positive integers are those whose divisor sum is a cube:
:$1, 7, 102, 110, 142, 159, 187, 381, 690, 714, 770, 994, 1034, \ldots$
== Examples ==
== Sources ==
* : $110$
Category:Integers whose Divisor Sum is Cube
Category:Divisor Sum Function
Category:Cube Numbers
Integers whose Divisor Sum is Cube/Mistake

== Source Work ==
:
:The Dictionary
::$110$
== Mistake ==
:$\map \sigma {110} = 216 = 6^3$, the first $n$, after $n = 1, 7$, for which $\map \sigma n$ is a cube.
== Correction ==
It is in fact the $2$nd $n$ after $n = 1, 7$, for which $\map \sigma n$ is a cube.
That is, it is the $4$th such $n$ altogether.
From Integers whose Divisor Sum is Cube, the sequence is in fact:
:$1, 7, 102, 110, 142, 159, 187, 381, 690, 714, 770, 994, 1034, \ldots$
So $102$ in particular has been missed.
== Sources ==
* : $110$
Category:Mistakes/Curious and Interesting Numbers
Integers whose Number of Representations as Sum of Two Primes is Maximum

== Theorem ==
$210$ is the largest integer which can be represented as the sum of two primes in the maximum number of ways.
The full list of such numbers is as follows:
:$1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 24, 30, 36, 42, 48, 60, 90, 210$
The list contains:
:$n \le 8$
:$n \le 18$ where $2 \divides n$
:$n \le 48$ where $2 \times 3 \divides n$
:$n \le 90$ where $2 \times 3 \times 5 \divides n$
:$210 = 2 \times 3 \times 5 \times 7$
=== Sufficient Condition ===
== Proof ==
From Number of Representations as Sum of Two Primes, the number of ways an integer $n$ can be represented as the sum of two primes is no greater than the number of primes in the interval $\closedint {\dfrac n 2} {n - 2}$.
The interval $\closedint {\dfrac {210} 2} {210 - 2}$ is $\closedint {105} {208}$.
The primes in this interval can be enumerated:
:$107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199$
It can be seen there are exactly $19$ of them.
We have:
and as can be seen, there are $19$ such representations, one for each prime in $\closedint {105} {208}$.
== Sources ==
* 
* : $210$
Category:Prime Numbers
Category:Integers whose Number of Representations as Sum of Two Primes is Maximum
Integers whose Number of Representations as Sum of Two Primes is Maximum/Sufficient Condition

== Theorem ==
Let $n$ be a (strictly) positive integer.
Suppose we have for some positive integer $k$:
:$p_k \# \divides n$
:$n \le 2 {p_{k + 1} }^2$
where $p_k \#$ denotes the product of the first $k$ primes.
Then $n$ can be represented as the sum of two primes in the maximum number of ways.
== Proof ==
From Number of Representations as Sum of Two Primes, the number of ways an integer $n$ can be represented as the sum of two primes is no greater than the number of primes in the interval $\closedint {\dfrac n 2} {n - 2}$.
Suppose we have for some positive integer $k$:
:$p_k \# \divides n$
:$n \le 2 {p_{k + 1} }^2$
Let $p$ be a prime in $\closedint {\dfrac n 2} {n - 2}$.
Then $2 \le n - p \le \dfrac n 2$.
$p$ must be coprime to $p_1, p_2, \dots, p_k$.
Since $p_1, p_2, \dots, p_k \divides n$:
:$n - p$ must also be coprime to $p_1, p_2, \dots, p_k$.
Hence the smallest prime factor of $n - p$ must be at least $p_{k + 1}$.
If $n - p$ is composite:
:$n - p \ge {p_{k + 1} }^2$
But we also have:
:$n - p \le \dfrac n 2 \le {p_{k + 1} }^2$
This leads to:
:$n - p = \dfrac n 2 = {p_{k + 1} }^2$
and thus:
:$p = \dfrac n 2 = {p_{k + 1} }^2$
which is a contradiction.
Thus $n - p$ must be prime.
This shows that $m$ is the sum of two primes in the maximum number of ways.
== Sources ==
* 
Category:Integers whose Number of Representations as Sum of Two Primes is Maximum