Math Ladder · College

Number Theory

Divisibility and the Euclidean algorithm, primes, modular arithmetic, the theorems of Fermat and Euler, RSA, quadratic residues and continued fractions.

0 of 41 topics passed

Start this course Skill map

41 topics in 8 units. Builds on Discrete Math. Leads to Abstract Algebra. Not sure this is the right course? Find your rung.

  • Passed
  • Review due
  • Learning
  • Ready to learn
  • Needs an earlier topic

Unit 1 Divisibility and the Euclidean Algorithm

6 topics

Divide with remainders, find greatest common divisors quickly, and solve ax + by = c in whole numbers.

  1. Divisibility
  2. The Division Algorithm
  3. Writing Numbers in Other Bases
  4. The Euclidean Algorithm
  5. Bézout's Identity and the Extended Euclidean Algorithm
  6. Linear Diophantine Equations

Unit 2 Primes and Factorization

8 topics

Test for primes, factor uniquely, and use factorizations to count divisors and study how primes are spread out.

  1. Testing Primes and the Sieve of Eratosthenes
  2. Unique Prime Factorization
  3. gcd and lcm from Prime Factorizations
  4. Counting and Adding Divisors
  5. Perfect Numbers and Mersenne Primes
  6. Prime Powers in n!
  7. Infinitely Many Primes
  8. How Common Are Primes?

Unit 3 Congruences

7 topics

Calculate with remainders: modular arithmetic, fast powers, inverses, linear congruences and the Chinese Remainder Theorem.

  1. Congruence mod n
  2. Arithmetic mod n
  3. Divisibility Tests from Congruences
  4. Fast Powers mod n
  5. Modular Inverses
  6. Linear Congruences
  7. The Chinese Remainder Theorem

Unit 4 Fermat, Euler and Wilson

5 topics

Tame huge powers with the theorems of Fermat and Euler, count units with φ, and see why passing Fermat's test does not prove a number prime.

  1. Fermat's Little Theorem
  2. Wilson's Theorem
  3. Euler's Phi Function
  4. Euler's Theorem
  5. Fermat Tests and Pseudoprimes

Unit 5 Orders and Primitive Roots

3 topics

Find how long the powers of a number take to repeat, find primitive roots, and meet discrete logarithms.

  1. The Order of an Element
  2. Primitive Roots
  3. Discrete Logarithms

Unit 6 Cryptography

3 topics

Put modular arithmetic to work in ciphers, key exchange and RSA.

  1. Shift and Affine Ciphers
  2. Diffie–Hellman Key Exchange
  3. The RSA Cryptosystem

Unit 7 Quadratic Residues

4 topics

Decide which numbers are perfect squares mod p, with Euler's criterion and the law of quadratic reciprocity.

  1. Squares mod p
  2. The Legendre Symbol and Euler's Criterion
  3. Is −1 or 2 a Square mod p?
  4. Quadratic Reciprocity

Unit 8 Diophantine Equations and Continued Fractions

5 topics

Find whole-number solutions of x² + y² = z², sums of two squares and Pell's equation, with continued fractions as the tool.

  1. Pythagorean Triples
  2. Sums of Two Squares
  3. Continued Fractions of Rational Numbers
  4. Continued Fractions of Square Roots
  5. Pell's Equation
@teddyrookbook GitHub