0
$\begingroup$

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

  • 0
    http://en.wikipedia.org/wiki/Fermat's_little_theorem2012-11-14

3 Answers 3

4

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

  • 0
    Yeah, any power of$3$greater than will make the remainder 0.2012-11-15
2

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$

  • 0
    @FredericJacobs: the first few lines of Martin Argerami's answer show it.2012-11-15
1

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.