# Help with Functions in Discrete Mathematics

I am having trouble solving this problem:

let $p$ be a positive prime number and let $f:Z_p -> Z_p$ be defined as $f([x])=[x^2]$. Show that $f$ is a function. Give examples of how it is not necessarily injective or surjective.

Work: I know that for a relation to be a function, it has to meet two criteria. However, I have trouble proving that for every $x$ there exists a $y$ such that $f(x)=y$. Putting integer modulo makes this question even harder and I do not know where to start.

Thanks

## 1 Answer

What you're supposed to show here is that $f$ is well-defined. Very often, it's pretty obvious whether a function definition fullfills that - if, from example, it's a valid combination of other well-defined functions, it's automatically well-defined.

But if you're dealing with residue classes, things are often not so obvious. In your case, you're dealing with the field $\mathbb{Z}_p = \mathbb{Z} / I$ where $I = p\mathbb{Z}$ of residue classes, i.e. $$\mathbb{Z}_p = \{[x] \,:\, x \in \mathbb{Z}\} \text{ where } [x] = \{y \in \mathbb{Z} \,:\, x -y \mid p\} \text{.}$$ Note that different $x \in \mathbb{Z}$ create the same residue class $[x]$ - as they must, since you know that $\mathbb{Z}_p$ contains only $p$ elements, where as $\mathbb{Z}$ contains countably many. In the expression $[x]$, $x$ is called a representative of the residue class - but that representative, per the previous sentence, is not unique. Thus, if you define a function on a set of residue classes in terms of representatives, you're at risk of producing a non-well-defined functions. Say for example, you define $$f\,:\, \mathbb{Z}_2 \to \mathbb{Z} \,:\, [x] \to x \text{ .}$$ Now, $0$ and $2$ are members of the same residue class in $\mathbb{Z}_2$, i.e. $[0] = [2]$. In other words, there aren't to distinct elements $[0]$ and $[2]$ in $\mathbb{Z}_2$, there's only one element $[0] = [2]$ with two different names. But your definition attempts to map $[0]$ to $0$ and $[2]$ to $2$, which comes down to mapping one element to two different values.

Thus, for functions defined on sets of residue classes, if the function is defined in terms of representatives, you need to show that the result of the function is independent from the particular choice of representative. For example, $$f\,:\, \mathbb{Z}_2 \to \mathbb{Z} \,:\, [x] \to \begin{cases} 1 &\text{if x is even} \\ -1 &\text{if x is odd.} \end{cases}$$ is fine, because you can easily prove that if $x,y$ are two representatives of the same residue class, then either both are even or both are odd, so it doesn't matter which one you pick to compute $f$.

• Hi, thank you so much for your reply. I know the danger of non well-defined functions, but I am still confused. Sorry, I just started learning both integer modulo and functions in my class, so all of this is really new to me. – mrQWERTY Apr 2 '14 at 21:19
• So I found another way to do it I think. Basically, to show that it is well-defined, I need to show that if $[a] \equiv [b]$, then $f([a]) \equiv f([b])$. So through this, I showed that if $p|a-b$ then $a-b=pk$ and then $a^2-b^2=(a-b)(a+b)=pk(a+b)=p(ka+kb)$. Since $ka+kb$ is an integer, then $p|a^2-b^2$ which means $a^2\equiv b^2$ thus $a^2=b^2$. I don't know if this is right, but this is how my textbook approached a similar problem. – mrQWERTY Apr 2 '14 at 21:32
• @Froggy Sounds fine. – fgp Apr 2 '14 at 22:12
• @Froggy But this is exactly what I suggest you do, no? Show that the value $f([x])$ depends only on the residue class, not on the representative. Which you have done nicely, btw. – fgp Apr 2 '14 at 23:05
• Thank you! Now I know how to do these types of problems :) – mrQWERTY Apr 2 '14 at 23:40