Find the last four digits of $2^{27653 }- 1$

Question

Find the last four digits of $2^{ 27653} - 1. This is one of the questions in a mathematics contest. I have tried to find the sequence but I found it impossible. (I have used excel to do this and the sequence repeat after 2 ^ 15XX - 1)

Answer 1

Using sage we get instantly

sage: R = Zmod(10000)
sage: R(2)^27653 - 1
2991

Using pari/gp also ...

? Mod(2,10000)^27653 - 1
%11 = Mod(2991, 10000)

The human solution would be to compute the result modulo $2^4$ and modulo $5^4$. Of course, the number $$N=2^{27653}$$ is congruent to $0$ modulo $2^4$. Let us compute it modulo $5^4$. The Euler indicator of this number is $\phi(5^4)=5^4\left(1-\frac 15\right)=4\cdot 5^3=500$. So $$N=2^{27653}\equiv 2^{27653\mod 500}=2^{153}\mod 5^4\ .$$ Now we can compute $2^{153}$ explicitly, it is $11417981541647679048466287755595961091061972992$, or write it like $(2^{51})^3$ and compute the third power of $(2^{51}\mod 5^4)=(2251799813685248\mod 5^4)=(5248\mod 5^4)=(248\mod 5^4)$. In each case we get the wanted $492$. Now we search among the numbers $492+5^4k$ with $0\le k< 2^4$ the one which fulfills the condition modulo $2^4$. The number divisible by $16$ among them is $2992$. We get the same answer as a human ...