Results 1 to 8 of 8

Math Help - modulo arithmetic

  1. #1
    Junior Member
    Joined
    Dec 2007
    From
    University of California, Berkeley
    Posts
    48

    maths help

    ..
    Last edited by yellow4321; March 9th 2008 at 03:39 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by yellow4321 View Post
    you have a calculator that can perform division with remainder 73 but cannot store nor output any number of size greater than +/-200, Show how to calculate 5^6 mod 73.

    i know id use something like that (5^3)^2
    5^6 = (5^3)^2 = 125^2

    And
    125 \equiv 52~\text{mod 73}

    So
    5^6 = 125^2 \equiv 52^2~\text{mod 73}

    Now
    52 = 4 \cdot 13 = 2^2 \cdot 13

    Thus
    5^6 \equiv 52^2 = (2^2 \cdot 13) = 2^4 \cdot 13^2

    So finally:
    \equiv 16 \cdot 169 = 16 \cdot 23 = 8 \cdot 46 = 4 \cdot 92 \equiv 4 \cdot 19 = 76 \equiv 3~\text{mod 73}

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    644
    Hello, yellow4321!

    You have a calculator that can perform division with remainder 73
    but cannot store nor output any number of size greater than \pm200
    Show how to calculate: . 5^6 \pmod{73}

    Calculate successive powers of 5, reducing modulo 73.

    5^1 \;\equiv \;5 \pmod{73}

    5^2\;\equiv\; 25 \pmod{73}

    5^3 \;\equiv\;125 \;\equiv\;\text{-}21 \pmod{73}

    5^4\;\equiv\;\text{-}105 \;\equiv\;\text{-}32 \pmod{73}

    5^5 \;\equiv\;\text{-}160 \;\equiv\;\text{-}14 \pmod{73}

    5^6 \;\equiv\;\text{-}70 \;\equiv\;3 \pmod{73}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by Soroban View Post
    Hello, yellow4321!


    Calculate successive powers of 5, reducing modulo 73.

    5^1 \;\equiv \;5 \pmod{73}

    5^2\;\equiv\; 25 \pmod{73}

    5^3 \;\equiv\;125 \;\equiv\;\text{-}21 \pmod{73}

    5^4\;\equiv\;\text{-}105 \;\equiv\;\text{-}32 \pmod{73}

    5^5 \;\equiv\;\text{-}160 \;\equiv\;\text{-}14 \pmod{73}

    5^6 \;\equiv\;\text{-}70 \;\equiv\;3 \pmod{73}

    I suppose that's a lot easier than my convoluted method!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Dec 2007
    From
    University of California, Berkeley
    Posts
    48
    much appreciated
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Quote Originally Posted by yellow4321 View Post
    you have a calculator that can perform division with remainder 73 but cannot store nor output any number of size greater than +/-200, Show how to calculate 5^6 mod 73.

    i know id use something like that (5^3)^2
    By Fermat's Little Theorem,

    5^{72} \equiv 1 \pmod{73}

    But

    \underbrace{(5^6)(5^6)(5^6)...}_{12\ times}\equiv \underbrace{(3)(3)(3)...}_{12 \ times} \pmod{73}

    \Rightarrow 5^{72} \equiv 36 \pmod{73}

    Is this correct? Why or why not?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by DivideBy0 View Post
    By Fermat's Little Theorem,

    5^{72} \equiv 1 \pmod{73}

    But

    \underbrace{(5^6)(5^6)(5^6)...}_{12\ times}\equiv \underbrace{(3)(3)(3)...}_{12 \ times} \pmod{73}

    \Rightarrow 5^{72} \equiv 36 \pmod{73}

    Is this correct? Why or why not?
    Isnt \underbrace{(3)(3)(3)...}_{12 \ times} = 3^{12}??
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Ah, ok thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modulo arithmetic proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 31st 2011, 08:27 AM
  2. modulo arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 15th 2010, 07:10 AM
  3. Modulo Arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 4th 2009, 11:47 AM
  4. Modulo Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 9th 2009, 03:56 AM
  5. Modulo arithmetic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 2nd 2007, 05:16 AM

Search Tags


/mathhelpforum @mathhelpforum