Understanding Modular Arithmetic and Rings in Mathematics
Exploring the concepts of modular arithmetic and rings in mathematics, including properties, operations, and examples. Learn how modular arithmetic simplifies computations and how rings define closed mathematical systems with specific laws and identities.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Modular Arithmetic ICS 6D Sandy Irani
DIV and MOD functions d an integer d 1 n an integer There are unique integers q for quotient r for remainder Such that r {0, 1, 2, ,d-1} n = d q + r
DIV and MOD functions for n < 0 q = floor(n/d) r = n - q d Example: n = -25, d = 6
DIV and MOD functions for n < 0 q = floor(n/d) r = n - q d Example n = -75, d = 12
DIV and MOD functions for n < 0 r = n q = 0 while (r < 0) r = r + d q = q - 1 Example n = -25, d = 6
DIV and MOD functions for n < 0 r = n q = 0 while (r < 0) r = r + d q = q -1 Example n = -75, d = 12
Modular Arithmetic Mod n is a function from to {0, 1, , n-1} Multiplication mod n: xy mod n Addition mod n: (x + y) mod n
Modular Arithmetic In computing arithmetic expressions mod n, can compute partial results mod n and the result is the same: ((x mod n) + (y mod n)) mod n = (x + y) mod n (158 + 219) mod 5 = ((x mod n) (y mod n)) mod n = (x y) mod n (158 219) mod 5 =
Modular Arithmetic (3474 + 120) mod 11 (56 72 + 62) mod 7
Modular Arithmetic 210 mod 7 = (25 mod 7) (25 mod 7) mod 7
Modular Arithmetic Any multiple of n acts like 0 mod n: (1235 170 + 2) mod 17 (8 + 170 98) mod 17 =
Rings A ring is a closed mathematical system with addition and multiplication operations that Obeys certain laws (associative, distributive, etc.) Has identities: 0 + x = x 1 x = x The elements of a ring can be different kinds of objects: Polynomials, sequences, numbers, etc.
The ring n The ring n is the set {0, 1, 2, , n-1} along with Addition mod n Multiplication mod n Example: 5 0 1 2 3 4 + 0 1 2 3 4 x 0 1 2 3 4 0 1 2 3 4
Equivalence mod n x mod n = y mod n (x-y) = integer multiple of n x y mod n x is equivalent to y mod n Example: n = 5 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
