Scribd Logo
Upload

Welcome to Scribd!

  • 20 views

    Modular Arithmetic Class1

    Uploaded by

    alok_b
    The document discusses modular arithmetic and congruence modulo. Modular arithmetic involves clock arithmetic and operations that wrap around after reaching 12 or 24 hours. Congruence modulo defines when two numbers have the same remainder when divided by a given number. Some properties and examples of modular arithmetic and congruence modulo are provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Modular Arithmetic Class1

    Uploaded by

    alok_b
    20 views2 pages
    The document discusses modular arithmetic and congruence modulo. Modular arithmetic involves clock arithmetic and operations that wrap around after reaching 12 or 24 hours. Congruence modulo defines when two numbers have the same remainder when divided by a given number. Some properties and examples of modular arithmetic and congruence modulo are provided.

    Original Title

    modular_Arithmetic_Class1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses modular arithmetic and congruence modulo. Modular arithmetic involves clock arithmetic and operations that wrap around after reaching 12 or 24 hours. Congruence modulo defines when two numbers have the same remainder when divided by a given number. Some properties and examples of modular arithmetic and congruence modulo are provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    20 views2 pages

    Modular Arithmetic Class1

    Uploaded by

    alok_b
    The document discusses modular arithmetic and congruence modulo. Modular arithmetic involves clock arithmetic and operations that wrap around after reaching 12 or 24 hours. Congruence modulo defines when two numbers have the same remainder when divided by a given number. Some properties and examples of modular arithmetic and congruence modulo are provided.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Modular Arithmetic

    Idea :

    12 12 1
    11 1 11
    10 2 10 2
    9 3 9 3

    8 4 8 4
    7 6 5 7 6 5
    8+7=3 3 - 5 = 10

    The basic idea of modular arithmetic is as follows for 12 hrs clock.


    3 hours after 10 o’clock is 1 o’clock (because 10 + 3 =13 and we subtract 12).
    Now, 17 hours after 9 o’clock will be 2 o’clock, because 17 + 9 = 26 and we must subtract 2 x
    12 = 24 to find where the hand is pointing on the clock face.
    9 hours before 4 o’clock is 7 o’clock, since 4 – 9 = - 5, and now we add 12 to get the answer
    7.
    When we have 24-hour clock, then arithmetic will be as follows –
    17 hours after 16 hours is 9 hours, since 17 + 16 = 33, and then 24 is subtracted to get the time.
    Now, 11 hours before 9 hours is 22 hours (9 – 11 = - 2; then add 24 to get 22).

    Congruent Modulo
    Note that some numbers have the same remainder when they are divided by a particular integer.
    For example, 47  5 has remainder 2 and 12  5 also has remainder 2.
    This similarity helps us to define a new number relationship called congruence.

    If two integers a and b have the property that a – b is divisible by another m ( m  1) then a
    and b are called congruent modulo m and write a  b (mod m ) .

    Example
    47 ≡ 2(mod 5) and 12 ≡ 2(mod 5)
    Now 47 ≡ 12(mod 5) as (47 – 12) is divisible by 5.
    47 and 12 are called congruent modulo 5.

    Similarly, – 16 ≡ 8 (mod 12) as – 16 – 8 is divisible by 12.

    Now we look at general modular arithmetic modulo n, where n is an integer greater than 1.
    1. if a ≡ b(mod n) then a – b is divisible by n.
    2. if a number a leaves a remainder of r after division by n, then a ≡ r(mod n).

    Some rules that modular arithmetic obeys are –


    1. if a ≡ b(mod n) and c ≡ d(mod n) then
    a + c ≡ b+d(mod n) and a – c ≡ b–d(mod n).
    2. if a ≡ b(mod n) and c ≡ d(mod n) then ac ≡ bd(mod n).
    3. a+b (mod n) ≡ b+a (mod n) [Commutative Law]
    4. Associative Laws
    (a+b) + c (mod n) ≡ a + (b+c) (mod n) and (ab)c (mod n) ≡ a(bc)(mod n)
    5. Distributive Laws
    a(b + c) (mod n) ≡ ab + ac (mod n) and (a + b)c ≡ ac + bc(mod n)

    Example 1:

    Find the possible values of m that satisfy each congruence:


    (a) 13 ≡ 3(mod m) (b) 15 ≡ 4(mod m)

    Solution:
    (a) By definition of congruence, 13 – 3 = 10 must be divisible by m. So the possible values
    of m are the positive divisors of 10 : hence m ∈ { 2, 5, 10 }as by definition m  1 .
    (b) Here 15 – 4 = 11 must be divisible by m. So m can only be 11.

    Example 2:

    If today is Wednesday, what day of the week will it be in 100 days’ time?

    Solution:

    Sun Mon Tue Wed Thurs Fri Sat


    0 1 2 3 4 5 6

    Since we have numbers 0, 1, 2 , 3, 4, 5 and 6, we will do our arithmetic in modulo 7.

    Today is Wednesday (i.e. day 3) hence to find 100 days later, we can write
    3 + 100 = 103 ≡ 5(mod 7).

    So the answer is the 5th day which is Friday.

    You might also like