+0

# When working modulo m,

0
235
1
+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}?$$

Jun 8, 2018

#1
+21340
+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.

Jun 8, 2018