Annotated Web Links

CHAPTER 3 - Primes and Greatest Common Divisors
Return to Annotated Web Links Home

 

 

3.1 Prime Numbers

Page 68

A wealth of information about primes can be found at the Prime Page http://www.utm.edu/research/primes/ (The Prime Page)

An excellent survey about prime numbers can be found at the St Andrews History of Mathematics Archive at
http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Prime_numbers.html (Prime numbers)

 

Page 70

Biographical information about Eratosthenes can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Eratosthenes.html (Eratosthenes)

You can find an applet for running the sieve of Eratosthenes at http://www.math.utah.edu/~alfeld/math/prime.html

Information about the sieve of Eratosthenes and links for implementations in C, Java, and Perl can be found at http://primes.utm.edu/links/programs/sieves/Eratosthenes/index.html

(The Sieve of Eratosthenes)

 

 

Page 71

Biographical information about G. Lejeune Dirichlet can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Dirichlet.html (Dirichlet) ]

 

An applet that finds primes in a arithmetic progression can be found at http://wims.unice.fr/wims/wims.cgi?session=8757B045&lang=en&module=tool%2Fnumber%2Fprimes.en

 

The largest known primes are discussed at http://www.utm.edu/research/primes/largest.html (The Largest Known Primes)

 

 

Page 72

 

Formulas for primes are discussed at http://mathworld.wolfram.com/PrimeFormulas.html (Prime Formulas." From MathWorld--A Wolfram Web Resource)

 

 

 

Page 73

 

Information about the proof that PRIMES is in P can be found at http://www.cse.iitk.ac.in/news/primality.html (PRIMES is in P).   Other sites with more information about this result are http://www.utm.edu/research/primes/prove/prove4_3.html (Finding primes and proving primality), http://www.ams.org/notices/200305/fea-bornemann.pdf (PRIMES is in P:  A Breakthrough for “Everyman”) and http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html (The PRIMES is in P little FAQ).

 

 

Page 75

 

You can find out more about the lucky numbers at http://www.wschnei.de/number-theory/lucky-numbers.html (Lucky Numbers) and at http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000959

 

 

 

 

3.2    The Distribution of Primes

 

Page 77

Biographical information about Pafnuty Lvovich Chebyshev can be found at the MacTutor History of Mathematics Archive at
http://www-groups.mcs.st-andrews.ac.uk/~history/Mathematicians/Chebyshev.html (Chebyshev)

 

Page 78

Biographical information about Jacques Hadamard can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Hadamard.html (Hadamard)

Biographical information about Charles-Jean-Gustave-Nicholas de la Valeé-Poussin can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Vallee_Poussin.html (Valeé-Poussin)

 

 

 

Page 79

 

An interactive applet for exploring the prime number theorem can be found at Peter Alfeld’s site at http://www.math.utah.edu/~alfeld/math/machine.html (The Prime Machine)

Biographical information about Paul Erdös can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Erdos.html (Erdös)

 

An informative article about the life of Paul Erdös can be found at http://www.maa.org/mathland/mathland_10_7.html (Paul Erdos: An Infinity of Problems)

 

Biographical information about Alte Selberg can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Selberg.html (Selberg)

 

 

 

Page 81

 

Information about the Riemann hypothesis can found at http://www.utm.edu/research/primes/notes/rh.html (The Riemann Hypothesis), at http://www.math.ubc.ca/~pugh/RiemannZeta/RiemannZetaLong.html (The Riemann Hypothesis in a Nutshell), and http://www.maths.ex.ac.uk/~mwatkins/zeta/conreyRH.pdf (The Riemann Hypothesis)

 

 

Page 83

 

Biographical information about Joseph Bertrand can be found at the MacTutor History of Mathematics Archive at http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Bertrand.html (Bertrand)

 

 
A description of some of the open questions about primes can be found on the Prime Pages at
http://www.utm.edu/research/primes/notes/conjectures (Prime Conjectures and Open Questions)

 

The largest twin primes known can be found at http://primes.utm.edu/top20/page.php?id=1 (The Top Twenty Twin Primes)

 

Counts of twin primes and computations of Brun’s constant can be found at http://www.trnicely.net/twins/twins2.html (Enumeration to 1.6*10^15 of the twin primes and Brun's constant)

 

You can learn more about the twin prime conjecture and related conjectures at http://www.ltkz.demon.co.uk/ktuplets.htm (Prime k-tuples)

 

 

Page 84

 

Biographical information (in Chinese) about Jing Run Chen can be found at http://www.math.ac.cn/Chinese/B/Chenjr/Chenjr.htm

 

 

Biographical information about Viggo Brun can be found at http://www.numbertheory.org/obituaries/OTHERS/brun/brun.html (Viggo Brun)

 

More information about the story behind the Intel Pentium chip flaw and its discovery can be found at http://www.emery.com/1e/pentium.htm (The Pentium Chip Story: A Learning Experience) and at http://www.maa.org/mathland/mathland_5_12.html (Pentium Bug Revisited).

