Take the 2-minute tour ×

I am trying to solve the following problem.
I need to find the value of
$$ a^{(b^x)} \bmod m $$ where $a,b$ are integers and
$$ x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 $$ the value of $n$ can be upto $10^5$
and $m = 1000000007$ which is a prime
Also note that its $a^{b^x}$ which is not equal to $a^{bx}$
Also by solving $c$ it comes out to be $\pmatrix{2n\\n}$
also $\pmatrix{2n\\n}$ satisfies the relation $$ a_n = a_{n-1} (4n-2)/n $$ where $a_0 = 1$
I have reached the fact that $a^{b^c} \bmod m$ is equivalent to
$$ a^{b^d \bmod \phi(m)} \bmod m $$ where $d=c \bmod \phi(\phi(m))$

but i am unable to calculate the value of $c$ as it involves a denominator term and modulo inverse is not possible since $\phi(\phi(m)) = 500000002$ is not a prime.
Can anyone suggest me any approach or any possible thing that I missed.

share|improve this question
You can use Chinese Remainder Theorem, see here –  Quixotic Jul 20 '12 at 15:55
It looks like you're going back and forth between $x$ and $c$ -- all occurrences of those two letters are meant to be the same variable, right? –  joriki Jul 20 '12 at 16:14
Why is no-one else voting to close this as a duplicate of the question Quixotic linked to? –  joriki Jul 20 '12 at 18:23
Abstract duplicate asked by the same user. –  Quixotic Jul 20 '12 at 21:17
well don't worry got it!! thnks so much for your help.. –  user1489938 Jul 21 '12 at 10:30
add comment


Your Answer



Browse other questions tagged or ask your own question.