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?
Others on here can probably do this in a more elegant manner, MC, but.....here's my clumsy attempt
n^2 = 5p + 4
n^3 = 5q + 2
Subtract the first equation from the second and rearrange as
5 (q - p) = [ n^3 - n^2 + 2 ]
q - p = [ n^3 - n^2 + 2] / 5
Note that the right side must be divisible by 5
So....the first "n" I find that works is n = 3
So....... 20/ 5 = 4 and q - p = 4
So
3^2 = 5(1) + 4
3^3 = 5(5) + 2
So..... n / 5 = 3 / 5 = 3 mod 5 = 3 = Remainder
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?
\(\begin{array}{|lrcll|} \hline (1) & n^2 & \equiv & 4 \pmod{5} \\ (2) & n^3 & \equiv & 2 \pmod{5} \\ \\ \hline \\ \dfrac{(2)}{(1)}: & \dfrac{n^3}{n^2} & \equiv & \dfrac{2}{4} \pmod{5} \\\\ &n & \equiv & \dfrac{1}{2} \pmod{5} \\\\ &\mathbf{n} & \mathbf{\equiv} & \mathbf{2^{-1} \pmod{5}} \\ \hline \end{array} \)
Modular multiplicative inverse by Euler:
\(\text{According to Euler's theorem, if $a$ is coprime to $m$, that is, $gcd(a, m) = 1$, then} \\ {\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},} \\ \text{where ${\displaystyle \phi }$ is Euler's totient function. } \)
The modular multiplicative inverse can be found directly:
\({\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}\\ \text{In the special case where $m$ is a prime, ${\displaystyle \phi (m)=m-1}$ and a modular inverse is given by } \\ {\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}.}\)
\(\text{So $2$ is coprime to $5$ }: \)
\(\begin{array}{|rcll|} \hline 2^{-1} & \equiv & 2^{5-2} \pmod{5} \\ & \equiv & 2^{3} \pmod{5} \\ & \equiv & 8 \pmod{5} \\ & \equiv & 8-5 \pmod{5} \\ & \equiv & 3 \pmod{5} \\ \hline \end{array}\)
\( \begin{array}{|rcll|} \hline &\mathbf{n} & \mathbf{\equiv} & \mathbf{2^{-1} \pmod{5}} \\ &\mathbf{n} & \mathbf{\equiv} & \mathbf{3 \pmod{5}} \\ \hline \end{array}\)