2
$\begingroup$

Hello I was wondering if anyone could help better my understanding of finding remainders using congruence and modular arithmetics as I cannot wrap my head around it.

The question I have been presented is to find the remainder when $4444^{4444}$ is divided by 9.

Now I have started by working out $4444$ (mod 9)

$4444\equiv16\equiv-2 \pmod 9$

but for the remaining part I am unsure how to work out.

I have been told through the answers that it should be done by the following:

$4444^{4444} \equiv-2^{4444}\equiv 2^{3*1481+1} \equiv -2 \equiv 7$

I follow the first step as I am aware from a Theorem that;

$a \equiv b \pmod m$ implies $a^{k} \equiv b^{k}\pmod m$ for any integer $k\geq 0$

But I don't understand why we split up the power and how to integer 2 flips between positive and negative.

Thanks in advance for any help

$\endgroup$
2
  • 1
    $\begingroup$ It doesn't "flip". you're missing a negative sign and parenthesis, namely $(-2)^{4444} \equiv (-2)^{3\times 1481 + 1 } \equiv - 2$. Can you figure this out from here? Hint: What is $(-2)^3 \pmod{9}$ $\endgroup$
    – Calvin Lin
    Commented Mar 2, 2021 at 10:13
  • $\begingroup$ Thank you for your comment no wonder I was getting confused with the textbook. I can work out that $-8$ (mod 9) = 1 but I cant figure it out from here. $\endgroup$
    – xyz
    Commented Mar 2, 2021 at 10:20

3 Answers 3

4
$\begingroup$

The point is that $(-2)^3\equiv 1\pmod 9$, and therefore $(-2)^{3k}\equiv1^k=1$ for any natural number $k$. So you can rewrite $(-2)^{4444}$ as $(-2)^1\times(-2)^{3\times 1481}$, and the second factor is $1\pmod 9$.

$\endgroup$
3
  • $\begingroup$ Thank you for your comment and I follow it but how do we deduce that $(-2)^1*(-2)^{3*1481} ≡ -2$ ? Im struggling to work this through in my head. $\endgroup$
    – xyz
    Commented Mar 2, 2021 at 10:25
  • 2
    $\begingroup$ @xyz: That's because the first factor is $-2$ and the second factor is $\bigl((-2)^3\bigr)^1481\equiv 1^{1481}=1$. $\endgroup$
    – Bernard
    Commented Mar 2, 2021 at 10:33
  • $\begingroup$ So the power of 1481 is just the value of k in the previous statement? $\endgroup$
    – xyz
    Commented Mar 2, 2021 at 10:40
2
$\begingroup$

For problems related to remainders it is often convenient and possible to get the remainder as $1$. In this case $4444 \equiv 7\equiv-2\mod{9}$ also $7^3 \equiv 1\mod9$. This means that $4444^3\equiv 1 \mod9$. Using this you split the exponent in a multiple of 3 and a remainder $4444^{4444}=4444^{3\times1481+1}$.

This is common and convenient method to solve this problem.

$\endgroup$
0
$\begingroup$

This is what you showed.

$4444^{4444} \equiv-2^{4444}\equiv 2^{3*1481+1} \equiv -2 \equiv 7$

The reason for $2^3$ is that $2^2 \equiv 8 \equiv -1 \pmod 9$

So \begin{align} 2^{3\times1481+1} \\ &\equiv (2^3)^{1481} \cdot 2^1 \pmod 9\\ &\equiv (-1)^{1481} \cdot 2 \pmod 9\\ &\equiv (-1)\cdot 2 \pmod 9\\ &\equiv -2 \pmod 9\\ &\equiv 7 \pmod 9 \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .