## Index Index

abundancy index, Definition

and odd perfect numbers, Theorem

abundancy outlaws, Paragraph

abundant number.

*See*number, abundantaliquot parts.

*See*divisor, properamicable numbers, Definition

algorithm, Algorithm

Apéry’s constant, Remark

via Twitter, Paragraph

Aryabhata, Historical remark

associates, Paragraph

asympotic, Definition

average.

*See*long-term averageBachet 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, extendedBig Oh notation.

*See*Landau notationBrahmagupta, Exercise Historical remark Paragraph

quote about mathematicians, Paragraph

Brun’s constant, Paragraph

Busy Beaver, Exercise

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

class number, Remark

CoCalc, Paragraph

code, Paragraph

coin problem.

*See*conductorcombinatorics, Paragraph

completing the square, Algorithm

composite number, Definition

conductor, Paragraph

exercises, Exercises

explore with Sage, Paragraph

solution, Fact

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 productcoprime, Definition

cancellation in linear congruences, Fact

chances at random, Paragraph

needed for Diffie-Hellman, Paragraph

coprime in pairs.

*See*mutually coprimecounting numbers.

*See*numbers, countingCRT.

*See*Chinese remainder theoremcryptography, Section.

*See also*encryption methodAdvanced 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, deficientdensity

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 progressiondivisibility, 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 CarrollDudeney, Paragraph

eggs in a basket, Exercise

Eisenstein, Historical remark Remark

Eisenstein criterion

ambiguous name, Remark

for quadratic residues, Theorem

Elements.

*See*Euclid’s ElementsMordell’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)applied to Fibonacci numbers, Exercise

example, Example

extended, Definition Paragraph

proof, Algorithm

statement, Algorithm

Euclid’s Elements, Historical remark

perfect numbers, Paragraph

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-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

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

Shor’s algorithm, Paragraph

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, Historical remark Exercise

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 functionFrobenius number.

*See*number, FrobeniusFTA.

*See*fundamental theorem of arithmeticfunction

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 constantGauss

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, GaussianGaussian prime.

*See*prime, Gaussiangcd.

*See*divisor, greatest commongenerator.

*See*group, generator ofGermain, 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 commongreatest 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

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

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

special case, Remark

Historical remarks

list of, Appendix

identity element, Subsubsection

induction proof.

*See*proof by inductioninfinite descent.

*See*proof by infinite descentinteger 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 interactsinverse

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, LiouvilleLandau 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 multipleleast common multiple, Exercise.

*See also*divisor, greatest commonexercises, 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 integrallinear 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’sMiller-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*piratesmonoid

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\) functionmultiplicative 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 coprimeMöbius, Historical remark

natural numbers.

*See*numbers, countingNewton’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, oppositeorder

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 indexand 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, positivepowers.

*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

direct, Paragraph

proper divisor.

*See*divisor, properpseudoperfect number.

*See*number, pseudoperfectpseudoprime, 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 Exercise

QR.

*See*quadratic residuequadratic congruences.

*See*congruences, quadraticquadratic 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 reciprocityconsecutive 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*coprimeremainder, 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, RSAcell server, Paragraph

cells, Section

get worksheet, Exercise

interactive help, Sage note

Sage notes

list of, Appendix

SageMath.

*See*Sagesame parity.

*See*parity, samesecret sharing, Subsection Algorithm

set partition.

*See*partition of setssets, Subsubsection

sieve

of Eratosthenes, Algorithm

quadratic, Exercise

\(\sigma(n)\).

*See*sum of divisors functions`sigma`

, Sage note
\(\sigma_k(n)\).

*See*sum of divisors functionsSkewes’ 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 ofstrong 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, superabundantlinear fully solved, Section

table

addition, Paragraph

multiplication, Paragraph

\(\tau(n)\).

*See*sum of divisors functionsTaylor series

in Hensel’s Lemma, Theorem

of log, Question

proving Euler’s formula, Paragraph

Tertullian

quote, Paragraph

Thabit ibn Qurra, Historical remark Historical remark Exercise

\(\Theta(x)\).

*See*function, Chebyshev thetatrapdoor, Paragraph

trial division, Subsection

algorithm, Algorithm

trial factorization.

*See*trial divisiontwin 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, weirdwell-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, zerozeta function, Definition

special values of, Remark

visualization, Subsection

Zhang, Historical remark