0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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