Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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\}$?

share|improve this question

4 Answers 4

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$.

share|improve this answer

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$.

share|improve this answer
    
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 at 19:09
4  
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 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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.