Please Login to access more options.

Problem 36 (Permutations of $U(n)$)

Suppose $n$ is an integer greater than 1 and let $X=U(n)$, so the set of integers mod $n$ that have a multiplicative inverse mod $n$. For each $a\in U(n)$, we can define a permutation of $U(n)$ by $f_a(x)=xa\pmod n$ for each $x\in U(n)$. This problem asks you to show that this is indeed a permutation of $U(n)$. This requires that you show the following:

  1. For each integer $n\geq 2$, show that if $a\in U(n)$ and $x\in U(n)$, then the product $f_a(x)=xa\pmod n\in U(n)$. This shows that $f_a:U(n)\to U(n)$ is a map from $U(n)$ to $U(n)$.
  2. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is one-to-one. (As a reminder, one-to-one means that if $f_a(x)=f_a(y)$, then $x=y$.)
  3. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is onto. (As a reminder, onto means that if $y\in U(n)$, then there exists $x\in U(n)$ such that $f_a(x)=y$.)

Solution

1. Let $n\geq 2$. Let $a,x\in U(n)$. We will show that $f_a(x)=xa\pmod n \in U(n)$. Since $a, x \in U(n)$, we know there exists $c_1, c_2 \in \mathbb{Z}_n$ such that $c_1a\pmod n =1$ and $c_2a\pmod n =1$. Note that $ac_1\pmod n =c_1a\pmod n =1$, so $c_1\in U(n)$. Likewise $c_2\in U(n)$. To show that $xa\pmod n \in U(n)$, we will show that there exists a $c\in \mathbb{Z}_n$ such that $cxa\pmod n =1$. I claim that $c=c_1c_2\pmod n$ satisfies these conditions. Clearly $c\in \mathbb{Z}_n$. We first compute $$ \begin{align} c_1c_2xa\pmod n&=c_1ac_2x\pmod n\\ &=(c_1a\pmod n c_2x\pmod n)\mod n\\ &=((1)(1))\mod n\\ &=1 \end{align} $$ We now compute $$ \begin{align} c_1c_2xa\pmod n&=(c_1c_2\pmod n xa\pmod n)\mod n\\ &=((c_1c_2\pmod n\pmod n )xa\pmod n)\mod n\\ &=((c_1c_2\pmod n)xa)\mod n \end{align} $$ Since $((c_1c_2\pmod n)xa)\mod n=c_1c_2xa\pmod n$ and $c_1c_2xa\pmod n=1$, we conclude that $((c_1c_2\pmod n)xa)\mod n=1$.

2. Let $x,y\in U(n)$ and suppose $f_a(x)=f_a(y)$, or $ax\pmod n=ay\pmod n$. We will show that $x=y$. Let $c\in \mathbb{Z}_n$ such that $ca\pmod n=1$. We can multiply $ax\pmod n =ay\pmod n$ by $c$ to obtain $cax\pmod n =cay\pmod n$. It then follows that $(ca\pmod n x\pmod n)\pmod n =(ca\pmod n y\pmod n)\pmod n$. Since $ca\pmod n=1$, this means $x\pmod n \pmod n=y\pmod n \pmod n$, or $x\pmod n =y\pmod n$. Since $x,y \in U(n)$, we know $1\leq x,y < n$, and hence $x=y$.

3. Let $y\in U(n)$. We must find $x\in U(n)$ such that $ax\pmod n =y$. Let $x=a^{-1}y\pmod n$. Since $a\in U(n)$, we know $a^{-1} \in U(n)$. From part 1, we know $x=a^{-1}y\pmod n \in U(n)$. We compute

$$ \begin{align} ax\pmod n &=a(a^{-1}y\pmod n )\mod n\\ &=(a\pmod n a^{-1}y\pmod n )\mod n\\ &=aa^{-1}y\pmod n\\ &=y\pmod n\\ &=y \end{align} $$

Tags

Change these as needed.

  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.