# Modular Arithmetic Related Question

I've been trying to solve this problem but I couldn't and I don't get the solutions either (I don't think I get how to use modular arithmetic to solve problems in general. And though I tried to understand it by reading articles from Khan Academy and Art of Problem Solving, when it comes to actual application and solving, I can't quite use modular arithmetic - can anyone explain it in a simpler way please?).

The problem goes like this:

For a certain natural number $n$, $n^2$ gives a remainder of $4$ when divided by $5$, and $n^3$ gives a remainder of $2$ when divided by $5$. What remainder does $n$ give when divided by $5$?

How would you solve this using the modular arithmetic - or is there a simpler way/ other way to solve the problem?

The answer is $3$, by the way.

If $n^2\equiv 4\mod5$, then we know $n\equiv2\mod5$ or $n\equiv 3\mod 5$, since \begin{align} n\equiv0\mod5 &\Rightarrow n^2\equiv0\mod5\\ n\equiv1\mod5 &\Rightarrow n^2\equiv1\mod5\\ n\equiv2\mod5 &\Rightarrow n^2\equiv4\mod5\\ n\equiv3\mod5 &\Rightarrow n^2\equiv4\mod5\\ n\equiv4\mod5 &\Rightarrow n^2\equiv1\mod5 \end{align} So $2$ and $3$ are the only options. We know that $n^3\equiv 2\mod5$, and since $2^3\equiv 3\mod5$ and $3^3\equiv 2\mod 5$, we know that $n\equiv 3\mod 5$ is the only leftover option.

In a case simple like this, you can simply compute the remainders of $n$, $n^2$ and $n^3$ modulo 5, for the numbers from 0 to 4 or from 1 to 5.

$$\begin{array}{|c||c|c|c|c|c|}\hline n &0 & 1 & 2 & 3 & 4 \\\hline n^2&0 & 1 & 4 & 4 & 1 \\\hline n^3&0& 1 & 3 & 2 & 4 \\\hline \end{array}$$

From this table the answer is immediate.

Use the following identity $ab\pmod n\equiv (a\pmod n)(b\pmod n)$.

In this case $a=n^2,b=n,n=5$ and we get $$n^3\pmod 5=(n^2\pmod 5)(n\pmod 5)\Rightarrow 2=4\cdot{n\pmod 5)}$$Multiplying both sides by $4^{-1}$ which is $4$ we get $3=n\pmod 5$.

• Oh is there an actual formula like this? Could you explain this in depth or where can I learn about it more? – jjhh Feb 19 '16 at 0:17
• All of the important identities regarding modular arithmetic can be found on wikipedia. Google "modular arithmetic", it should be the first result. – Galc127 Feb 19 '16 at 5:03