The permutation $\alpha : \mathbb Z_{11} \rightarrow \mathbb Z_{11}$ given by $\alpha(x)=4x^2-3x^7$ is a cycle? If it´s not a cycle then write it as a product of disjoint cycles.
Is the permutation $\alpha : \mathbb Z_{11} \rightarrow \mathbb Z_{11}$ given by $\alpha(x)=4x^2-3x^7$ a cycle or not?
-
0@TMM: Nothing to worry about. I mean, this question does not exactly have the ring of a FAQ to it :-). You have my +1. Srivatsan doesn't write down the cycles explicitly, and in theory his answer leaves it open, whether the restriction of $\alpha$ on the QRs (or NQRs) is a cycle, or even the identity mapping. – 2012-03-28
1 Answers
Of course martini's comment is very true, as the easiest thing to do would just be computing $\alpha(x) \bmod 11$ for $x = 0, 1, \ldots, 10$, and seeing if we get a cycle. But let us try to be clever, and try to obtain the cycles without doing 'brute force' calculations. (Maybe it's too much, in which case you can just skip to the bottom...)
First, modulo $11$, by Euler's theorem we have that $x^{10} \equiv 1$ for $x \neq 0$, but also $x^5 = +1$ if $x$ is a quadratic residue, and $x^5 = -1$ if $x$ is a quadratic nonresidue in $\mathbb{Z}_{11}^{*}$. So:
$\alpha(x) = 4x^2 - 3x^7 \equiv 4x^2 + 8x^7 = 4x^2(1 + 2x^5) \equiv 4x^2(1 + 2(\pm1))\equiv \begin{cases} x^2, & \text{if }x \in \square, \\ 7x^2, & \text{if } x \notin \square. \end{cases}$
Since $7 \equiv -4 \bmod 11$ and $4 \in \square$ we have $7 \notin \square$, and since $7^2 \not\equiv 1 \bmod 11$ it follows that $7$ is a generator of $\mathbb{Z}_{11}^{*}$. And in terms of powers of $7$, the function $\alpha$ is simple:
$\alpha(7^k) \equiv \begin{cases} 7^{2k} & \text{if } k \text{ even} \\ 7^{2k+1} & \text{if } k \text{ odd} \end{cases}$
Also note that $7^{10 + k} \equiv 7^k$ by Euler, so we can reduce the exponents modulo $10$. So in terms of the generator $7$, we get the following cycles:
$7^0 \to 7^0 \\ 7^1 \to 7^3 \to 7^7 \to 7^5 \to 7^{1} \\ 7^2 \to 7^4 \to 7^8 \to 7^6 \to 7^2 \\ 7^9 \to 7^9 \\ (0 \to 0)$
To get actual numbers out of this we do need to do some calculations now. But notice that to obtain the result that we have two cycles of length $4$ and three cycles of length $1$, we arguably did not have to do any calculations. In any case, these cycles correspond to the following numbers.
$1 \to 1 \\ 7 \to 2 \to 6 \to 10 \to 7 \\ 5 \to 3 \to 9 \to 4 \to 5 \\ 8 \to 8 \\ (0 \to 0)$
So as a product of cycles, we get $(1)(7,2,6,10)(5,3,9,4)(8)(0)$.