Results 1 to 4 of 4

Math Help - powers modulo m help needed

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    powers modulo m help needed

    I see the pattern when the numbers are raised to a small integer, but once at a^8 I am lost....Can someone please help me with the following....

    a=28 28^749(mod1174)
    a^1 = 28(mod1147)
    a^2 = 784 (mod1147)
    a^4 = 1011 (mod1147)
    I see how 1011 came by...28^4=614656/1147=535
    then 614656-535*1147=1011
    However, for the following
    a^8 = {I know its 144 from the book but how did that come about?}
    if I take 28^8 its to large to really work with the actual interger..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,894
    Thanks
    326
    Awards
    1
    Quote Originally Posted by duggaboy View Post
    I see the pattern when the numbers are raised to a small integer, but once at a^8 I am lost....Can someone please help me with the following....

    a=28 28^749(mod1174)
    a^1 = 28(mod1147)
    a^2 = 784 (mod1147)
    a^4 = 1011 (mod1147)
    I see how 1011 came by...28^4=614656/1147=535
    then 614656-535*1147=1011
    However, for the following
    a^8 = {I know its 144 from the book but how did that come about?}
    if I take 28^8 its to large to really work with the actual interger..
    a^8 \equiv (a^4)^2 \equiv 1011^2 \text{ mod(1147)}

    \equiv 1022121 - 891 \cdot 1147 \equiv 144

    So
    a^{16} \equiv (a^8)^2 \equiv 144^2~\text{mod(28)}
    etc.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2008
    Posts
    39
    awesome thank you
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    629
    Hello, duggaboy!

    Use the "reduced" forms . . .


    a\:=\:28 . Find: . 28^{749} \pmod{1174}

    \begin{array}{cccccccc}a^1 &=& 28 &\equiv & 28 & & & \pmod{1174} \\<br />
a^2 & \equiv & 784 &\equiv &784 & & & \pmod{1174} \\<br />
a^4 & \equiv & 784^2 & \equiv & 614,656 & \equiv & 654 & \pmod{1174} \\<br />
a^8 & \equiv & 654^2 & \equiv & 427,716 & \equiv & 380 & \pmod{1174} \\<br />
a^{16} &\equiv & 380^2 & \equiv & 144,440 & \equiv & 1172 & \pmod{1174}<br />
\end{array}

    Note that: . 1172 \equiv -2 \pmod{1174}

    Then we have:

    \begin{array}{cccccccc} a^{32} & \equiv & (-2)^2 & \equiv & 4 & & & \pmod{1174} \\<br />
a^{64} & \equiv & 4^2 & \equiv & 16 & & & \pmod{1174} \\<br />
a^{128} & \equiv & 16^2 & \equiv & 256  & & & \pmod{1174} \\<br />
a^{256} & \equiv & 256^2 & \equiv & 65,536 & \equiv & 966 & \pmod{1174}\end{array}

    Get the idea?

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing square roots modulo prime powers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 3rd 2011, 07:50 PM
  2. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  3. Modulo
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: November 25th 2009, 06:35 AM
  4. proof of a congruence modulo prime powers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 21st 2009, 03:41 AM
  5. powers modulo p and primitive root question
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 16th 2008, 10:57 AM

Search Tags


/mathhelpforum @mathhelpforum