# Math Help - powers modulo m help needed

1. ## 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..

2. Originally Posted by duggaboy
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

3. awesome thank you

4. Hello, duggaboy!

Use the "reduced" forms . . .

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

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

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

Then we have:

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

Get the idea?