We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
+2
213
3
avatar+335 

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
avatar+101431 
+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

 

cool cool cool

 Dec 3, 2018
 #2
avatar+335 
+2

Thank you! :)

MathCuber  Dec 3, 2018
 #3
avatar+22363 
+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} \\ {\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}\)

 

laugh

 Dec 3, 2018

5 Online Users