+0  
 
+2
1221
3
avatar+537 

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+128474 
+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+537 
+2

Thank you! :)

MathCuber  Dec 3, 2018
 #3
avatar+26367 
+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

2 Online Users

avatar
avatar