What is $2^{7!}\bmod{2987}$ Find the remainder when $2^{7!}$ is divided by $2987$.
I tried to factorise $2987$ to make it simple but it was in vain.
 A: Hint: The unique prime factorization of $2987$ is,
$$2987=29\times 103$$
Now, use Fermat's Little Theorem to reduce the exponent and get the remainder modulo $29$ and $103$.
Combine the results using Chinese Remainder Theorem.

Alternatively, you can use Euler's totient function to compute $\phi(2987)$ and then use Euler's Totient theorem but that might result in tedious calculations and we being lazy never want to do it the tedious way. :P
A: $2^{\large 7!}\!\pmod{\color{brown}{29}87}\,$ can be computed using only simple mental arithmetic.
Note that  $\ \color{brown}{29}\!\mid\! 87,\,$ i.e. $\, 29\cdot 3 = 87\ $ so $\ 2987 = 29(100\!+\!3) = 29\cdot 103$
Since $\, p = 29,103\,$ are prime, we can use little Fermat to reduce exponents, i.e.
$(1)\qquad\qquad\ \ N \equiv n\pmod{p\!-\!1}\ \Rightarrow\ 2^{N}\!\equiv 2^{n}\pmod p$
${\rm mod}\,\ \ 28\!:\ 7! \equiv 0\ $ by $\ 7,4\mid 7!\,\Rightarrow\, 28=7\cdot 4\mid 7!$ 
${\rm mod}\ 102\!:\, 7! \equiv (7\cdot 5\cdot 3)(6\cdot 4\cdot 2)\equiv 105(14\!+\!34)\equiv 3(14) \equiv 42,\, $ so,  $ $ applying $(1)$
${\rm mod}\ 29\!:\ \ \ x\equiv  2^{\large 7!}\equiv 2^{0}\equiv\color{#c00} 1$
${\rm mod}\ 103\!:\ x\equiv 2^{\large 7!}\equiv 2^{42}.\ $  Let's compute this power: 
$\qquad\ 2^{10}=1024\equiv 1030\!-\!6\equiv -6,\,$ so $\,2^{11}\equiv -12\,$ so $\,2^{21}\equiv (-6)(-12) \equiv 72\equiv -31$  
$\ \Rightarrow\  2^{42} \equiv (2^{21})^2\equiv (-31)^2\equiv (1\!+\!30)^2 \equiv 1 + 2(30)+9(-3)\equiv \color{blue}{34}$
Finally we apply $ $ CRT = Chinese Remainder Theorem:
${\rm mod}\ 29\!:\ \color{#c00}1\equiv x\equiv \color{blue}{34}\!+\!103j\equiv 5\!+\!16j\!\iff\! 16j\equiv -4\!\iff\! 4j\equiv -1\equiv 28\!\iff\! j\equiv\color{#0a0} 7$
So we deduce $\ x = 34\! +\! 103(\color{#0a0}7\!+\!29k)\, =\, 755 + 2987k$
A: Here is a solution that does not make use of Fermat's Little Theorem.

The Algorithm:


*

*Input: $x=2,e=7!,n=2987$

*Output: $y=1$

*Repeat until $e=0$:


*

*If $e\equiv1\pmod2$ then set $y=yx\bmod{n}$

*Set $x=x^2\bmod{n}$

*Set $e=\left\lfloor\frac{e}{2}\right\rfloor$
C Implementation:
int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

int result = PowMod(2,5040,2987); // 755

Intermediate Output:
   x   |   e   |   y
-------|-------|-------
     2 |  5040 |     1
     4 |  2520 |     1
    16 |  1260 |     1
   256 |   630 |     1
  2809 |   315 |     1
  1814 |   157 |  2809
  1909 |    78 |  2691
   141 |    39 |  2691
  1959 |    19 |    82
  2373 |     9 |  2327
   634 |     4 |  1995
  1698 |     2 |  1995
   749 |     1 |  1995
  2432 |     0 |   755


Please note that the complexity is $O(\log_2e)$, resulting in $\lceil\log_27!\rceil=13$ iterations.
A: Computational answer=755 (Cloud Sage)
Edit: 7! not 71. Sorry
