COMPSCI 70 Chapter Notes - Chapter 6: Coprime Integers, Modular Multiplicative Inverse, Modulus Guitars
31 Jan 2018
School
Department
Course
Professor
Document Summary
Modular arithmetic modular arithmetic - involves performing all arithmetic operations relative to a modulus (a fixed number) If the common divisors are the same, then the largest element (the gcd) must also be the same. Keep adding the mod number until you get a positive number. The positive number is the remainder. or or all give the remainder of. If and , then and (converse is true too) , because are both divisible by so is divisible by d. The set of common divisors between is equal to the set of common divisors between and (and the set of common divisors between and ) The greatest common divisor of and are the same: and and would have the same set of divisors as because and have the same divisors (they are just the negative of one another) For all divisors of and , we know that . For all divisors of and , we know that , which means .
