+0

# Help Urgent

+2
261
3

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?

Dec 3, 2018

#1
+3

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   Dec 3, 2018
#2
+2

Thank you! :)

MathCuber  Dec 3, 2018
#3
+15

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} \\ a^{\phi (m)}\equiv 1{\pmod {m}},} \\ \text{where \phi } is Euler's totient function. }$$

The modular multiplicative inverse can be found directly:

$$a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}\\ \text{In the special case where m is a prime, \phi (m)=m-1} and a modular inverse is given by } \\ 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}$$ Dec 3, 2018