Modular Arithmetic

Printable View

March 10th 2011, 07:22 PM
pawnag3

Modular Arithmetic

Hi,
I'm not too confident about some mod simplification.
I am wondering if anyone can help me simplify this:
2^(28) (mod 37)
Basically, I don't know how to get it to become a 2^x = 1 or -1 (mod 37)
Here's my attempt
1) (2^2) (3^2) = -1 (mod 37)
Therefore...
Well, let's face it, I have no idea where to go from there.

Thanks for any help
P.S.: Please forgive me, I'm having some trouble with LaTex right now :(
March 11th 2011, 04:19 AM
tonio

Quote:

Originally Posted by pawnag3

Hi,
I'm not too confident about some mod simplification.
I am wondering if anyone can help me simplify this:
2^(28) (mod 37)
Basically, I don't know how to get it to become a 2^x = 1 or -1 (mod 37)
Here's my attempt
1) (2^2) (3^2) = -1 (mod 37)
Therefore...
Well, let's face it, I have no idea where to go from there.

Thanks for any help
P.S.: Please forgive me, I'm having some trouble with LaTex right now :(

$2^{28}=(2^7)^4=17^4=12\!\!\pmod {37}$

Tonio
March 11th 2011, 11:27 AM
Capillarian

There's another way to do it, using intuitive ideas and only 6 operations. Start with 2; you know of course that 2 = 2 (mod 37). Successively square this until you have 2^16:

$2^1\equiv 2 \text{ (mod 37)}, \qquad 2^2\equiv 4 \text{ (mod 37)}, \qquad 2^4\equiv 16 \text{ (mod 37)},$
$2^8\equiv 256 \equiv -3 \text{ (mod 37)},\qquad 2^{16}\equiv 9 \text{ (mod 37)}.$

Now you notice that 28 = 16 + 8 + 4. So you calculate the product:

$2^{28} \equiv 2^{16+8+4} \equiv 9 \times -3\times 16 \equiv 12\text{ (mod 37)}.$

Tonio's method is essentially the same but uses 9 operations.