# How to compute large modulos with pen and paper?

I would like to compute $47^{9876543210} \bmod 9$ and $48^{12345678901234567890} \bmod 9$ with pen and paper.

I know this is similar to computing $2^{9876543210} \bmod 9$ and $3^{12345678901234567890} \bmod 9$

I also noticed that 987653210 is divisible by 9 but don't see how it helps.

Any clue on how to do it ?

Thanks

-

In the first case, since $987653210$ is even and a multiple of $3$, it is a multiple of $6$. The usual observation here is that $2^6\equiv 1\,\mod 9$. So, for any $n\in\mathbb Z$, $$2^{6n}=(2^6)^n\equiv 1\,\mod 9.$$

In your second case, $3^2\equiv 0\,\mod 9$, and your exponent there is even. We have $$3^{2n}=9^n\equiv 0\,\mod n$$ for any $n$.

-
I don't see what number is multiple of 3 in the first case. –  BrainOverfl0w Nov 15 '12 at 0:05
You said that $987653210$ is a multiple of $9$. Then it is a multiple of $3$. –  Martin Argerami Nov 15 '12 at 0:06
Oh right ! Thanks –  BrainOverfl0w Nov 15 '12 at 0:09
You are welcome! Sorry for not being clear enough. –  Martin Argerami Nov 15 '12 at 0:11
But $3^5 \equiv 0 \pmod 9$ even though 5 is odd. We just care that the exponent is at least 2. –  Ross Millikan Nov 15 '12 at 0:12

For the first, try the first few powers of $2 \pmod 9$ and you will see a pattern. For the second, any power of $3$ greater than $1$ is a multiple of $9$

-
I notice the pattern for the first one. But I can't prove why it's accurate to predict so. –  BrainOverfl0w Nov 15 '12 at 0:02
@FredericJacobs: the first few lines of Martin Argerami's answer show it. –  Ross Millikan Nov 15 '12 at 0:12

One thing you can do is find power $k$ that you raise $47$ to such that $47^k \mod 9\equiv 1 \mod 9$. Suppose you want to find $47^m \mod 9$. Then we can write $47^m=47^{kq+r}=47^{kq}47^r$, where $q$ is the quotient of $m$ divided by $k$, and $r$ is the remainder. Once you know this, you can apply the multiplication rule for modular arithmetic.

If $a_1\equiv b_1 \mod n$

and $a_2 \equiv b_1 \mod n$

then: $a_1a_2 \equiv b_1$

This implies that $47^{kq}\equiv 1 \mod 9$, and so $47^{m}\mod 9\equiv 47^r\mod 9$. $r$ will be less than $k$ so it will be a simpler problem to solve at this point. I think you can use the discrete log function to find the $k$ needed, but I am not too familiar with that function. For $47$ i tried brute force and $k=6$ should work.

-