# Problem on exponents

1. Oct 9, 2012

### sambarbarian

What will be the remainder when 2^256 is divided by 17 ?

I tried expressing 2^256 as 16^64 and seeking a pattern between the remainders of the multiples of 16 when divided by 17 , but that didn't work

2. Oct 9, 2012

### rcgldr

Try converting 17 to base 2, and doing the divide in base 2 to look for a pattern, or convert to base 16 and divide in base 16. You'll need to convert back to decimal once you find a pattern.

3. Oct 9, 2012

no luck

4. Oct 9, 2012

### uart

Some really useful properties of modulo.

1. (a + b) mod q = ( (a mod q) + (b mod q) ) mod q

2. (a b) mod q = ( (a mod q) (b mod q) ) mod q

3. (b^a) mod q = ( (b mod q)^a ) mod q

Note that for the last one you can take the modulo of the base (but not the exponent) before doing the exponentiation, without changing the final result. Use this to break your exponentiation down to a manageable size.

So for example write $2^{256} \mod 17 = (2^{16})^{16} \mod 17$ and apply property (3) above.

5. Oct 9, 2012

### rcgldr

In base 16, you'd be dividing 100000... by 11. The quotient is F0F0F0... . In base 2 you'd be dividing 1000000.... by 10001, the quotient is 1111000011110000... . The remainder at each step also goes through a pattern.

uart's modulo property #3 is also a good method and used in finite field math, but I don't know what you're expected to know at this point in your class.

Last edited: Oct 9, 2012
6. Oct 9, 2012

### sambarbarian

guys , i am in class 10th and i don't know any of these things . This question must have an easy but tricky solution .

7. Oct 9, 2012

### uart

That's ok, just read "modulo q" as "remainder when divided by q" and now it's year 10 level.

2^16 modulo 17 = remainder when 2^16 is divided by 17. You can do that. :)

8. Oct 9, 2012

### rcgldr

The pattern method is similar to what uart is suggesting.

what is

2^8 mod 17
2^16 mod 17
2^24 mod 17
2^32 mod 17
...

9. Oct 10, 2012

### sambarbarian

so i would get , 16^64 mod 17 = ( ( 16 mod 17 )^64 ) mod 17

how do i solve this ?

10. Oct 10, 2012

### rcgldr

Yes, but that doesn't help, since

(16 mod 17) = 16

try

( (16^2) mod 17) ^32) mod 17

you can check this by trying

( (16^4) mod 17) ^16) mod 17

or combining multiple rules:

( ( ((16^3) mod 17) ((16^3) mod 17) ((16^2) mod 17) )^8 ) mod 17

you could also do this with powers of 2, notice a pattern (this is also what you would notice doing long division).

(2^0 mod 17) = 1
(2^1 mod 17) = 2
(2^2 mod 17) = 4
(2^3 mod 17) = 8
(2^4 mod 17) = 16
(2^5 mod 17) = 15
(2^6 mod 17) = 13
(2^7 mod 17) = 9
(2^8 mod 17) = 1
(2^9 mod 17) = 2
...

I'm curious as to what you've been taught in the classroom, that would have helped solve this problem. Anything about remainders or modulo properties?

Last edited: Oct 10, 2012
11. Oct 12, 2012

### sambarbarian

it isnt a classroom problem , i am preparing for a scholarship 9 ( ntse ) and i found it in the sample papers :)

12. Oct 12, 2012

### rcgldr

Then the problem is probably based on how modulo works and the 3 rules posted by uart.