Integer Division and Finding Factors/Multiplies

• 9.1: The Division Algorithm
• 9.2: Modular arithmetic
• 9.3: Prime factorizations
• 9.4: Factoring and primality testing
• 9.5: Greatest common divisor and Euclid’s algorithm

9.1: The Division Algorithm

• Integer division is division where the input and output must always be integers
  • 9 / 4 returns 2 remainder 1 instead of 2.25
  • Definition of division:
• Linear combination: The sum of the multiples of two numbers
  • If a number x can divide two numbers y and z, then x can divide any linear combination of y and z
• The Division Algorithm defines division and remainders
  • Theorem:
  • Definitions derived:
  • Note that the Division Algorithm states that applying the modulo operator on negative numbers will never return a negative number; -7 % 4 = 1, not -3

9.2: Modular arithmetic

• Mod m can be seen as a function that maps an integer to the target {0, 1, 2, …, m-1}
  • If we want addition and multiplication functions to return integers in a certain set, then we can use addition mod m and multiplication mod m (adding and multiplying then applying mod m, respectively) in order to do so
  • The set {0, 1, 2, …, m-1} along with addition mod m and multiplication mod m creates a closed mathematical system called a ring, denoted by Z_m
  • Z₅ multiplication and addition tables:
• For a fixed m, two integers x and y are congruent if x mod m = y mod m
  • This is denoted as ${x \equiv y \text{ (mod m)}}$

  • Can also be defined as m

    (x - y), or m evenly divides x - y

• The mod operation has the same precedence as multiplication or division, so 6 * 2 mod 7 = 12 mod 7 = 5
• To compute other arithmetic operations mod m, we can use the following definitions:

9.3: Prime factorizations

• The Fundamental Theorem of Arithmetic states that every positive integer (besides 1) can be uniquely expressed as a product of prime numbers
  • The multiplicity of a prime number in a prime factorization is the number of times p appears in the factorization
    • For example, in 12, 2 has a multiplicity of 2 and 3 has a multiplicity of 1
• The greatest common divisor (gcd) of two integers is the greatest integer that divides both of them
• The least common multiple (lcm) of two inegers is the smallest positive integer that is a multiple of them
• Two numbers are relatively prime if their gcd is 1
• Formulas for finding the GCD and LCM of two integers with known prime factorizations:

9.4: Factoring and primality testing

• Many ways to find if a number is prime
  • A brute force algorithm solves a problem by trying all possible inputs and outputs
• There are an infinite amount of primes, with proof:
  • The Prime Number Theorem stipulates how dense prime numbers are packed among integers:
  • This theorem can be interpreted as follows: If a random number is randomly selected from 2 to x, then the chance that the number is prime is approximately 1/ln(x)

9.5: Greatest common divisor and Euclid’s algorithm

• Euclid’s algorithm gives a way to recursively calculate the GCD of any two integers
  • Algorithm: gcd(x, y) = gcd(y mod x, x)
  • Written out in code:
• The Extended Euclidean Algorithm states that gcd(x, y) = sx + ty
• The multiplicative inverse mod n (AKA inverse mod n) of an integer x is an integer s such that sx mod n = 1
  • For example, 3 is the inverse of 7 mod 10 because 3 * 7 mod 10 = 21 mod 10 = 1
• This section is something you need to practice; can’t really understand off of notes