23*d = 1mod66
Because gcd(23,66) = 1 we can calculate the modulo inverse:
\(\begin{array}{rcl} 23\cdot d & \equiv& 1 \pmod {66} \\ d & \equiv& \frac{1}{23} \pmod {66} \\ d & \equiv& 23^{-1} \pmod {66} \\ \end{array}\)
We use the Extended Euclidean Algorithm to get d:
\(\begin{array}{|rcl|r|c|rc|} \hline 66 &=& 23\cdot 2+20 & or &(4) & [66 - 23\cdot 2] &=& 20\\ 23 &=& 20\cdot 1 + 3 & or &(3) & [23-20] &=& 3\\ 20 &=& 3\cdot 6 + 2 & or &(2) & [20-18] &=& 2\\ 3 & =& 2\cdot 1 + 1 & or & (1) & [3-2 ] &=& 1\\ \hline \end{array}\\\\ \begin{array}{lrcl} (1) & 3-2 &=&1 \qquad | \qquad (2) \quad 2 = [20-18]\\ & 3-[20-18] &=&1 \\ & 3 - 20 + 18 &=&1 \\ & 3 (1+6) -20 &=&1\\ & 3 \cdot 7 -20 &=&1 \qquad | \qquad (3) \quad 3 = [23-20] \\ & [23-20] \cdot 7 -20 &=&1 \\ & 23 \cdot 7 - 20 \cdot 7 - 20 &=& 1 \\ & 23 \cdot 7 -20\cdot 8 &=& 1 \qquad | \qquad (4) \quad 20 = [66 - 23\cdot 2] \\ & 23 \cdot 7 - [66 - 23\cdot 2] \cdot 8 &=& 1 \\ & 23 \cdot 7 - 66 \cdot 8 + 23 \cdot 16 &=& 1 \\ & 23 \cdot 23 - 66 \cdot 8 &=& 1 \qquad | \qquad \pmod {66}\\ & 23\cdot 23 &\equiv& 1 \pmod{66} \\ \hline & 23^{-1} \pmod{66} &\equiv& 23 \\ & 23\cdot d &\equiv& 1 \pmod{66} \\ & d &= & 23 \end{array}\)
All Solutions: \(d \equiv 23 \pmod {66} \\ \qquad \text{or} \\ d - 23 = n\cdot 66 \\ \mathbf{ d = 23 \pm n \cdot 66 \qquad n \in N }\)
