# Find the remainder $4444^{4444}$ when divided by 9 [duplicate]

Find the remainder $4444^{4444}$ when divided by 9

When a number is divisible by 9 the possible remainder are $0, 1, 2,3, 4,5,6,7,8$ we know that $0$ is not a possible answer. My friend told me the answer is $7$ but how

I am thinking of taking 4444 divide by 9 and that left a remainder of 7 so $4444 \cong 7$ mod 9 based on that I am guessing $4444^{4444} \cong 7^{4444}$ mod 9 so to me no matter how big the power is that will still be a remainder of 7 is that correct to think like that

## marked as duplicate by Watson, Dan Rust, Claude Leibovici, Paramanand Singh, John BJun 17 '16 at 14:06

• You're on the right track. Have you learned any shortcuts to computing residues for large powers? (I'm thinking of one that involves expressing the exponent in binary.) – Sammy Black Sep 28 '15 at 21:10
• no unfortunately that is all i know – user146269 Sep 28 '15 at 21:11
• @user146269 Look at $7, 7^2, 7^3, 7^4, \ldots$ mod $9$ and see if you can find a pattern. – Erick Wong Sep 29 '15 at 5:26

Hint: You've got the right idea! Notice now that $7 \cong -2 \pmod 9$ and $(-2)^3 \cong -8 \cong 1 \pmod 9$. Using this can you write $4444$ as a multiple of a certain (useful) number plus a remainder term?

Extra: An example for clarification. What's the remainder on dividing $33^{33}$ by $7$? We have: $$33 \cong 5 \pmod 7$$ so $$33^{33} \cong 5^{33} \pmod 7$$ But now we can notice that $5^3 \cong -1 \cong 6\pmod 7$ and therefore: $$33^{33} \cong 5^{33} \cong 5^{3 \times 11} \cong (5^3)^{11} \cong (-1)^{11} \cong -1 \cong 6\pmod 7$$ So $33^{33}$ has remainder $6$ on division by $7$. Can you try a similar thing with your example?

• Feel free to ask for more hints/clarification if you need it :) – Zestylemonzi Sep 28 '15 at 21:16
• i do not quite follow it is because i know that $4444 \cong 7$ mod 9 that is why i was able to derive that. elaborate more in the hint – user146269 Sep 28 '15 at 21:19
• I'll add a simpler example to my answer. – Zestylemonzi Sep 28 '15 at 21:20
• after i follow your example i have (-2)^1111 mod 9 how do i simplify this – user146269 Sep 28 '15 at 21:47
• Sounds good to me, now notice that $1111 = (3 \times 370) + 1$, so now....? – Zestylemonzi Sep 28 '15 at 21:53

Using the Euler's theorem ( $a^{\phi(m)}\equiv 1 \pmod m$) you can write: $$4444^{4444}\equiv 4444^{6\cdot 740+4}\equiv 4444^4\equiv 7^4\equiv 25\equiv 7\pmod 9$$

• yeah unfortunately i can not use it. A friend of mine was telling me about it. thanks though – user146269 Sep 29 '15 at 16:30
• Please do not skip the step of checking if $a$ is coprime to $9$. – Element118 Jan 6 '16 at 23:03

You are on the right track. You may now want to have a look at modular exponentiation.

• this is not helping me getting anywhere – user146269 Sep 28 '15 at 21:34