×

# Chef and Pattern

 0 hey guys , Can you please help me in proving that (k^(2^n))%MOD is equailvalent to (k^((2^n)%(MOD-1))%MOD? Thanks, asked 22 Jan '15, 11:41 2★johri21 446●1●3●7 accept rate: 12%

 1 It comes from Fermat's Little theorem... check this thread for proof : click here answered 22 Jan '15, 12:22 337●4●5●14 accept rate: 0%
 0 I tried the following, a = (2^n-3)%MOD [ n<=2 taken care manually] ans = (k^a)%MOD; But it gives WA.. Why is that?? answered 22 Jan '15, 14:43 3●1 accept rate: 0% If you look in closely a was infact at max 2^(1e9) so that large a value will not be taken care by any language(a will overflow, so you have to mod a then k^a%MOD) , so you had to use the formuale mentioned above in my post. (22 Jan '15, 18:28) johri212★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×333
×15

question asked: 22 Jan '15, 11:41

question was seen: 1,285 times

last updated: 22 Jan '15, 18:28