Natural Numbers Pigeonhole principle Heart of Math Chapter 2.1 Proof by Induction http://en.wikipedia.org/wiki/Mathematical_induction Fibonacci Numbers and Related Ideas Fibonacci Numbers Heart of Math Chapter 2.2 http://en.wikipedia.org/wiki/Fibonacci_sequence Continued Fractions http://en.wikipedia.org/wiki/Continued_fraction http://www.mathpath.org/concepts/cont.frac.htm Golden Ration (\phi) Heart of Math Chapter 2.2 http://en.wikipedia.org/wiki/Golden_ratio (note that the golden ratio and the Euler function do not have any obvious connection even though they both are represented by the same Greek letter \phi). Prime Numbers, Multiplication and Division Infinitude of Primes Heart of Math Chapter 2.3 Magic of Numbers Chapter 10.5 http://primes.utm.edu/notes/proofs/infinite/euclids.html Fundamental Theorem of Arithmetic Heart of Math Chapter 2.3 Magic of Numbers Chapter 11.4 http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic Division with Remainder Heart of Math Chapter 2.3 http://en.wikipedia.org/wiki/Remainder Greatest Common Divisor Magic of Numbers Chapter 8.3 http://en.wikipedia.org/wiki/Greatest_common_divisor http://www.math.com/school/subject1/lessons/S1U3L2GL.html Sieve of Eratosthenes Magic of Numbers Chapter 10.3 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm Euclid's Algorithm Magic of Numbers Chapter 8.4, 8.5 http://www.antilles.k12.vi.us/math/cryptotut/euclidean_algorithm.htm http://en.wikipedia.org/wiki/Euclidean_algorithm Extended Euclid's Algorithm (i.e. finding x, y such that ax + by = gcd(a,b)) http://www.antilles.k12.vi.us/math/cryptotut/euclidean_algorithm.htm http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm Modular (or Clock) Arithmetic Equivalence Relations http://en.wikipedia.org/wiki/Equivalence_relation Calculation in Modular (or Clock) Arithmetic Heart of Math Chapter 2.4 Magic of Numbers Chapter 15 http://www.math.csusb.edu/faculty/susan/modular/modular.html Multiplicative Inverses Magic of Numbers Chapter 17.4 http://en.wikipedia.org/wiki/Modular_multiplicative_inverse Check Digits on Bar Codes Heart of Math Chapter 2.4 http://www.cs.queensu.ca/~bradbury/checkdigit/upccheck.htm Fermat's Little Theorem Heart of Math Chapter 2.5 http://en.wikipedia.org/wiki/Fermat's_little_theorem Euler's Function Magic of Numbers Chapter 13.2 http://en.wikipedia.org/wiki/Euler%27s_totient_function Euler's Theorem Magic of Numbers Chapter 20.4 http://en.wikipedia.org/wiki/Euler%27s_theorem Codes Substitution Codes Magic of Numbers Chapter 21.1 http://www.simonsingh.net/The_Black_Chamber/frequencypuzzle.htm http://en.wikipedia.org/wiki/Substitution_cipher http://www.otr.com/ciphers.shtml RSA or Public Key Cryptography Heart of Math Chapter 2.5 Magic of Numbers Chapter 22 http://en.wikipedia.org/wiki/RSA http://en.wikipedia.org/wiki/Public-key_cryptography Prime Factorization Heart of Math Chapter 2.4 http://en.wikipedia.org/wiki/Prime_factor http://www.gomath.com/algebra/factor.php http://www.amby.com/educate/math/2-1_fact.html Rational and Irrational Numbers Rational Numbers (i.e. Fractions) Heart of Math Chapter 2.6 http://en.wikipedia.org/wiki/Fraction_%28mathematics%29 http://en.wikipedia.org/wiki/In_lowest_terms http://en.wikipedia.org/wiki/Rational_number Irrational Numbers Heart of Math Chapter 2.6 Magic of Numbers Chapter 12.6 http://en.wikipedia.org/wiki/Irrational_number http://www.mathsisfun.com/irrational-numbers.html Square Roots and nth Roots Heart of Math Chapter 2.6 http://en.wikipedia.org/wiki/Nth_root Real Line Heart of Math Chapter 2.7 http://www.langara.bc.ca/mathstats/resource/onWeb/precalculus/reals/numline.htm Decimal Expansions of Real Numbers Heart of Math Chapter 2.7 http://en.wikipedia.org/wiki/Recurring_decimal http://en.wikipedia.org/wiki/Decimal_representation Turning Repeating Decimals into Fractions. Heart of Math Chapter 2.7 http://www.webmath.com/dec2fract.html http://en.wikipedia.org/wiki/Fraction_(mathematics)