Results 1 to 4 of 4

Thread: 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
    12,028
    Thanks
    848
    Hello, Joel!

    I have been able to do mod questions such as:

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

    . . $\displaystyle 104 - 2 \:=\: 102$

    . . $\displaystyle 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: .$\displaystyle 675^3 \equiv 29\text{ (mod 713)}$ .[1]

    How is this done?

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

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

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

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


    Therefore: .$\displaystyle 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 $\displaystyle 675^{307} \, mod \, 713 $ ?

    This is the method I use:

    307 = 256 + 32 + 16 + 3

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


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

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

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

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

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

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

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


    summary:

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

    Thus

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





    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: Nov 11th 2011, 08:50 PM
  2. A question on modular notation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 28th 2010, 12:16 AM
  3. A question on modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Nov 19th 2010, 04:25 AM
  4. Another modular inverse question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 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 for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum