A small question about multiplicative inverses I wan't to find the multiplivative inverse of $[22]^{-1}_{12} $ in $Z_{12}$
But when I do the euclidean algorithm on 22 and 12 I get : gcd(22, 12) = 2
Does that mean there are no multiplicative inverses? I only know how to get the multiplicative inverse if gcd(22, 12) = 1.
Are there any other ways to get the multiplicative inverse of $[22]^{-1}_{12} $ in $Z_{12}$
 A: Suppose that there was a multiplicative inverse of $22$ in $\Bbb Z_{12}$, call it $k$.  Then $22k\equiv 1\pmod{12}$, implying that there exists an integer $n$ such that $22k=1+12n$, but this is an impossibility since the number on the left is even but the number on the right is odd for every integer values of $k$ and $n$
Therefore, $22$ does not have a multiplicative inverse in $\Bbb Z_{12}$.
In general, for $x$ to have a multiplicative inverse in $\Bbb Z_n$ one requires that $\gcd(x,n)=1$
A: Note that $22n$ is an even number for every integer $n$, so there cannot exist $N$ such that $22N = 12k + 1$ for some integer $k$. As you say, this is precisely because $gcd(22,12) = 2 \neq 1$.
If $a$ and $b$ are coprime, then running Euclid gives you $\alpha$ and $\beta$ such that $a\alpha + b\beta = 1$, and thus $a \alpha = 1 - b\beta$ and $b\beta = 1 - a \alpha$, so you have found $\alpha = a^{-1} \mod{b}$  and $\beta = b^{-a} \mod{a}$.
A: Exactly: a number $n$   has a multiplicative inverse  mod $m$,  by definition, if there exists an integer $u$ such that $\;un\equiv 10\mod m$, i.e. if there exists $k\in\mathbf Z$ such that
$$un=1+km\iff un-km=1\iff\gcd(n,m)=1.$$
A: Suppose that $ab \equiv 1 \pmod{n}$.  Then $ab + kn = 1$ which implies $\gcd(a, n) = 1$. Hence if $a$ has a multiplicative inverse then $a$ is relatively prime to $n$.  So there is no multiplicative inverse of $22 \pmod{12}$.
A: If there were a multiplicative inverse to $22$ in $Z_{12}$, then we would have an $x$ such that $22x\equiv 1\pmod{12}$. But then $12$ would divide $22x-1$, meaning $2$ divides $22x-1$, which in turn gives $2$ divides $1$.
So no multiplicative inverse to $22$ in $Z_{12}$ exists.
In general, if $\gcd(a, b)\neq 1$, then there is no multiplicative inverse to $a$ in $Z_b$.
