Solving Exponent Remainders: 2^256 Mod 17 Using a Pattern Method

[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

 

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

 

[sambarbarian]

no luck

 

[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 [itex]2^{256} \mod 17 = (2^{16})^{16} \mod 17[/itex] and apply property (3) above.

 

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

 

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

 

[uart]

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

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

 

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

 

[sambarbarian]

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

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

how do i solve this ?

 

[rcgldr]

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

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?

 

[sambarbarian]

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

 

[rcgldr]

it isn't a classroom problem , i am preparing for a scholarship 9 ( ntse ) and i found it in the sample papers.

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