Results 1 to 9 of 9

Math Help - Modular Arithmetic

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    190

    Modular Arithmetic

    Hi I do not understand the answers to these 2 questions:

    1. Can you work out what the remainder is when 2^1000 is divided by 7?

    As 1000 = 333 × 3 + 1 then 2^1000 leaves remainder 2 when divided by 7.


    2. Expand the brackets of (x − 1)(x − 7) and (x − 3)(x − 5) in mod 8 arithmetic.

    (x − 1)(x − 7) = x^2 − 8x + 7 = x^2 − 1 (mod 8);
    (x − 3)(x − 5) = x^2 − 8x + 15 = x^2 − 1 (mod 8).

    Why is there a "-1", we dont take remainders to be negative?

    I'm new to modular arithmetic, just started it right now, so apologies if its a stupid qustion.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by Aquafina View Post
    Hi I do not understand the answers to these 2 questions:

    1. Can you work out what the remainder is when 2^1000 is divided by 7?

    As 1000 = 333 × 3 + 1 then 2^1000 leaves remainder 2 when divided by 7.


    2. Expand the brackets of (x − 1)(x − 7) and (x − 3)(x − 5) in mod 8 arithmetic.

    (x − 1)(x − 7) = x^2 − 8x + 7 = x^2 − 1 (mod 8);
    (x − 3)(x − 5) = x^2 − 8x + 15 = x^2 − 1 (mod 8).

    Why is there a "-1", we dont take remainders to be negative?

    I'm new to modular arithmetic, just started it right now, so apologies if its a stupid qustion.

    in general

    ax(mod a) ==0 x is an integer

    a==b(mod m) that's mean

    m\mid a-b


    8=2^3==1(mod 7)

    2^{1000}=2^{999}\cdot 2^1 = (2^3)^{333}\cdot 2 ==2 (mod 7)

    since

    (2^3)^{333}(mod 7) == 1^{333}\cdot 2=2

    x^2-8x+7 ==x^2 -(0)x -1 (mod 8)

    7==-1(mod 8 )
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by Amer View Post
    in general

    ax(mod a) ==0 x is an integer

    a==b(mod m) that's mean

    m\mid a-b


    8=2^3==1(mod 7)

    2^{1000}=2^{999}\cdot 2^1 = (2^3)^{333}\cdot 2 ==2 (mod 7)

    since

    (2^3)^{333}(mod 7) == 1^{333}\cdot 2=2

    x^2-8x+7 ==x^2 -(0)x -1 (mod 8)

    7==-1(mod 8 )
    hi doesnt 7 == 7(mod 8) ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by Aquafina View Post
    hi doesnt 7 == 7(mod 8) ?
    that's right since any number divides zero you can say

    a==a(mod x)

    x \mid 0 is true for all integer numbers x,a
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    a \equiv b \ (mod \ c) \Leftrightarrow c|a-b

    7 \equiv -1 \ (mod \ 8) \Leftrightarrow 8|7-(-1) i.e. 8|7+1 or 8|8

    If you want, you can think of it this way ... positive numbers means moving "forward", while negative means moving "backwards" ... can you see how moving forward 7 is the same as moving back 1 by mod 8?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by Bingk View Post
    a \equiv b \ (mod \ c) \Leftrightarrow c|a-b

    7 \equiv -1 \ (mod \ 8) \Leftrightarrow 8|7-(-1) i.e. 8|7+1 or 8|8

    If you want, you can think of it this way ... positive numbers means moving "forward", while negative means moving "backwards" ... can you see how moving forward 7 is the same as moving back 1 by mod 8?
    Thanks, so we can take 7 or -1, depending on what we need in our answer?

    Am i supposed to use this to solve the next question

    Without direct calculation, determine the next to last digit in 2^1000? (i.e. the one in the “tens” column.) [Hint: listing the last two digits of each power of 2 you should find a cycle of length 20 which first starts with the second power.]

    I don't understand the hint. I've written down the last 2 digits till 2^20, but dont seem to find a pattern. Is this what I was supposed to do?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by Aquafina View Post
    Thanks, so we can take 7 or -1, depending on what we need in our answer?

    Am i supposed to use this to solve the next question

    Without direct calculation, determine the next to last digit in 2^1000? (i.e. the one in the “tens” column.) [Hint: listing the last two digits of each power of 2 you should find a cycle of length 20 which first starts with the second power.]

    I don't understand the hint. I've written down the last 2 digits till 2^20, but dont seem to find a pattern. Is this what I was supposed to do?

    2^2=04
    2^3=08
    2^4=16
    2^5=32
    2^6=64
    2^7=128
    2^8=256
    2^9=512
    2^{10}=1024
    2^{11}=2048
    2^{12}=4096
    2^{13}=8192
    2^{14}=16384
    2^{15}=22768
    2^{16}=25536
    2^{17}=51072
    2^{18}=102144
    2^{19}=204288
    2^{20}=408576
    2^{21}=817152
    2^{22}=1634304

    the last two digits in 2^2 equal to the last two digits in 2^22 and the last two digits in 2^42 is 04 like 2^2 and so on
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by Amer View Post
    2^2=04
    2^3=08
    2^4=16
    2^5=32
    2^6=64
    2^7=128
    2^8=256
    2^9=512
    2^{10}=1024
    2^{11}=2048
    2^{12}=4096
    2^{13}=8192
    2^{14}=16384
    2^{15}=22768
    2^{16}=25536
    2^{17}=51072
    2^{18}=102144
    2^{19}=204288
    2^{20}=408576
    2^{21}=817152
    2^{22}=1634304

    the last two digits in 2^2 equal to the last two digits in 2^22 and the last two digits in 2^42 is 04 like 2^2 and so on
    Hi so 2^982 will be the last number to end in a 04, then we still have 18 more powers to go to get 1000. 2^1000 ends in 76.

    So i did:

    2^1000 = 2^982 x 2^18
    = .....04 x ......44
    = ........76?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,971
    Thanks
    1121
    Quote Originally Posted by Aquafina View Post
    Hi I do not understand the answers to these 2 questions:

    1. Can you work out what the remainder is when 2^1000 is divided by 7?

    As 1000 = 333 × 3 + 1 then 2^1000 leaves remainder 2 when divided by 7.
    Since 1000= 333 x 3+ 1, 2^1000= 2^(333 x 3+ 1)= 2((2^3)^333)= 2(8^333). Now 8= 7+ 1 so 8^n= (7+ 1)^n and, by the binomial theorem, that is a sum of multiples of powers of 7 plus 1. 8^n has remainder 1 when divided by 7 for all positive n.


    2. Expand the brackets of (x − 1)(x − 7) and (x − 3)(x − 5) in mod 8 arithmetic.

    (x − 1)(x − 7) = x^2 − 8x + 7 = x^2 − 1 (mod 8);
    (x − 3)(x − 5) = x^2 − 8x + 15 = x^2 − 1 (mod 8).

    Why is there a "-1", we dont take remainders to be negative?
    The convention is to reduce all number "mod n" to between 0 and n-1. But, for example, 7, 15, -1 are all equivalent to 7 because they are a multiple of 8 plus 7 (in the case of -1, (-1)8+ 7= -1) but we don't have to. Yes, x^2- 1 is equivalent to x^2+ 7 (mod 8) but we can leave it as x^2- 1 if we want.

    I'm new to modular arithmetic, just started it right now, so apologies if its a stupid qustion.[/QUOTE]
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 05:08 AM
  2. Arithmetic Modular help!!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 24th 2010, 08:44 AM
  3. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 12:17 PM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 03:17 PM
  5. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2008, 08:47 AM

Search Tags


/mathhelpforum @mathhelpforum