7
$\begingroup$

I know how to determine injectivity and surjectivity for maps between regular sets, but in this case I've got some problems. How can I solve this?

Given the following map $\psi:\overline{x} \in \mathbb{Z}_{16}\mapsto \overline{7}\overline{x}\in\mathbb{Z}_{16}$. Without calculating a single element's image, and just using the properties of $\overline{7}$ in $\mathbb{Z}_{16}$, decide if $\psi$ is injective, surjective or both. If possible, find the inverse of $\psi$.

$\endgroup$
  • 6
    $\begingroup$ $7\times 7=49=3\cdot 16 +1$ so what about $\psi\circ\psi$? $\endgroup$ – Davide Giraudo Feb 13 '12 at 12:43
  • 3
    $\begingroup$ Note also that injectivity and surjectivity are equivalent for functions between finite sets of the same cardinality. $\endgroup$ – lhf Feb 13 '12 at 12:58
  • $\begingroup$ I haven't tried nothing, cause I don't know how to proceed. I was able to do inj. and surj. check calculating every single elements. But in this case I can't do that. @davide: what do you mean? Why $7\times 7$? $\endgroup$ – BAD_SEED Feb 13 '12 at 13:04
  • 2
    $\begingroup$ We have $\bar 7 \cdot\bar 7=\bar 1$. Thanks to that you can say what $\psi\circ\psi$ is. $\endgroup$ – Davide Giraudo Feb 13 '12 at 13:12
  • 1
    $\begingroup$ @J.D., the bar means class mod 16. $\endgroup$ – lhf Feb 13 '12 at 19:41
2
$\begingroup$

You may want to attack the more general question of what you can say about $\psi_a:x\mapsto ax$. Clearly, $\psi_1 = id$ and $\psi_a \circ \psi_b = \psi_{ab}$. In particular, if $ab \equiv 1$ then $\psi_a$ and $\psi_b$ are inverses of each other.

Now, consider whether there is a $b$ such that $7b\equiv 1 \bmod 16$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Since $7$ is relatively prime to $16$, it is a unit in the ring $\mathbb{Z}_{16}$, so $7x=7y$ implies $x=y$. Thus, multiplication by $7$ is injective. Since $\mathbb{Z}_{16}$ is a finite set, multiplication by $7$ is also bijective. The inverse of the map is also multiplication by $7$ since $7$ is its own inverse mod $16$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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