# Find the inverse of the equivalence class

I have to check if the equivalence class has an inverse(without calculations). If yes, I have to find it. $$[7] \in \mathbb{Z}_{36}$$ We know that $[a] \in \mathbb{Z}_m$ has an inverse $\Leftrightarrow (a,m)=1$. In this case, knowing that $(7,36)=1$ we conclude that $[7]$ has an inverse. $$\text{So there is a } x \text{ such that } [7][x]=[1] \text{ in } \mathbb{Z}_{36}.$$ But how can I find this $x$? Do I have to check all integers that are in $\mathbb{Z}_{36}$, that means all integers in $\{0,1,...,35\}$?

-

Depends on whether you are supposed to use "general" methods or not. If not, we have $5\cdot 7=35\equiv -1\pmod{36}$, so the equivalence class of $-5$ is the inverse. We could also call it the equivalence class of $31$.

-

A way to find this inverse is to compute $[7^{\phi(36)-1}] = [7^{11}] = [31]$, using Euler's theorem, which states that $[a^{\phi(m)}] = [1]$ in $\mathbb{Z}_m$.

-
Why do you calculate $[7^{\phi(36)-1}] = [7^{11}] = [31]$?? Since Euler's theorem states that $[a^{\phi(m)}] = [1]$ in $\mathbb{Z}_m$ shouldn't it be $[7^{\phi(36)}]$? –  Mary Star Mar 7 '14 at 19:09
Since $[a^{\phi(m)}] = [1]$ we have $[a][a^{\phi(m)-1}]=[1]$, hence $[a^{\phi(m)-1}]$ is the multiplicative inverse of $[a]$. –  user133281 Mar 7 '14 at 19:10

You can use the Extended Euclidean algorithm to compute integers $u, v$ such that $$a \cdot u+ m \cdot v = \gcd(a, m) = 1$$ If follows that $$a \cdot u = 1 \pmod{m}$$ which means that $[u]$ is the inverse to $[a]$ in $\mathbb Z_m$.

-

Hint $\ {\rm mod}\ 36\!:\,\ 7x\equiv 1\,\Rightarrow\, x\,\equiv\, \dfrac{1}7 \,\equiv\, \dfrac{-35}7 \,\equiv\, -5.\,$

Alternatively, more generally, we can lift the obvious solution mod $\,6$ to a solution mod $\,36$ as follows (a special case of Hensel lifting)

${\rm mod}\ 36\!:\ 7x\equiv 1\,\Rightarrow\,{\rm mod}\ 6\!:\ x\equiv 1,\,$ so $\, x = 1\!+\!6j.\$ Hence, substituting this for $\,x\,$

${\rm mod}\ 36\!:\ 1\equiv 7x\equiv 7(1\!+\!6j)\,\Rightarrow\,6(j\!+\!1)\equiv 0\,\Rightarrow\, j= -1\!+\!6k\,\Rightarrow\,x=1\!+\!6j=-5\!+\!36k$.

More generally one can employ the Extended Euclidean Algorithm to compute modular inverses. See this answer for a very convenient and easily memorable way to perform such calculations.

-