# Modular Arithmetic/Congruence

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

• 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}$ Commented Mar 2, 2021 at 10:13
• 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.
– xyz
Commented Mar 2, 2021 at 10:20

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

• 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.
– xyz
Commented Mar 2, 2021 at 10:25
• @xyz: That's because the first factor is $-2$ and the second factor is $\bigl((-2)^3\bigr)^1481\equiv 1^{1481}=1$. Commented Mar 2, 2021 at 10:33
• So the power of 1481 is just the value of k in the previous statement?
– xyz
Commented Mar 2, 2021 at 10:40

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.

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}