Last $n$ digits of $a^b$

Last year I came acoss the following problem in a mathematics competition

What are the last $2$ digits of $2012^{2012}$? $\ \ \ \ \ $(Ans: 56)

I found the last two digits using the standard technique involving some modular arithmetic.

Another student came up with a very clever technique that did not rely on modular arithmetic but rather on logarithms and the floor function (scientific calculators were allowed, but no graphing calculators or computer algebra systems). I've forgotten the details of this technique, which was really just a function that could be written in a single line, but remember that it easily generalized to give the last $n$ digits of any number of the form $a^b$ without causing overflow errors on little scientific calculators, even with sizable $a$ and $b$.

I've searched stackexchange and the web for information on this technique but found nothing. I spent a fair amount of time thinking about the problem but not made any progress. Has anyone seen such a technique? If so, please help me reproduce the function he used.

I am specifically interested in the technique described above; without any modular arithmetic, Chinese Remainder Theorem, Euler's Generalization, Repeated Squaring, etc.

Let's start with some modular arithmetic. I know you don't want an answer explicitly using any modular trickery, but often an answer can hide the means used to get it.

The goal is to calculate $a^b\bmod 10^n$, which as you have pointed out is equal to $a^b-10^n\left\lfloor a^b10^{-n}\right\rfloor$, although that formula is plainly useless if $a$ or especially $b$ are even moderately large. The identity $x\bmod y=x-y\lfloor x/y\rfloor$ will come in handy though. Let $m=10^n$ be the base for the mod operation.

The way we can proceed is by reducing $a$ and $b$ as much as possible, using modular arithmetic. The easy one is $a$: since modular arithmetic preserves products, $a^b\equiv (a\bmod m)^b$. Thus, we need only consider $a\le m$.

The most useful formula in this context is Euler's theorem $a^{\phi(m)}\equiv 1\pmod m$, where $\phi(m)$ is the totient function. In general, $\phi(m)$ is quite difficult to compute, but by a stroke of luck we happen to know $m=10^n$, so we know the prime factorization, and by the formula

$$\phi(m)=\phi(p_1^{e_1}\dots p_n^{e_n})=m\left(1-\frac1p_1\right)\dots\left(1-\frac1p_n\right),$$

we find that $\phi(10^n)=10^n(1-1/2)(1-1/5)=4\cdot 10^{n-1}$.

Unfortunately, Euler's theorem comes with the caveat that $a$ and $m$ must be coprime, so it doesn't work in full generality like you want. An even stronger result is Carmichael's theorem, which is just the same as Euler's, but with a smaller function in the exponent: $a^{\lambda(m)}\equiv 1\pmod m$, where $\lambda(10^n)=2\cdot 10^{n-1}$. Furthermore, $a^{\lambda(m)+b}\equiv a^b\pmod m$ for any integer $a<m$ and any $b\ge k$, where $k$ is the largest exponent in the prime factorization of $a$. Now we want a general formula that doesn't need any factorization, so let's upper-bound $k$. The worst-case scenario is if $a$ is a high power of $2$ less than $10^n$. In this case, $a=2^k<2^{n\log_2 10}=10^n$, so $k<n\log_2 10$. (Note that $n\log_2 10$ is not an integer, but with our floor trick for calculating $\bmod$ this won't be a problem. It is just as well to use $\lfloor n\log_2 10\rfloor$ instead.)

We're ready to put it all together now. We have $a^b\bmod m=c^d\bmod m$ as long as $a\bmod m=c\bmod m$ and $b\bmod\lambda(m)=d\bmod\lambda(m)$ and $b,d\ge n\log_2 10$. (I'm assuming $a$ and $b$ are "large", and we are trying to reduce them to reasonable proportions. If $b<n\log_2 10$, then just plug the damn thing into your calculator.) Thus, the optimal choices that satisfy the criteria are $$c=a\bmod 10^n=a-10^n\left\lfloor a10^{-n}\right\rfloor,\quad\rm and$$ $$\begin{align} d&=((b-n\log_2 10)\bmod2\cdot 10^{n-1})+n\log_2 10 \\ &=b-2\cdot 10^{n-1}\left\lfloor\frac{b-n\log_2 10}{2\cdot 10^{n-1}}\right\rfloor, \end{align}$$

and we finish by plugging those into $a^b\bmod 10^n=c^d-\left\lfloor c^d10^{-n}\right\rfloor$.

For the case in the OP, $a=b=2012$, and $n=2$. Then $c=12$, $\phi(10^n)=40$, $\lambda(10^n)=20$, $n\log_2 10=6.64\dots$, $\lfloor n\log_2 10\rfloor=6$, and $d=12$, so $$2012^{2012}\bmod 100=12^{12}\bmod 100=8916100448256\bmod 100=56.$$

The numbers are still somewhat large, but certainly within the realm of scientific calculators. The problem becomes of course much more tractable if you split the exponent in half. This is step one of exponentiation by repeated squaring (but I claim to be avoiding the restriction on the OP, since I'm not advocating the whole iterative process ;) ). Better yet, we can divide the exponent into $q$ equal pieces (more on choosing $q$ in a bit). The way it goes is (after having reduced $a$ and $b$ to $c$ and $d$ as above) to calculate $c^{qr+s}\bmod m=(c^r\bmod m)^qc^s\bmod m$, where $d=qr+s$ is the quotient and remainder of $d$ on division by $q$, i.e. $r=\lfloor d/q\rfloor$ and $s=d\bmod q$. Now our final result is

$$a^b\bmod 10^n=(c^{\lfloor d/q\rfloor}\bmod 10^n)^qc^{d\:\bmod\:q}\bmod 10^n,$$ where as before $x\bmod y$ is shorthand for $x-y\lfloor x/y\rfloor$. Using this formula instead, with the original numbers, and choosing $q=3$, we get $$\begin{align} a^b\bmod 10^n&=(12^4\bmod 100)^312^0\bmod 100\\ &=(20736\bmod 100)^312^0\bmod 100=46656\bmod 100=56,\end{align}$$ which is well within the range of an 8-digit pocket calculator.

But where does $q$ come from? The two big numbers in our calculation are $c^{\lfloor d/q\rfloor}=20736=h$ and $(h\bmod 100)^{d\:\bmod\:q}=46656$. The bigger $q$ is, the smaller the first number is and the larger the second is. On a rough heuristic, both $c$ and $h\bmod 100$ are large numbers mod $100$, so they should be approximately 50, if I pretend the numbers are uniformly distributed. (Don't read too much into this estimate.) Thus a good choice of $q$ would approximately equalize the exponents, i.e. $q=\lfloor\sqrt d\rfloor$ (which is equal to $3$ in our example).

Are you sure the problem asked about the last few digits? If it was first few digits, the one-line solution using logarithms would sounds a lot more likely: $$g(a,b,n)=\left\lfloor 10^{b\log_{10}a - \lfloor b\log_{10}a\rfloor + 1 + n} \right\rfloor$$

Of course, this is just a disguised version of $\left\lfloor \frac{a^b}{10^{k-n}}\right\rfloor$, where $k$ is the number of digits of $a^b$.