Skip to main content
Logo image

Index Index

abundancy index, Definition
and odd perfect numbers, Theorem
abundancy outlaws, Paragraph
abundant number. See number, abundant
aliquot parts. See divisor, proper
amicable numbers, Definition
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
quote about mathematicians, Paragraph
Brun’s constant, Paragraph
Busy Beaver, Exercise
Carmichael numbers, Definition
characterization of, Proposition
certificate of primality, Paragraph
Chebyshev, Subsection
Chinese remainder theorem, Theorem Algorithm Paragraph
example, Example
for solving polynomial congruences, Algorithm
practical application of, Subsection
cipher, Paragraph
class number, Remark
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
solution, Fact
arithmetic well-defined, Proposition
of two numbers, Definition
same as having same remainder, Lemma
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)
congruent number problem, Paragraph Paragraph
Artin’s, Conjecture
Birch-Swinnerton-Dyer, Exercise Note Note
Carmichael’s, Exercise
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
positive, Paragraph
encryption, Paragraph Algorithm
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
divmod, Sage note
Dodgson, Charles. See Lewis Carroll
Dudeney, Paragraph
eggs in a basket, Exercise
Eisenstein criterion
ambiguous name, Remark
for quadratic residues, Theorem
Elements. See Euclid’s Elements
elliptic curves, Paragraph Paragraph Exercises
cryptographic applications, Paragraph Paragraph
Mordell curves as special case, Section Paragraph
Mordell’s theorem on rational points, Theorem
use in proving Fermat’s Last Theorem, Paragraph
encode, Paragraph
encryption key, Paragraph
encryption method
Diffie-Hellman, Paragraph Algorithm
El-Gamal, Exercise
elliptic curve, Paragraph
Goldwasser-Micali, Paragraph
RSA, Algorithm
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)
Euclidean algorithm, Section Paragraph
applied to Fibonacci numbers, Exercise
example, Example
example, Example Example
proof, Algorithm
statement, Algorithm
Euclid’s Elements, Historical remark
perfect numbers, Paragraph
and quadratic residues, Paragraph
son (Johann Albrecht), Paragraph
Euler \(\phi\) function, Definition Paragraph
long-term average, Proposition
Euler products, Definition
Euler-Mascheroni constant, Definition Paragraph Paragraph Note
ir/rationality unknown, Remark
euler_phi, Sage note
Euler’s criterion
for quadratic residues, Theorem
Euler’s theorem, Theorem
exploring formulas, Section
multiplicative, Fact
using for inverses, Subsection
visualization, Paragraph
exponentiation (mod \(n\))
algorithm for, Algorithm
in cryptography, Section Section
not well-defined, Example
visualization, Subsection
factor, Item
prime (see prime, factorial)
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
Shor’s algorithm, Paragraph
trial (see trial division)
unique, Subsection Paragraph Paragraph Paragraph (see also fundamental theorem of arithmetic)
in Gaussian integers, Paragraph
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 last theorem, Paragraph Fact
Fermat’s little theorem, Theorem
square root of, Theorem
visualization, Paragraph
visualization, Paragraph Paragraph
numbers (see numbers, Fibonacci)
field, Paragraph
number (see number field)
with one element, Remark
floor function. See greatest integer function
Frobenius number. See number, Frobenius
FTA. See fundamental theorem of arithmetic
arithmetic, Paragraph
average value (see long-term average)
Chebyshev theta, Definition
Dirichlet identity, Definition
floor (see greatest integer function)
Gamma, Remark Note
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
brief biographical notes, Historical remark
Gaussian integers, Historical remark
introducing congruence notation, Paragraph
letter to Encke, Figure
many proofs of quadratic reciprocity, Paragraph
prime numbers, Paragraph Figure
quote, Paragraph
Gaussian integers. See integers, Gaussian
Gaussian prime. See prime, Gaussian
gcd. See divisor, greatest common
generator. See group, generator of
Germain primes, Paragraph
and Artin’s conjecture, Example
and Fermat’s Last Theorem, Paragraph
and Mersenne numbers, 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
example of non-Abelian, Exercise
finite, Subsubsection
generator of, Subsubsection Proposition
homomorphism, Remark
ideal class, 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
socks and shoes property, Fact Exercise
solving equations in, Subsubsection Example
hardware bugs found using number theory, Historical remark Historical remark
harmonic series, Paragraph Paragraph
prime (see prime harmonic series)
Hensel’s lemma, Theorem
for solving polynomial congruences, Algorithm
quadratic example, Example Example Example
special case, Remark
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
positive points, Section 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
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
inverse_mod, Paragraph 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
decryption, Paragraph
encryption, Paragraph
exchange, Algorithm
Korselt’s theorem, Proposition
Kronecker symbol, Sage note
kronecker_symbol, Sage note
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
general, Remark
integer (see integer lattice)
positive integer points, Section Paragraph
sublattice, Paragraph
lcm. See least common multiple
least common multiple, Exercise. See also divisor, greatest common
exercises, Exercises
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
list comprehension, Sage note Sage note
filtered, Sage note
discrete, Subsection
natural, Definition
logarithmic integral, Definition
long-term average
Euler \(\phi\) function, Proposition
sum of divisors functions, Fact Subsection
sums of squares, Fact Example
Lucas-Lehmer test, Algorithm
‘man in the middle’ attack, Subsection Subsection
MathJax, Paragraph
maximum, Definition
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-Rabin test for primality, Algorithm
Miller’s test base \(a\), 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
commutative, Definition
Mordell equation, Paragraph Section Paragraph
finitely many integer points, Paragraph
rational points, Theorem
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
natural numbers. See numbers, counting
Newton’s method, Paragraph
next_prime, Paragraph
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
amicable (see amicable numbers)
counting, Definition
Fibonacci, Exercise
natural (see numbers, counting)
\(\omega(n)\), Definition
associative, Subsubsection
example where fails, Example
binary, Subsubsection
closed, Subsubsection
commutative, Paragraph
opposite parity. See parity, opposite
of a group, Definition
of a group element, Definition
parametrization, Paragraph
big problems reduce to checking, Remark Claim Subsection
opposite, Definition
same, Definition
of a number, Exercise
of sets, Fact Paragraph Fact
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)\)
quote, Item
pigeonhole principle, Paragraph
pirates, Exercise
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
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
arithmetic progressions of, Subsection
cousin, Paragraph
in an arithmetic progression, Theorem
proof of infinitude of, Theorem Fact Theorem
sexy, Paragraph
twin (see twin primes)
primitive root, Definition Paragraph
characterization of, Proposition
number of, Fact Fact
primes possess, Theorem
testing for, Lemma
use in solving congruences, Section
primitive_root, Paragraph
prime (see prime, primorial)
print, Sage note
by contradiction, Remark
by contrapositive, Remark
by induction, Subsection Paragraph
another easy example, Example
archetype, Example
by infinite descent, Paragraph Example
direct, Paragraph
proper divisor. See divisor, proper
pseudoperfect number. See number, pseudoperfect
pseudoprime, Definition
infinitely many, Corollary
strong (see strong pseudoprime)
public-key cryptography, Paragraph
Pythagorean theorem, Paragraph Paragraph
Pythagorean triple, Definition
characterization of primitive, Theorem
primitive, Definition
group operation, Remark
Python, Item Sage note
comments, Sage note
indexing, Sage note
loop, Sage note
Pépin’s test, Paragraph Fact
QR. See quadratic residue
quadratic congruences. See congruences, quadratic
quadratic forms, Paragraph
quadratic formula, Paragraph
quadratic nonresidue, Definition
quadratic reciprocity, Theorem
alternate form, Remark Remark
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
(mod \(n\)), Definition
quadratic (see quadratic residue)
complete system of, Definition
least absolute, Definition Example
least nonnegative, Definition Example
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
Sage, Item Section
cell server, Paragraph
cells, Section
get worksheet, Exercise
interactive help, Sage note
interacts, Paragraph Sage note
Sage notes
about, Item Sage note
list of, Appendix
SageMath. See Sage
same parity. See parity, same
secret sharing, Subsection Algorithm
set partition. See partition of sets
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
long-term average, Fact Example
more than two squares, Subsection
primes as, Section
visualization, Paragraph
Zagier one-sentence proof, Section
superabundant number. See number, superabundant
system of congruences, Theorem Paragraph
linear fully solved, Section
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
quote, Paragraph
\(\Theta(x)\). See function, Chebyshev theta
trapdoor, Paragraph
trial division, Subsection
algorithm, Algorithm
trial factorization. See trial division
try/except, Sage note
twin prime
conjecture, Conjecture
constant, Remark
twin primes, Definition
and Fermat factorization, Example
type, Sage note
examples, Example
modulo \(n\) (see units, group of)
quadratic residues quotient group of, Remark
quadratic residues subgroup of, Theorem Remark
Euler’s theorem, Paragraph
exponentiation (mod \(n\)), Subsection
Fermat’s little theorem, Paragraph Paragraph
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