+0  
 
0
158
1
avatar+737 

When working modulo m, the notation a^-1 is used to denote the residue b for which \(ab\equiv 1\pmod{m},\) if any exists. For how many integers a satisfying \(0 \le a < 100\) is it true that \(a(a-1)^{-1} \equiv 4a^{-1} \pmod{20}?\)

MIRB16  Jun 8, 2018
 #1
avatar+20630 
+1

When working modulo m, the notation a^-1 is used to denote the residue b for which ab\equiv 1\pmod{m}, if any exists.
For how many integers a satisfying  0 \le a < 100 is it true that
a(a-1)^{-1} \equiv 4a^{-1} \pmod{20}?

 

 

\(\begin{array}{|rcll|} \hline a(a-1)^{-1} & \equiv & 4a^{-1} \pmod{20} \qquad | \quad \cdot (a-1) \\ a(a-1)^{-1}(a-1)^1 & \equiv & 4a^{-1}(a-1) \pmod{20} \\ & \quad & | \quad (a-1)^{-1}(a-1)^1 =(a-1)^{-1+1} =(a-1)^{0} = 1 \\ a & \equiv & 4a^{-1}(a-1) \pmod{20} \qquad | \quad \cdot a \\ a^2 & \equiv & 4a^{-1}a^1(a-1) \pmod{20} \\ & \quad & | \quad a^{-1}a^1 = a^{-1+1} = a^{0} = 1 \\ a^2 &\equiv & 4(a-1) \pmod{20} \qquad | \quad - 4(a-1) \\ a^2 - 4(a-1)&\equiv & 4(a-1)- 4(a-1) \pmod{20} \\ a^2 - 4(a-1)&\equiv & 0 \pmod{20} \\ a^2-4a+4 & \equiv & 0 \pmod{20} \\ \mathbf{ (a-2)^2 } & \mathbf{ \equiv } & \mathbf{ 0 \pmod{20} } \\ \hline \end{array}\)

 

\(\text{Therefore, $20$ divides $(a-2)^2$ }\)

 

\(\begin{array}{|rcll|} \hline (a-2)^2 &=& n\cdot 20 \\ a-2 &=& \sqrt{20n} \\ \mathbf{a} & \mathbf{=} & \mathbf{ 2+ \sqrt{20n} } \quad & | \quad \text{if $\sqrt{20n}$ is an integer. $\quad 20 = 2^2\cdot 5$ } \\ \hline \end{array} \)

 

\(\text{so $n$ must complete the $20 (=2^2\cdot 5)$ to a perfect square.} \)

A perfect square has each distinct prime factor occurring an even number of times.

 

\(\begin{array}{|lrcll|} \hline & a &=& 2 + \sqrt{20n} \qquad | \quad 20 = 2^2\cdot 5 \\ & a &=& 2 + \sqrt{2^2\cdot 5\cdot n} \\\\ n=5 & a &=& 2 + \sqrt{2^2\cdot 5\cdot 5} \\ & &=& 2 + \sqrt{2^2\cdot 5^2} \qquad | \quad \text{$2^2\cdot 5^2$ has each distinct prime factor$\\$occurring an even number of times } \\ & &=& 2 + 2\cdot 5 \\ & \mathbf{a} & \mathbf{=} & \mathbf{12}\checkmark \qquad | \quad 0 \le a < 100 \\\\ n=2^25 & a &=& 2 + \sqrt{2^2\cdot 5\cdot 2^2\cdot 5} \\ & &=& 2 + \sqrt{2^4\cdot 5^2} \qquad | \quad \text{$2^4\cdot 5^2$ has each distinct prime factor$\\$occurring an even number of times } \\ & &=& 2 + 2^2\cdot 5 \\ & \mathbf{a} & \mathbf{=} & \mathbf{22}\checkmark \qquad | \quad 0 \le a < 100 \\\\ n=5^3 & a &=& 2 + \sqrt{2^2\cdot 5\cdot 5^3} \\ & &=& 2 + \sqrt{2^2\cdot 5^4} \qquad | \quad \text{$2^2\cdot 5^4$ has each distinct prime factor$\\$occurring an even number of times } \\ & &=& 2 + 2\cdot 5^2 \\ & \mathbf{a} & \mathbf{=} & \mathbf{52}\checkmark \qquad | \quad 0 \le a < 100 \\\\ n=2^25^3 & a &=& 2 + \sqrt{2^2\cdot 5\cdot 2^2 \cdot 5^3} \\ & &=& 2 + \sqrt{2^4\cdot 5^4} \qquad | \quad \text{$2^4\cdot 5^4$ has each distinct prime factor$\\$occurring an even number of times } \\ & &=& 2 + 2^2\cdot 5^2 \\ & \mathbf{a} & \mathbf{=} & \mathbf{102} \text{ no } \qquad | \quad 0 \le a < 100 \\ \hline \end{array}\)

 

\(\mathbf{a = 12, 22, \text{ and } 52}\)


\(\text{But technically, $a^{-1}$ and $(a-1)^{-1}$ have to exist $\mod {20}$, $\\$which means both $a$ and $a-1$ are coprime to $20$.} \)
Which is impossible as either one of them has to be even.

 

laugh

heureka  Jun 8, 2018

5 Online Users

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.