How to find the inverse of a function $f:\mathbb{Z}_{30}\to\mathbb{Z}_{30}$ defined by $f([a])=[7a]$

Question

If $f:\mathbb{Z}_{30}\to\mathbb{Z}_{30}$ is a function defined by $f([a])=[7a]$, show that $f$ is one-to-one and onto, and find $f^{-1}$.

I've got proof that the function is well defined, one to one, and onto. I can't seem to understand these notes I have though that shows its inverse. Maybe I took them down wrong, or missed some details?

\begin{align*} f^{-1}([b])=[a]&\iff f([a])=[b]\\ &\iff [7a]=[b]\\ &\iff 7a\equiv b\ (mod\ 30)\\ gcd(30,7)=1&\iff \exists r,s\in\mathbb{Z} \ni 30r+7s=1\\ &\iff 13\times 7-3\times 30=1\\ &\iff \end{align*}

And then there, I have something that jumps to the conclusion that $a=13b$, $[a]=[13b]$, $f^{-1}([b])=[13b]$

But I have no idea how my prof got $a=13b$ in the first place... not from looking at my notes anyhow.

Answer 1

The Euclidean algorithm (see also Bézout) is your friend here. It is used to write $1 = \gcd(30, 7)$ as a linear combination of $30$ and $7$: $$ 1 = 13 \cdot 7 - 3 \cdot 30.\tag{comb} $$ Then the function $g([a]) = [13 a]$ is the inverse of $f$, as $$ g(f(a)) = [13 \cdot 7 \cdot a] = [13 \cdot 7] [a] = [a], $$ as $13 \cdot 7 \equiv 1 \pmod{3}$ from (comb).

Answer 2

They solved the equation $7a \equiv b$ by multiplying through by the inverse of $7$. The inverse of $7$ is the number $x$ so that $7x \equiv 1$, so you should be able to see why that strategy works. As to why $13$ is the inverse of $7$, that's easy to see from the extended gcd calculation they did when you consider it modulo $30$. (in fact, that's why they did the extended gcd calculation)

Answer 3

$\rm mod\ 30\!:\,\ 7x\equiv 1 \Rightarrow 7x\!+\!30y=1\Rightarrow mod\ 7\!:\ 2y\equiv 1\:\Rightarrow\: y\equiv \frac{1}2\equiv \frac{-6}2\equiv -3,\:$ so $\rm\:y = -3\! +\! 7n.\: $ Back-substituting: $\rm\ x = (1\!-\!30y)/7 = (1\!-\!30(-3\!+\!7n))/7 = 13-30n,\ $ by $\rm\ 91/7 = 13$.

Remark $\ $ The method used is a special case of the Extended Euclidean GCD Algorithm, which would be a bit overkill to use for such a simple case (small numbers).