CMPSC 40 Chapter Notes - Chapter 4.1-4.3: Number Theory, Modular Arithmetic, Division Algorithm
Document Summary
Number theory = the part of mathematics devoted to the study of the set of integers and their properties. 4. 1: divisibility and modular arithmetic i. ii. iii. set of integers. Definition 1: if and are integers with , we say that divides if there is an integer such that , or equivalently, if is an integer. When divides we say that is a factor or divisor of , and that is a multiple of . We can express using quantifiers as , where the universe of discourse is the. Theorem 1: let , , and be integers, where . Corollary 1: if , , and are integers, where , such that and , then whenever and are integers. Theorem 2: the division algorithm: let be an integer and a positive integer. Then there are unique integers and , with , such that.