Input and Output of function using Congruence Classes modulo n. Show neither surjective nor injective.

Question

Recall that we define

$$Z_n = \{[0], [1], . . . , [n − 1]\}$$

to be the set of congruence classes modulo n. Also define the function

$f_n : Z_n → Z_n, f(x) = x^2$

For example, $Z_{11} = \{[0], [1], [2], . . . , [10]\}$,

and $f_{11}([5]) = [3]$, since $5^2 = 25 \equiv 3 \pmod{11}$.

(a) Create a table showing all input-output pairs for the function $f_{11} : Z_{11} → Z_{11}.$

(b) Show that $f_{11}$ is neither surjective nor injective.

(c) Show that $f_n$ is never injective for integer n ≥ 3. (Hint: Consider what happens to the congruence classes [1] and [n − 1].)

For (a) I don't really know how to go about listing the input-output pairs as I am a bit confused on what each input would be and what its corresponding output would be as well. Would we have to find all congruences for each f(n) for n = 0,1,2,...,10?

For (b) I know to show non-surjectivity and non-injectivity we need to provide a a counterexample, but I am not sure how I would use congruence to find this.

For (c) I am not really sure where to begin and what the concluding line should look like.

My attempt so far for (a) is:

$f_{11}([0]) = 0^2 = 0 \equiv 0 \pmod{11}$,

$f_{11}([1]) = 1^2 = 1 \equiv 1 \pmod{11}$,

$f_{11}([2]) = 2^2 = 4 \equiv 4 \pmod{11}$,

$f_{11}([3]) = 3^2 = 9 \equiv 9 \pmod{11}$,

$f_{11}([4]) = 4^2 = 16 \equiv 5 \pmod{11}$,

$f_{11}([5]) = 5^2 = 25 \equiv 3 \pmod{11}$,

$f_{11}([6]) = 6^2 = 36 \equiv 3 \pmod{11}$,

$f_{11}([7]) = 7^2 = 49 \equiv 5 \pmod{11}$,

$f_{11}([8]) = 8^2 = 64 \equiv 9 \pmod{11}$,

$f_{11}([9]) = 9^2 = 81 \equiv 4 \pmod{11}$,

$f_{11}([10]) = 10^2 = 100 \equiv 1 \pmod{11}$

for (b):

$f_{11}([5]) \equiv f_{11}([6]) \equiv 3 \pmod{11} \Rightarrow$ not injective.

Not sure for surjectivity.

Answer 1

For (a) you have to compute all the $x^2$ like in the example.

For (b) we can do it faster: because $\mathbb{Z}_{11}$ is a finite set, then if $f:\mathbb{Z}_{11} \rightarrow \mathbb{Z}_{11}$ is not injective, $|f(\mathbb{Z}_{11})| < |\mathbb{Z}_{11}|$ and it can't be surjective. Tabulating $f_{11}$ in (a) you can check that $5^2 \equiv_{11} 6^2$ or we can conclude from (c).

For (c) we can use the hint: $(n-1)^2 = n^2 - 2n +1 \equiv_n 1 = 1^2$ (and $n-1 \neq 1$).

Answer 2

fo $a$ you just lised them.

For $b$ it check one-to-one you check to see if there are any cases where $a\ne b$ but $f(a) = f(b)$. And there are: $f([5]) = f([6]$ for one example so it isn't 1-1.

To check surjective just check see if for every value $[m]$ there is an $[n]$ so that $f([n]) = [m]$. So is there $f[n] = [0]$? yep, $f([0]) = [0]$. So far so good. Is there $f[n] = 1$? Yep $f([1]) = 1; f([10]) = 1$. So far so good. Is there $f[n] = [2]$? Um.....no.... doesn't seem to be. So that's it. It's not surjective.

$c$. Just follow the hint. If $n\ge 2$ then $[n-1] \ne [n]$ (why?). And if $f$ is one-to-one then $f_n([n-1]) \ne f_n([1])$? Does it or doesn't it? What is $[1]^2$ and what is $[n-1]^2$? Are they always different? Are they sometimes different sometimes the same? Are they always the same?