1
$\begingroup$

This question already has an answer here:

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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.) $\endgroup$ – Sammy Black Sep 28 '15 at 21:10
  • $\begingroup$ no unfortunately that is all i know $\endgroup$ – user146269 Sep 28 '15 at 21:11
  • $\begingroup$ @user146269 Look at $7, 7^2, 7^3, 7^4, \ldots$ mod $9$ and see if you can find a pattern. $\endgroup$ – Erick Wong Sep 29 '15 at 5:26
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Feel free to ask for more hints/clarification if you need it :) $\endgroup$ – Zestylemonzi Sep 28 '15 at 21:16
  • $\begingroup$ 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 $\endgroup$ – user146269 Sep 28 '15 at 21:19
  • $\begingroup$ I'll add a simpler example to my answer. $\endgroup$ – Zestylemonzi Sep 28 '15 at 21:20
  • $\begingroup$ after i follow your example i have (-2)^1111 mod 9 how do i simplify this $\endgroup$ – user146269 Sep 28 '15 at 21:47
  • $\begingroup$ Sounds good to me, now notice that $1111 = (3 \times 370) + 1$, so now....? $\endgroup$ – Zestylemonzi Sep 28 '15 at 21:53
1
$\begingroup$

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

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

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

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

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