2
$\begingroup$

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

  • 0
    You can use Chinese Remainder Theorem, see [here](http://math.stackexchange.com/questions/95491/n-choose-k-bmod-m-using-chinese-remainder-theorem)2012-07-20
  • 0
    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?2012-07-20
  • 1
    Why is no-one else voting to close this as a duplicate of the question Quixotic linked to?2012-07-20
  • 0
    [Abstract duplicate](http://math.stackexchange.com/questions/172317/) asked by the same user.2012-07-20
  • 0
    well don't worry got it!! thnks so much for your help..2012-07-21

0 Answers 0