Information about the current status of numerical evidence supporting Golbach's conjecture can be found at http://www.ieeta.pt/~tos/goldbach.html (Goldbach conjecture verification) and at
http://www.informatik.uni-giessen.de/staff/richstein/ca/Goldbach.html (Goldbach's Conjecture

Biographical information about Christian Goldbach can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Goldbach.html (Goldbach)

 

 

3.3    Greatest Common Divisors

Page 90

An excellent starting place for learning about greatest common divisors is
http://www.utm.edu/research/primes/glossary/GCD.html (The Prime Glossary: greatest common divisor)

Page 96

Information about Farey series and about Farey himself can be found at
http://www.cut-the-knot.com/blue/Farey.html (Farey Series)

Programs for computing Farey series can be found at
http://www.maths.usyd.edu.au:8000/u/magma/Examples/node6.html (Farey sequence)

 

Biographical information about John Farey can be found at the MacTutor History of Mathamatics Archive at http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Farey.html (John Farey)

 

 

3.4 The Euclidean Algorithm

Page 97

Biographical information about Euclid can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Euclid.html (Euclid)

Biographical information about Arybhata can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Aryabhata.html (Aryabhata)

 

 

Page 98

 

An applet for computing greatest common divisors can be found at http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html

 

 

 

Page 101

Biographical information about Lamé can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Lame.html (Lamé)

 

 

Page 103

 

An applet for performing the extending Euclidean algorithm can be found at http://users.erols.com/eweidaw/applets/EuclidExtension.html (Applet for Euclid’s Algorithm (Extended))

 

You can use the tool at http://www.numbertheory.org/php/euclid.html to perform the extended Euclidean algorithm.

 

You can find source code for a C program implementing the extended Euclidean algorithm at
http://www.mindspring.com/~pate/crypto/chap02.html

 

 

 

Page 107

 

An applet for the game of Euclid can be found at http://www.cut-the-knot.org/blue/EuclidAlg.shtml (Euclid’s Game)

 

 

 

 

 

3.4    The Fundamental Theorem of Arithmetic

 

Page 109

 

Applets for finding prime factorizations can be found at http://www.math-it.de/Mathematik/Zahlentheorie/Zahl/ZahlApplet.html (The prime factors of an integer n) and at http://wims.unice.fr/wims/wims.cgi?lang=en&module=tool/algebra/factor.en&cmd=new& (factoris)

 

Page 112

 

An applet for computing least common multiples can be found at

http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html

 

You can compute least common multiples of sets of integers using the tool at http://www.numbertheory.org/php/lcm.html (Calculating the LCM of an array of positive integers)

 

 

Page 118

Biographical information about David Hilbert can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Hilbert.html (Hilbert)

 

 

 

 

 

 

3.5    Factorization Methods and the Fermat Numbers

 

Page 124

Biographical information about Pierre de Fermat can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Fermat.html (Fermat)

A succinct report on modern factorization methods can be found as part of the RSA Labs FAQ at
http://www.rsasecurity.com/rsalabs/faq/2-3-4.html (RSA Labs FAQ - What are the best factoring methods in use today?)

Another good place to learn about different factorization methods is in Eric Weisstein's World of Mathematics at
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html (Eric W. Weisstein. "Prime Factorization Algorithms." From MathWorld--A Wolfram Web Resource)

Page 125

 

A description of the factorization of RSA-129 and the quadratic sieve can be found at http://www.willamette.edu/~mjaneba/rsa129.html (Factoring Challenge Conquered)

 

 

Page 127

 
You can learn about the RSA Factoring Challenge at the following Web page at the RSA Data Security site:
http://www.rsasecurity.com/rsalabs/challenges/factoring/ (RSA Factoring Challenge)

 

 

Page 128

The currently known data about the factorization of Fermat numbers can be found on the following page created and maintained by Wilfrid Keller http://www.prothsearch.net/fermat.html  (Fermat factoring status)

Cash prizes are offered for finding prime factors of certain Fermat numbers have been offered by Perfectly Scientific; these may be extended in the future. See http://www.perfsci.com/freegoods.htm#fermat (Perfectly Scientific, Inc.)

 

 

Page 129

Information about the Cunningham project, including the "most wanted" numbers awaiting factorization can be found at
http://www.cerias.purdue.edu/homes/ssw/cun/ (The Cunningham Project)

 

 

 

3.7 Linear Diophantine Equations

Page 133

Biographical information about Diophantus can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Diophantus.html (Diophantus)

 

 

Page 134

Biographical information about Brahmagupta can be found at the MacTutor History of Mathematics Archive at
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Brahmagupta.html (Brahmagupta)

An interactive applet for solving linear diophantine equations can be found at
http://www.thoralf2.uwaterloo.ca/htdocs/linear.html (Linear Diophantine Equations)