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$.
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$
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.
