+753 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}?\)
+26393 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.
