I want to write an algorithm to reasonably efficiently calculate $a^L \pmod n$ where $a$ and $n$ are reasonably small (ten digits or so), and $L$ is unreasonably large (billions of digits). I can efficiently calculate $L \pmod m$ for any reasonably small modulus $m$.
Euler's theorem tells us that, when naturals $a$ and $n$ are relatively prime, for any $b$,
$$ a^b \equiv a^{b \text{ mod } \phi(n)} \pmod n$$
where $\phi$ is Euler's totient function. This can also be expressed as $a^{\phi(n)} \equiv 1 \pmod n$.
However, this doesn't apply when $a$ and $n$ have a common factor. For instance, $10^x \equiv 1 \pmod{18}$ only holds when $x = 0$.
I conjecture that, for any naturals $a$ and $b$ and $n$, that $a^b \equiv a^{f(b)} \pmod n$ where
$$f(b) = \left\{\begin{array}{ll} b & \mbox{if } b \le \phi(n) \\ \phi(n) + (b \mbox{ mod } \phi(n)) & \mbox{if } b > \phi(n) \end{array}\right.$$
I've exhaustively tested this for $n \le 1000$. If this is generally true, then I can confidently transform any of my big exponents to a reasonable ($\le 2\phi(n)$) size. Can anyone prove this, point me at an established equivalent theorem, or provide a counterexample?
Let $\phi(n)+(b \pmod \phi(n))=t$
Also let $ \frac{n}{gcd(n, a^t)}=s$
Also let $b=k\phi(n)+r$
If $b> \phi(n)$ then $b \geq t$
Then $a^{b} \equiv a^t \pmod n $ is equivalent to $a^{b-t} \equiv 1 \mod \frac{n}{gcd(n, a^t)}$
So, its enough to prove $a^{b-t} \equiv 1 \mod \frac{n}{gcd(n, a^t)}$
Now, since $gcd(a, \frac{n}{gcd(n, a^t)})=1$ by euler's theorem
we have
$a^{\phi(s)} \equiv 1 \pmod s$.
Clearly $s|n$. So, $\phi(s)| \phi(n)$.
So, let $\phi(n)=g\phi(s)$
Raising both sides to $g$ in $a^{\phi(s)} \equiv 1 \pmod s$ we have
$a^{\phi(n)} \equiv 1 \pmod s$.
Also $b-t=k\phi(n)+r-\phi(n) -(b \mod \phi(n))=(k-1)\phi(n)$
So, now raise both sides of $a^{\phi(n)} \equiv 1 \pmod s$ to $k-1$
to get
$a^{b-t} \equiv 1 \pmod s$ which is what we wanted to show. So, the conjecture is true.