Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
add comment

3 Answers 3

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|improve this answer
    
I don't see what number is multiple of 3 in the first case. –  fred 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 –  fred Nov 15 '12 at 0:09
    
You are welcome! Sorry for not being clear enough. –  Martin Argerami Nov 15 '12 at 0:11
1  
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
show 1 more comment

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|improve this answer
    
I notice the pattern for the first one. But I can't prove why it's accurate to predict so. –  fred 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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.