Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?


share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
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$

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.