+0  
 
+2
90
3
avatar+260 

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+94545 
+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+260 
+2

Thank you! :)

MathCuber  Dec 3, 2018
 #3
avatar+20838 
+10

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

12 Online Users

avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.