# powers modulo m help needed

• Jun 5th 2008, 07:32 AM
duggaboy
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..
• Jun 5th 2008, 08:04 AM
topsquark
Quote:

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

$\displaystyle a^8 \equiv (a^4)^2 \equiv 1011^2 \text{ mod(1147)}$

$\displaystyle \equiv 1022121 - 891 \cdot 1147 \equiv 144$

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

-Dan
• Jun 5th 2008, 08:28 AM
duggaboy
awesome thank you
• Jun 5th 2008, 08:49 AM
Soroban
Hello, duggaboy!

Use the "reduced" forms . . .

Quote:

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

$\displaystyle \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: .$\displaystyle 1172 \equiv -2 \pmod{1174}$

Then we have:

$\displaystyle \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?