4. The Integers

This chapter will serve as an introduction to number theory, the study of integers and their properties.

Key considerations in number theory are division and prime numbers. This extendeds to modular arithmetic, congruence relations, and even cryptography. Number theory is typically a very “pure” mathematical topic, but it has many practical applications. Of course, cryptography is very useful in practice, including internet security, banking, and more. Number theory also has many other applications in computer science, as we will (hopefully) explore.

• 4.1. Divisibility and Modular Arithmetic
  • 4.1.1. Divisibility
  • 4.1.2. Division with remainder
  • 4.1.3. Congruence Relations
    • Modulo as “removing multiples”
    • mod versus \(\bmod\)
    • Congruence, sums, and products
  • 4.1.4. Arithmetic modulo \(m\)
    • Properties of arithmetic modulo \(m\)
    • Congruence as equivalence relations
  • 4.1.5. Exercises
• 4.2. Greatest Common Divisors and Primes
  • 4.2.1. Prime numbers
  • 4.2.2. Finding Primes
  • 4.2.3. Computing Primes
  • 4.2.4. Greatest Common Divisors
    • Least Common Multiples
    • Euclidean Algorithm
    • Bézout Relations and GCDs
    • Consequences of Bézout
  • 4.2.5. Exercises
• 4.3. Solving Congruences
  • 4.3.1. Linear Congruences
    • Modular Inverses
    • Computing Modular Inverses
  • 4.3.2. Systems of Linear Congruences
    • Chinese Remainder Theorem
  • 4.3.3. Exercises
• 4.4. Integer Representations
  • 4.4.1. Positional Number Systems
    • Radix-\(r\) representations
    • Radix-\(r\) numbers in practice
  • 4.4.2. Converting to radix-\(r\)
  • 4.4.3. Binary, Octal, Hex Conversion
  • 4.4.4. Binary Arithmetic
  • 4.4.5. Exercises
• 4.5. Applications
  • 4.5.1. Pseudo-Random Numbers
  • 4.5.2. Cryptogrophy
    • Ciphers
    • RSA Encryption