Understanding Modular Arithmetic and Rings in Mathematics

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}
Addition mod n:
 (x + y) mod n
Multiplication mod n:
 
xy 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
(34
74
 + 120) mod 11
(56·72 + 62) mod 7
Modular Arithmetic
2
10
 mod 7 = (2
5
 mod 7) (2
5
 mod 7) mod 7
Modular Arithmetic
Any multiple of n acts like 0 mod n:
 (123
5
 ·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
01234
0      1      2      3      4
01234
x
+
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”
-1
0
1
2
3
4
5
6
7
8
9
0
-9
-8
-7
-6
-5
-4
-3
-2
Example
: n = 5
Slide Note
Embed
Share

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.


Uploaded on Apr 20, 2024 | 6 Views


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


  1. Modular Arithmetic ICS 6D Sandy Irani

  2. 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

  3. DIV and MOD functions for n < 0 q = floor(n/d) r = n - q d Example: n = -25, d = 6

  4. DIV and MOD functions for n < 0 q = floor(n/d) r = n - q d Example n = -75, d = 12

  5. 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

  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

  7. 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

  8. 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 =

  9. Modular Arithmetic (3474 + 120) mod 11 (56 72 + 62) mod 7

  10. Modular Arithmetic 210 mod 7 = (25 mod 7) (25 mod 7) mod 7

  11. Modular Arithmetic Any multiple of n acts like 0 mod n: (1235 170 + 2) mod 17 (8 + 170 98) mod 17 =

  12. 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.

  13. 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

  14. 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

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#