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.

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.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer

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)

share|improve this answer

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

share|improve this answer
    
I'm sorry - I really can't follow what you're saying here with all the implications on one line. Can you break them up maybe by putting the implications one line at a time like I did in my above example? –  agent154 Mar 28 '13 at 14:39
    
@agent154 To master algebraic language, is is essential to learn to read complex inferences like that - just as it is essential learn to read complex sentences in natural language. With practice, one can easily mentally check each inference. If you can't see how to mentally justify some inference, break it out and work on it separately. If you're stuck on one, let me know and I will gladly elaborate. You will learn better if you do this rather than I. –  Math Gems Mar 28 '13 at 15:15

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.