Title: Theory / Unimportant / Math / Number Theory / Hardy - Wright{ / 01 Primes
Tags: fromMath mathToDef fromImplication hasSeenConjDef mathToSee autDo fromAlgorithm hasNotNewEffectReturnsMeaning mid1516974248815 oldAlgoNewName toBinaryRelation toUnary typToBinary

Name: The rational integers
Definition: \(\dots,-3,-2,-1,0,1,2,\dots\).
Page: 1
Chapter: I
Section: 1.1
Name2: The integers

Name: The non-negative integers
Definition: \(0,1,2,\dots\).
Page: 1
Chapter: I
Section: 1.1

Name: The positive integers
Definition: \(1,2,\dots\).
Page: 1
Chapter: I
Section: 1.1

Definition: not \(b|a\)
Page: 1
Chapter: I
Section: 1.1
Variables: \(a,b\) integer
Notation: \(b\nmid a\)

Smaller0: \(c|a\), \(c|b\)
Greater0: \(c|ma+nb\) for each \(m,n\) integers
Page: 2
Chapter: I
Section: 1.1
Variables: \(a,b,c\) integer
Smaller to greater: iff
Assuming: \(c\ne 0\)

Name: A prime number
Definition: A positive number which have no divisors except 1 and itself.
Page: 2
Chapter: I
Section: 1.2

Name: A composite number
Definition: A number which is not prime.
Page: 2
Chapter: I
Section: 1.2

Question: \(n\) is
Answer: a product of prime.
Page: 2
Chapter: I
Section: 1.2
Variables: \(n\) a positive integer
Index: 1
Kind: Theo
Assuming: \(n\ne 1\)

Name: The standard form expression of an integer
Definition: \(\Pi_{i=1}^kp_i^{a_i}\) with \(p_i<p_{i+1}\) prime, and \(a_i>0\).
Page: 2
Chapter: I
Section: 1.2
Assuming: \(n\ne 1\)

Smaller0: \(n\) prime
Greater0: \(n|a\) or \(n|b\)
Page: 3
Chapter: I
Section: 1.3
Variables: \(n,a,b\) positive integer
Kind: Theo
Smaller1: \(n|ab\)
Name: Euclid's first theorem

Page: 4
Implementation: Write every number greater between \(2\) and \(s\).
For each \(i\), not crossed, less than \(\sqrt s\). Cross every multiple of \(i\) at least equal to \(i^2\).
Section: 1.4
Chapter: I
Variables: \(s\) a positive integer
Name: Sieve of Eratosthene
Returns: The list of primes smaller than \(s\).

Question: The number of prime is
Answer: infinite.
Page: 5
Chapter: I
Section: 1.4
Name: Euclid's second theorem

Smaller0: \(c=N!\)
Greater0: composite numbers
Page: 6
Chapter: 1
Section: 4
Variables: \(N\in\mathbb N\)
Index: 5
Kind: Theo
Hide middle: yes
Prefix Greater: the \(N\) numbers after \(c\) are

Name: A prime pair
Definition: A pair of prime numbers of the form \((p,p+2)\).
Page: 6
Chapter: 1
Section: 4
Index: 5
Kind: Theo

Definition: The number of primes which do not exceed \(n\).
Page: 7
Chapter: 1
Section: 5
Variables: \(n\in\mathbb N\)
Notation: \(\pi(n)\)
Kind: Theo

Question: \(\pi(p_n)=\)
Answer: \(n\)
Page: 7
Chapter: 1
Section: 5
Variables: \(n\in\mathbb N\),
\(p_n\) be the \(n\)-th prime

Definition: \(|f|<A\phi\) for some \(A\) constant.
Page: 7
Chapter: 1
Section: 5
Variables: \(f,\phi:D\to\mathbb R\) with \(D\subseteq\mathbb R^+\) unbounded
Notation: \(f=O(\phi)\)

Definition: \(f/\phi\to0\).
Page: 8
Chapter: 1
Section: 5
Variables: \(f,\phi:D\to\mathbb R\) with \(D\subseteq\mathbb R^+\) unbounded
Notation: \(f=o(\phi)\)
Notation2: \(f\prec \phi\)

Q: \(f=[...](\phi)\) [...] \(f=[...](\phi)\).
A: o; implies; O
Page: 7
Chapter: 1
Section: 5
Variables: \(f,\phi:D\to\mathbb R\) with \(D\subseteq\mathbb R^+\) unbounded
Index: iii

Definition: \(f/\phi\to\infty\).
Page: 7
Chapter: 1
Section: 5
Variables: \(D\subseteq\mathbb R^+\) unbounded
\(f,\phi:D\to\mathbb R\)
Notation: \(f\succ \phi\)
Extra: \phi=o(f) ?

Name: \(f\) is of the same order of magnitude as \(\phi\)
Definition: \(A\phi<f<A'\phi\) with \(A,A'\) constant.
Page: 7
Chapter: 1
Section: 5
Variables: \(f,\phi:D\to\mathbb R\) with \(D\subseteq\mathbb R^+\) unbounded
Notation: \(f\asymp\phi\)
Extra: theta?

Question: The next prime is at most
Answer: \(p^n_n-1\)
Page: 14
Variables: \(p_n\) the \(n\)-th prime

Question: \(p_n\) is bounded by
Answer: \(2^{2^{n+1} }\)
Page: 14
Variables: \(n\in\mathbb N\)

Question: \(\pi(n)\) is at least
Answer: \(\log\log n\).
Page: 15
Chapter: 2
Variables: \(n\in\mathbb N\)
Index: 10
Kind: Theo

Question: To find a prime, equivalent to 3 modulo 4, greater than \(n\):
Answer: \(2\Pi_{p\text{ prime}<n}p-1\).
Page: 15
Chapter: 2
Section: 3
Variables: \(n\in\mathbb N\)

Question: To find a prime, equivalent to 5 modulo 6, greater than \(n\):
Answer: \(\Pi_{p\text{ prime}<n}p-1\).
Page: 15
Chapter: 2
Section: 3
Variables: \(n\in\mathbb N\)

Smaller0: \(a,b\) have no common factor
Greater0: \(d\equiv 1\mod 4\)
Page: 16
Chapter: 2
Section: 3
Variables: \(a,b,d\in\mathbb N\)
Index: 13
Kind: Theo
Smaller1: \(d|a^2+b^2\) odd

Question: To find a prime, equivalent to 5 modulo 8, greater than \(n\):
Answer: \(\Pi_{2<p\text{ prime}<n}p^2+4\).
Page: 16
Chapter: 2
Section: 3
Index: 14
Kind: Theo

Smaller0: \(a,b\) coprime, \(a>0\)
Greater0: there are infinitely many prime equivalent to \(a\) mod \(b\)
Page: 16
Chapter: 2
Section: 3
Variables: \(a,b\in\mathbb N\)
Index: 15
Kind: Theo
Hide middle: yes
Name: Dirichlet's theorem

Name: The \(n\)th Fermat's number
Definition: \(2^{2^n}+1\)
Page: 17
Chapter: 2
Section: 3
Variables: \(n\in\mathbb N\)
Notation: \(F_n\)

Smaller0: \(a\ge2\)
Greater0: \(a\) even
Page: 18
Chapter: 2
Section: 5
Variables: \(a,n\in\mathbb N\)
Index: 17
Kind: Theo
Smaller1: \(a^n+1\) prime
Greater1: \(n\) is a power of 2
Counterexample: 17 divides \(6^{2^3}+1\)

Smaller0: \(a^n-1\) prime
Greater0: \(a=2\)
Page: 19
Chapter: 2
Section: 5
Variables: \(a,n\in\mathbb N\)
Index: 18
Kind: Theo
Smaller1: \(n\ge2\)
Greater1: \(n\) prime
Counterexample: 5 divides \(2^4-1\)

Question: \(\sum\frac1p\) for \(p\) prime is
Answer: divergent
Page: 21
Chapter: 2
Section: 5
Variables: \(a,n\in\mathbb N\)
Index: 19
Kind: Theo

Question: The number of composite numbers in \(f[\mathbb Z]\) is
Answer: infinite
Page: 22
Chapter: 2
Section: 5
Variables: \(f\in\mathbb Z[x]\)
Index: 21
Kind: Theo
Assuming: f not constant

Question: The number of composite in the image of \(f(n,2^n,3^n,\dots,k^n)\) is
Answer: infinite
Page: 22
Chapter: 2
Section: 5
Variables: \(f\in\mathbb Z[x_1,\dots,x_n]\)
Index: 21
Kind: Theo
Assuming: \(f\) grows to infinity

Name: A modulus
Definition: A system \(S\subseteq\mathbb Z\) closed under + and -
Page: 23
Chapter: 2
Section: 9

Question: A modulus is
Answer: either null or \(d\mathbb Z\)
Page: 23
Chapter: 2
Section: 9
Kind: Theo

Name: Their least common multiple
Definition: Least positive integer which is a multiple of both \(a\) and \(b\).
Page: 57, 58
Chapter: 5
Section: 1
Variables: \(a,b\in\mathbb Z\)
Notation: \(\{a,b\}\)
Index: 51
Kind: Theo
Definition2: \(\prod_p p^{\max(a_p,b_p)}\), with \(a_p\) the coefficient of \(p\) in \(a\)
Assuming: \(a\) or \(b\) is not null

Name: Their highest common divisor
Definition: Largest positive integer which divides both \(a\) and \(b\).
Page: 24, 57
Chapter: 2, 5
Section: 9, 1
Variables: \(a,b\in\mathbb Z\)
Notation: \((a,b)\)
Index: 50
Kind: Theo
Definition2: \(\prod_p p^{\min(a_p,b_p})\), with \(a_p\) the coefficient of \(p\) in \(a\)
Assuming: \(a\) or \(b\) is not null

Question: \((0,a)\)
Answer: is \(|a|\)
Page: 24
Chapter: 2
Section: 9
Variables: \(a\in\mathbb Z\)
Assuming: \(a\) not null

Definition: \(f/\phi\to1\),
Page: 7
Chapter: 1
Section: 5
Variables: \(f,\phi:D\to\mathbb R\) with \(D\subseteq\mathbb R^+\) unbounded
Notation: \(f\sim\phi\)
Index: iii
Definition2: \(f=\phi+o(\phi)\),
Definition3: \(f=\phi(1+o(1))\).

Question: The number of standard form expression of \(n\) is
Answer: exactly one.
Page: 3
Chapter: I
Section: 1.3
Variables: \(n\) a positive integer
Index: 2
Kind: Theo
Name: Fundamental theorem of arithmetic

Page: 1, 2
Definition: \(\exists c. bc=a\).
Chapter: I
Section: 1.1
Variables: \(a,b\) integer, \(b\ne0\)
Notation: \(b|a\)
Name: \(a\) is divisible by \(b\)
Transitive: Transitive
Example: \(1\) divides every integers
Name2: \(b\) is a divisor of \(a\)
Example2: every non zero integers are divisors of 0
Example3: \(a\) divides \(a\)

Question: \(\pi(n)\) is asymptotic to
Answer: \(n/\log n\).
Page: 10
Chapter: 1
Section: 5
Index: 6
Kind: Theo

Question: \((F_n,F_m)=\)
Answer: 1
Page: 17
Chapter: 2
Section: 4
Variables: \(n\ne m\in\mathbb N\),
\(F_i\) the \(i\)-th Fermat number
Index: 16
Kind: Theo

Question: The modulus \(xa+yb\) is
Answer: the aggregate of multiples of \((a,b)\)
Page: 25
Chapter: 2
Section: 9
Variables: \(a,b\in\mathbb Z\)

Question: \((ac,bc)=\)
Answer: \((a,b)c\)
Page: 25
Chapter: 2
Section: 9
Variables: \(a,b,c\in\mathbb Z\)
Index: 27
Kind: Theo
Assuming: \(c\ne 0\)

Name: An abnormal number
Definition: A number which can be factorized into prime in more than one way.
Page: 26
Chapter: 2
Section: 11
Kind: Theo
Property: Does not exists in integers

Name: Coprime integers
Definition: Integrals \(a,b\) such that \((a,b)=1\)
Page: 58
Chapter: 5
Section: 1

Definition: [$]\defFun{\mathbb N}{\mathbb N}{m}{\text{number of naturals less than $m$, coprime to $m$} }[/$]
Page: 63, 64, 20
Section: 5, 2
Chapter: 5, 2 Ireland, Rosen
Notation: \(\phi\)
Name: The Euler function
Index: Theo
Kind: 60
Extra: Multiplicative
Context: Number theory

Name: A complete set of residues prime to \(m\)
Definition: A set containing an element for each of the \(\phi(m)\) residues prime to \(m\)
Page: 63
Chapter: 5
Variables: \(m\) integer
Context: Number theory

Page: 63
Chapter: 5
Variables: \(m\) integer
Index: 58
Kind: Theo
Name: Complete set of residues prime to \(m\)
Closure: multiplication by an integer
Q: [...]
A: prime with \(m\)
Context: Number theory

Question: How to obtain a complete set of residues mod \(m_1m_2\) ?
Answer: Take \(a_1m_2+a_2m_1\) with \(a_i\) ranging in a complete set of residues mod \(m_i\)
Page: 63
Chapter: 5
Variables: \(m_1,m_2\) integer
Index: 59
Kind: Theo