Index Index
abundancy index, Definition
and odd perfect numbers, Theorem
abundancy outlaws, Paragraph
abundant number. See number, abundant
amicable numbers, Paragraph
algorithm, Algorithm
Apéry's constant, Remark
via Twitter, Paragraph
Aryabhata, Historical remark
associates, Paragraph
asympotic, Definition
average. See long-term average
Bachet equation, Historical remark Paragraph
as special case of Mordell, Historical remark
Euler's ‘proof’ of, Fact
Bachet, sieur de Méziriac, Historical remark
base \(a\) test, Definition Definition
Miller's (see Miller's test base \(a\))
Bertrand's postulate, Theorem
Bezout identity. See Euclidean algorithm, extended
Big Oh notation. See Landau notation
Brahmagupta, Exercise Historical remark Paragraph
quote about mathematicians, Paragraph
Brun's constant, Paragraph
Carmichael numbers, Definition
characterization of, Proposition
certificate of primality, Paragraph
Chebyshev, Subsection
example, Example
for solving polynomial congruences, Algorithm
practical application of, Subsection
cipher, Paragraph
CoCalc, Paragraph
code, Paragraph
coin problem. See conductor
combinatorics, Paragraph
completing the square, Algorithm
composite number, Definition
conductor, Paragraph
exercises, Exercises
explore with Sage, Paragraph
congruence
arithmetic well-defined, Proposition
of two numbers, Definition
same as having same remainder, Lemma
congruences
as solutions to congruences, Section
giving system of congruences, Paragraph
linear (see linear congruences)
modular equivalent of equations, Definition Paragraph
quadratic, Paragraph
system of (see system of congruences)
conjecture
Artin's, Conjecture
Carmichael's, Exercise
Catalan's, Question Historical remark Paragraph
generalized Elliott-Halberstam, Paragraph
Goldbach, Conjecture
Polignac's, Conjecture
Riemann hypothesis, Conjecture
twin prime (see twin prime conjecture)
Von Koch's, Conjecture
Wagstaff's, Item
continued fraction, Paragraph
convolution. See Dirichlet product
coprime, Definition
cancellation in linear congruences, Fact
chances at random, Paragraph
needed for Diffie-Hellman, Paragraph
coprime in pairs. See mutually coprime
counting numbers. See numbers, counting
CRT. See Chinese remainder theorem
cryptography, Section. See also encryption method
Advanced Encryption Standard, Exercise
asymmetric key, Paragraph
cipher, Paragraph
decode, Paragraph
decryption, Paragraph
digital signature, Paragraph
elliptic curve, Paragraph
encode, Paragraph
encryption, Paragraph
key exchange, Algorithm
‘man in the middle’ attack, Subsection Subsection
secret sharing, Subsection Algorithm
symmetric key, Paragraph
trapdoor, Paragraph
Cython, Sage note
decode, Paragraph
decryption, Paragraph
key, Paragraph
def, Sage note
deficient number. See number, deficient
density
positive, Paragraph
Diffie-Hellman
key exchange, Algorithm
digital signature, Paragraph
Diophantine equations
general, Paragraph
higher-order, Paragraph
linear (see linear Diophantine equations)
Diophantus, Historical remark
Dirichlet, Historical remark
Dirichlet product, Definition
Dirichlet series, Definition
Dirichlet's Theorem. See primes, in an arithmetic progression
divisibility, Definition
basic facts, Proposition
division algorithm, Theorem
uses of, Subsection
divisor, Definition
common, Definition
greatest common, Definition
characterization, Theorem
use in Pollard rho, Paragraph
zero and zero, Remark
proper, Definition Example
divmod, Sage note
Dodgson, Charles. See Lewis Carroll
Dudeney, Paragraph
eggs in a basket, Exercise
Eisenstein, Historical remark Remark
Eisenstein criterion
ambiguous name, Remark
for quadratic residues, Theorem
Elements. See Euclid's Elements
Mordell's theorem on rational points, Theorem
use in proving Fermat's Last Theorem, Paragraph
encode, Paragraph
encryption key, Paragraph
encryption method
El-Gamal, Exercise
elliptic curve, Paragraph
Goldwasser-Micali, Paragraph
RSA, Algorithm
eponymy
Boyer's law of (see Stigler's law of eponymy)
Stigler's law of (see Stigler's law of eponymy)
equivalence class, Fact
mod \(n\), Definition
equivalence relation, Proposition
congruence as example of, Proposition
Eratosthenes, Historical remark
sieve of (see sieve of Eratosthenes)
Euclid's Elements, Historical remark
perfect numbers, Paragraph
applied to Fibonacci numbers, Exercise
example, Example
extended, Definition Paragraph
proof, Algorithm
statement, Algorithm
Euler, Historical remark Paragraph
and quadratic residues, Paragraph
son (Johann Albrecht), Paragraph
Euler \(\phi\) function, Definition Paragraph
long-term average, Proposition
Euler products, Definition
Euler's criterion
for quadratic residues, Theorem
Euler's theorem, Theorem
exploring formulas, Section
multiplicative, Fact
using for inverses, Subsection
visualization, Paragraph
Euler-Mascheroni constant, Definition Paragraph Paragraph Note
ir/rationality unknown, Remark
euler_phi, Sage note
exponentiation (mod \(n\))
algorithm for, Algorithm
not well-defined, Example
visualization, Subsection
factor, Item
factorial, Definition Theorem Paragraph Fact
prime (see prime, factorial)
factorization
continued fraction, Exercise
Fermat, Algorithm
in cryptography, Paragraph
of an integer, Definition
Pollard \(p-1\), Exercise
Pollard rho, Algorithm
prime, Definition
prime power, Definition
quadratic sieve, Exercise
trial (see trial division)
unique, Subsection Paragraph Paragraph Paragraph (see also fundamental theorem of arithmetic)
in Gaussian integers, Paragraph
Fermat, Historical remark
Fermat factorization, Algorithm
Fermat numbers, Paragraph Definition
factoring, Historical remark
Pépin's test for primality, Fact
primes from, Proposition
Fermat prime, Definition
Fermat's little theorem, Theorem
square root of, Theorem
visualization, Paragraph
Fibonacci, Paragraph
numbers (see numbers, Fibonacci)
field, Paragraph
number (see number field)
with one element, Remark
Fields Medal, Paragraph Historical remark Paragraph Theorem
floor function. See greatest integer function
Frobenius number. See number, Frobenius
FTA. See fundamental theorem of arithmetic
function
arithmetic, Paragraph
average value (see long-term average)
Chebyshev theta, Definition
Dirichlet identity, Definition
floor (see greatest integer function)
greatest integer (see greatest integer function)
identity, Definition
Liouville, Definition
Moebius \(\mu\) (see Moebius \(\mu\) function)
multiplicative (see multiplicative function)
probability density, Paragraph
Riemann zeta (see zeta function)
step, Paragraph
sum of divisors (see sum of divisors functions)
unit, Definition
fundamental region, Item
fundamental theorem of arithmetic, Theorem
gamma. See Euler-Mascheroni constant
Gauss
brief biographical notes, Historical remark
Gaussian integers, Historical remark
introducing congruence notation, Paragraph
letter to Encke, Figure
many proofs of quadratic reciprocity, Paragraph
quote, Paragraph
Gaussian integers. See integers, Gaussian
Gaussian prime. See prime, Gaussian
gcd. See divisor, greatest common
generator. See group, generator of
Germain, Historical remark
Germain primes, Paragraph
and Artin's conjecture, Example
and Fermat's Last Theorem, Paragraph
and Mersenne numbers, Remark
GIMPS, Historical remark
Girard, Historical remark
greatest common divisor. See divisor, greatest common
greatest integer function, Definition
convenience for turning functions into sums, Paragraph
use in estimating number of divisors, Paragraph
group, Definition
Abelian, Subsubsection Fact Historical remark Paragraph
cyclic, Subsubsection Proposition Theorem
example of non-Abelian, Exercise
finite, Subsubsection
generator of, Subsubsection Proposition
homomorphism, Remark
identity, Subsubsection
of quadratic residues (see quadratic residue, group)
of units (see units, group of)
order of, Definition
order of an element, Definition
quotient, Remark
solving equations in, Subsubsection Example
hardware bugs found using number theory, Historical remark Historical remark
prime (see prime harmonic series)
Hensel's lemma, Theorem
for solving polynomial congruences, Algorithm
Historical remarks
list of, Appendix
identity element, Subsubsection
induction proof. See proof by induction
infinite descent. See proof by infinite descent
integer lattice, Definition Paragraph Paragraph
as complex numbers, Paragraph
integers, Definition
Eisenstein, Exercise
Gaussian, Definition
unique factorization, Paragraph
modulo \(n\), Definition
integral test for series convergence, Proposition
@interact, Sage note
interacts. See Sage interacts
inverse
computing with Sage, Paragraph
modulo \(p\), Fact
of a group element, Subsubsection
of a number, Definition
group of units, Proposition
of a product, Fact
used in proof of CRT, Item
visualize, Paragraph
irrational number, Definition
Apéry's constant, Remark
examples, Exercises
\(\gamma\) status unknown, Remark
is_prime, Item
Jacobi symbol, Definition Paragraph
same as Legendre for \(2\), Exercise
key
decryption, Paragraph
encryption, Paragraph
exchange, Algorithm
Korselt's theorem, Proposition
Kronecker symbol, Sage note
kronecker_symbol, Sage note
Lagrange, Historical remark
and quadratic residues, Paragraph
Lagrange's theorem
for polynomials, Theorem
false for composite moduli, Paragraph
vindicated, Paragraph
on group order, Theorem
\(\lambda(n)\). See function, Liouville
Landau notation, Definition
basic exercises, Exercises
prime counting function \(\pi(x)\) computation, Theorem
lattice
general, Remark
integer (see integer lattice)
sublattice, Paragraph
lcm. See least common multiple
least common multiple, Exercise. See also divisor, greatest common
exercises, Exercises
Legendre
biography, Historical remark
prime numbers, Paragraph
quadratic residues, Definition
Legendre symbol, Definition
computation, Algorithm
as checking parity, Paragraph
using Jacobi symbol, Paragraph
via Eisenstein, Theorem
via Euler's criterion, Theorem
via quadratic reciprocity, Example
multiplicative, Proposition Proposition
legendre_symbol, Paragraph
lemma, Paragraph
correct Greek plural of, Paragraph
easier English plural of, Paragraph
Lewis Carroll, Historical remark
\(Li(x)\). See logarithmic integral
linear congruences, Paragraph
full solution, Section
simplification strategies, Fact
linear Diophantine equations, Section
geometric interpretation, Paragraph
solutions of, Theorem
filtered, Sage note
logarithm
discrete, Subsection
natural, Definition
logarithmic integral, Definition
long-term average
Euler \(\phi\) function, Proposition
sum of divisors functions, Fact Subsection
Lucas-Lehmer test, Algorithm
‘man in the middle’ attack, Subsection Subsection
MathJax, Paragraph
maximum, Definition
Mersenne, Historical remark
amicable numbers, Figure
Mersenne numbers, Definition
and Germain primes, Remark
primes from, Proposition
Mersenne primes, Subsection Definition
computer search (see GIMPS)
in perfect numbers, Paragraph
Mihailescu's theorem, Historical remark. See also conjecture, Catalan's
Miller's test base \(a\), Algorithm
Miller-Rabin test for primality, Algorithm
minimum, Definition
Minkowski, Historical remark
Minkowski's Theorem, Remark
mod(x,m), Paragraph
modulus, Definition
moebius, Sage note
Moebius \(\mu\) function, Definition
alternate definition, Proposition
multiplicative, Corollary
Moebius inversion formula, Theorem
monkeys. See pirates
monoid
commutative, Definition
finitely many integer points, Paragraph
rational points, Theorem
special cases, Proposition Theorem Paragraph Paragraph
visualization, Paragraph
Mordell's theorem, Theorem
\(\mu(n)\). See Moebius \(\mu\) function
multiplicative function, Definition
Euler's function as, Fact
Legendre symbol as, Proposition Proposition
Moebius function as, Corollary
preserved by Dirichlet product, Proposition
preserved by inversion, Proposition
preserved by summation, Theorem
mutually coprime, Paragraph
application of CRT, Subsection Algorithm
combine solutions, Fact
definition, Definition
in Pythagorean triples, Definition
needed for CRT, Theorem
mutually relatively prime. See mutually coprime
Möbius, Historical remark
natural numbers. See numbers, counting
Newton's method, Paragraph
next_prime, Paragraph
norm, Definition Paragraph
number
abundant, Definition
Carmichael (see Carmichael numbers)
composite, Definition
deficient, Definition
Fermat (see Fermat numbers)
Frobenius (see conductor)
irrational (see irrational number)
\(k\)-perfect, Definition
Mersenne, Definition
perfect (see perfect numbers)
prime (see prime)
pseudoperfect, Definition
pseudoprime (see pseudoprime)
rational (see rational number)
Skewes', Historical remark
superabundant, Definition
weird, Definition
number field, Paragraph
numbers
amicable (see amicable numbers)
complex, Definition Example
counting, Definition
Fibonacci, Exercise
natural (see numbers, counting)
\(\omega(n)\), Definition
operation
associative, Subsubsection
example where fails, Example
binary, Subsubsection
closed, Subsubsection
commutative, Paragraph
opposite parity. See parity, opposite
order
of a group, Definition
of a group element, Definition
parametrization, Paragraph
parity
big problems reduce to checking, Remark Claim Subsection
opposite, Definition
same, Definition
partition
of a number, Exercise
Pell's equation, Paragraph
perfect numbers, Definition. See also abundancy index
and Mersenne primes, Paragraph
characterization of even, Theorem
in Euclid's Elements, Paragraph
and abundancy index, Theorem
currently known criteria, Fact
\(\phi(n)\). See Euler \(\phi\) function
\(\pi(x)\). See prime counting function \(\pi(x)\)
Picasso
quote, Item
pigeonhole principle, Paragraph
pirates, Exercise
points
adding, Algorithm
doubling, Algorithm
rational on conics, Section
rational on elliptic curves (see elliptic curves, Mordell's theorem on rational points)
Pollard rho factorization, Algorithm
PolyMath Projects, Historical remark
polynomial
prime-generating, Paragraph
positive density. See density, positive
powers. See exponentiation (mod \(n\))
PreTeXt, Paragraph
prime, Definition
as conjectured from concept of relatively prime, Exercises
constellation, Paragraph
factorial, Item
Fermat (see Fermat prime)
Gaussian, Fact
visualization, Paragraph
Germain (see Germain primes)
harmonic series, Proposition
Mersenne (see Mersenne primes)
primorial, Item
races, Paragraph
relatively (see coprime)
repunit, Exercise
prime counting function \(\pi(x)\), Definition
explicit formula (see Riemann explicit formula for \(\pi(x)\))
Landau (Big Oh) computation, Theorem
not useful formula, Subsection
prime number theorem, Theorem
elementary proof, Historical remark
prime_divisors, Paragraph
prime_pi, Sage note
prime_range, Item
primes
arithmetic progressions of, Subsection
cousin, Paragraph
in an arithmetic progression, Theorem
sexy, Paragraph
twin (see twin primes)
primitive root, Definition Paragraph
characterization of, Proposition
primes possess, Theorem
testing for, Lemma
use in solving congruences, Section
primitive_root, Paragraph
primorial, Definition Proposition
prime (see prime, primorial)
print, Sage note
proof
by contradiction, Remark
by contrapositive, Remark
by induction, Subsection Paragraph
another easy example, Example
archetype, Example
proper divisor. See divisor, proper; divisor, proper
pseudoperfect number. See number, pseudoperfect
pseudoprime, Definition
infinitely many, Corollary
strong (see strong pseudoprime)
public-key cryptography, Paragraph
Pythagorean triple, Definition
characterization of primitive, Theorem
primitive, Definition
group operation, Remark
comments, Sage note
indexing, Sage note
loop, Sage note
Qin Jiushao, Historical remark
QR. See quadratic residue
quadratic congruences. See congruences, quadratic
quadratic forms, Paragraph
quadratic formula, Paragraph
quadratic nonresidue, Definition
quadratic reciprocity, Theorem
applications of, Section
cryptography, Subsection
factoring, Subsection
primality testing, Subsection
many proofs, Paragraph Subsection
meaning, Paragraph
proof of, Section
quadratic residue, Definition. See also Legendre symbol; quadratic reciprocity
consecutive ones, Exercise
Eisenstein criterion, Theorem
Euler criterion, Theorem
group, Definition
visualization, Paragraph
quadratic sieve, Exercise
quadratic_residues, Sage note
quaternions, Fact
quotient, Theorem
rational number, Definition
reify, Quotation
relation, Paragraph
equivalence (see equivalence relation)
relatively prime. See coprime
remainder, Theorem
connection to congruence, Lemma
repunit, Exercise
residue
(mod \(n\)), Definition
quadratic (see quadratic residue)
residues
complete system of, Definition
least absolute, Definition Example
least nonnegative, Definition Example
Riemann, Historical remark
Riemann explicit formula for \(\pi(x)\), Fact
Riemann Hypothesis, Conjecture
consequences of, Fact
ring, Paragraph
example of non-unique factorization domain, Exercise
example of unique factorization domain, Definition Paragraph Paragraph
of arithmetic functions, Remark
of integers (hint of), Definition Exercise Paragraph Paragraph
RSA. See encryption method, RSA
cell server, Paragraph
cells, Section
get worksheet, Exercise
interactive help, Sage note
Sage notes
list of, Appendix
SageMath. See Sage
same parity. See parity, same
secret sharing, Subsection Algorithm
set partition. See partition of sets
sets, Subsubsection
sieve
of Eratosthenes, Algorithm
quadratic, Exercise
\(\sigma(n)\). See sum of divisors functions
sigma, Sage note
\(\sigma_k(n)\). See sum of divisors functions
Skewes' number, Historical remark
solve_mod, Sage note
square root modulo \(n\), Definition
preliminary exploration, Section
Stigler's law of eponymy, Historical remark. See also eponymy, Boyer's law of
strong pseudoprime, Definition
sum of divisors functions, Definition
long-term average, Fact Subsection
sums of squares, Chapter Paragraph Definition
full statement, Theorem
insane fact concerning, Fact
more than two squares, Subsection
primes as, Section
visualization, Paragraph
Zagier one-sentence proof, Section
superabundant number. See number, superabundant
linear fully solved, Section
table
addition, Paragraph
multiplication, Paragraph
\(\tau(n)\). See sum of divisors functions
Taylor series
in Hensel's Lemma, Theorem
of log, Question
proving Euler's formula, Paragraph
Tertullian
quote, Paragraph
\(\Theta(x)\). See function, Chebyshev theta
trapdoor, Paragraph
trial division, Subsection
algorithm, Algorithm
trial factorization. See trial division
twin prime
conjecture, Conjecture
constant, Remark
twin primes, Definition
and Fermat factorization, Example
type, Sage note
units, Subsubsection
examples, Example
group of, Definition Paragraph
modulo \(n\) (see units, group of)
quadratic residues quotient group of, Remark
visualization
Euler's theorem, Paragraph
exponentiation (mod \(n\)), Subsection
Gaussian primes, Paragraph
Mordell equation, Paragraph
quadratic residue, Paragraph
Riemann zeta function, Subsection
sums of squares, Paragraph
Waring's Problem, Fact
weird number. See number, weird
well-defined, Proposition
exponentiation (mod \(n\)) not an example, Example
well-ordering principle, Axiom
Euclid implicitly assuming, Paragraph
not equivalent to induction, Paragraph
proof of division algorithm using, Paragraph
proof of Euclidean algorithm using, Algorithm
use in infinite descent, Paragraph
use to define order of group element, Paragraph
Wilson's theorem, Theorem
false for composite moduli, Exercise
xgcd, Paragraph
zero density. See density, zero
zeta function, Definition
special values of, Remark
visualization, Subsection
Zhang, Historical remark