Results 1 to 4 of 4

Math Help - Modular Question

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    136
    Awards
    1

    Modular Question

    Hi again,

    I have been able to do mod questions such as:

    .45 Ξ 3 (mod 6) and 104 Ξ 2 (mod 6)

    45 - 3 = 42
    42 / 6 = 7 therefore 45 less 3 (42) is a multiple of 6

    104 - 2 = 102
    102 / 6 = 17 therefore 104 less 2 (102) is a multiple of 6


    I am now asked to do a question with a massive number that a calculator can't do.


    Verify 675⁰⁷ mod 713.


    How is this done???

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,713
    Thanks
    633
    Hello, Joel!

    I have been able to do mod questions such as:

    Verify: . 104 \equiv 2\text{ (mod 6)}

    . . 104  -  2 \:=\: 102

    . . 102 \div6  \:=\: 17\qquad \text{Therefore: }\:104 - 2\text{ is a multiple of 6}


    I am now asked to do a question with a massive number that a calculator can't do.

    . . Verify: . 675^3 \equiv 29\text{ (mod 713)} .[1]

    How is this done?

    We note that: . 675 \equiv -38\text{ (mod 713)}

    Substitute into [1]: . (-38)^3 \equiv 29\text{ (mod 713)} \quad\Rightarrow\quad -54,\!872 \equiv 29\text{ (mod 713)}

    . . -54,\!872 - 29 \:=\:-54,\!901

    . . -54,\!901 \div 713 \:=\:-77\qquad\text{Hence: }(-38)^3 - 29\text{ is a multiple of 713.}


    Therefore: . 675^3 - 29 is a multiple of 713.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2009
    Posts
    136
    Awards
    1
    675 to the power of 307 is the question.... how do you get .[1] ???
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Joel View Post

    [snip]
    I am now asked to do a question with a massive number that a calculator can't do.

    Verify 675⁰⁷ mod 713.

    How is this done???
    675 to the power of 307 is the question.... how do you get
    From where did the 307 arrive?

    The question is what is  675^{307} \, mod \, 713 ?

    This is the method I use:

    307 = 256 + 32 + 16 + 3

     675^{256} \times 675^{32} \times 675^{16} \times 675^3 = 675^{307}


     675^2 \equiv 18 \, mod(713)

     675^4 \equiv 18^2 \equiv 324 \, mod(713)

     675^8 \equiv 18^4 \equiv 324^2 \equiv 165 \, mod(713)

     675^{16} \equiv 165^2 \equiv 131 \, mod(713)
    That takes care of 1 of the values.

     675^{32} \equiv 131^2 \equiv 49 \, mod(713)
    That's another one.

     675^{64} \equiv 49^2 \equiv 262 \, mod(713)
     675^{128} \equiv 262^2 \equiv 196 \, mod(713)
     675^{256} \equiv 196^2 \equiv 627 \, mod(713)
    Another one.

    And the last one.
     675^3 \equiv 675^2 \times 675 \equiv 18 \times 675 \equiv 29 \, mod(713)


    summary:

     \left ( 627 \times 49 \times 131 \times 29 \right ) \equiv 3 \, mod(713)

    Thus

     675^{307} \, \equiv 3 \, mod \,\; 713





    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 11th 2011, 08:50 PM
  2. A question on modular notation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 28th 2010, 12:16 AM
  3. A question on modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 19th 2010, 04:25 AM
  4. Another modular inverse question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 25th 2010, 07:14 PM
  5. Modular solutions question
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: May 1st 2008, 11:45 AM

Search Tags


/mathhelpforum @mathhelpforum