CMPSC 40 Lecture Notes - Lecture 16: Prime Number Theorem, Additive Inverse, Congruence Relation
Document Summary
Multiplying both sides of a valid congruence by an integer preserves validity. Integer division: if and are integers with , then divides if there exists an integer such that. Congruence relation: if and are integers and is a positive integer, then is congruent to modulo if divides. If holds, then , where is any integer, holds as well. If holds, then , where is any integer, holds. Computing the function of products and sums sum of two integers when divided by from the remainders when each is divided by. Corollary: let be a positive integer and let and be integers. Definitions: let be the set of nonnegative integers less than. Using these operations is said to be doing arithmetic modulo. We use the following corollary to theorem 5 to compute the remainder of the product or. Dividing a congruence by an integer does not produce a valid congruence. Adding an integer to both sides of a valid congruence preserves validity.
